A következő kombinatorika szeminárium ideje

április 11. (péntek), ! 10:30 !,

helye

Kalmár Intézet, Árpád tér, szemináriumi szoba (második emelet, a folyosó vége)

és előadása:

Andrew Treglown (Queen Mary, University of London): On generalisations of the Hajnal-Szemerédi theorem

We say that a graph G has a perfect H-packing if there exists a set of vertex-disjoint copies of H which cover all the vertices in G. The seminal Hajnal-Szemerédi theorem states that every graph G whose order n is divisible by r and whose minimum degree is at least (1-1/r)n contains a perfect Kr-packing. It is easy to see that the minimum degree condition here is "best-possible".

Balogh, Kostochka and the speaker gave a conjecture on the degree sequence of a graph G that forces a perfect Kr-packing in G. If true, the conjecture is a strong generalisation of the Hajnal-Szemerédi theorem as it allows for n/r vertices in G to have degree less than (1-1/r)n. In this talk I will mention a very recent asymptotic solution to this conjecture. I will also discuss recent results on generalising the Hajnal-Szemerédi theorem to the directed graph setting.

Mindenkit szeretettel várunk,

Péter

Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073, Telemedicine Oriented Research in the Fields of Mathematics, Informatics and Medical Sciences