A Multipartite Hajnal-Szemerédi Theorem

Peter Keevash; Richard Mycroft

doi:10.1016/j.jctb.2015.04.003

A Multipartite Hajnal-Szemerédi Theorem

Peter Keevash, Richard Mycroft

Mathematics

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

178 Downloads (Pure)

Abstract

The celebrated Hajnal-Szemerédi theorem gives the precise minimum degree
threshold that forces a graph to contain a perfect K_k-packing. Fischer’s conjecture states that the analogous result holds for all multipartite graphs except for those formed by a single construction. Recently, we deduced an approximate version of this conjecture from new results on perfect matchings in hypergraphs. In this paper, we apply a stability analysis to the extremal cases of this argument, thus showing that the exact conjecture holds for any sufficiently large graph.

Original language	English
Pages (from-to)	187-236
Number of pages	50
Journal	Journal of Combinatorial Theory. Series B
Volume	114
Early online date	24 Apr 2015
DOIs	https://doi.org/10.1016/j.jctb.2015.04.003
Publication status	Published - Sept 2015

Keywords

graph theory
perfect packing

Access to Document

10.1016/j.jctb.2015.04.003

Keevash_Multipartite_Hajnal-Szemeredi_Theorem_Combinatorial_Theory_B_2015
NOTICE: this is the author’s version of a work that was accepted for publication in Journal of Combinatorial Theory, Series B. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Journal of Combinatorial Theory, Series B, DOI: 10.1016/j.jctb.2015.04.003. Eligibility for repository checked April 2015.
Accepted author manuscript, 470 KB

Cite this

@article{bff0133b985f4701b98fd12270669a3c,

title = "A Multipartite Hajnal-Szemer{\'e}di Theorem",

abstract = "The celebrated Hajnal-Szemer{\'e}di theorem gives the precise minimum degreethreshold that forces a graph to contain a perfect K_k-packing. Fischer{\textquoteright}s conjecture states that the analogous result holds for all multipartite graphs except for those formed by a single construction. Recently, we deduced an approximate version of this conjecture from new results on perfect matchings in hypergraphs. In this paper, we apply a stability analysis to the extremal cases of this argument, thus showing that the exact conjecture holds for any sufficiently large graph.",

keywords = "graph theory, perfect packing",

author = "Peter Keevash and Richard Mycroft",

year = "2015",

month = sep,

doi = "10.1016/j.jctb.2015.04.003",

language = "English",

volume = "114",

pages = "187--236",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - A Multipartite Hajnal-Szemerédi Theorem

AU - Keevash, Peter

AU - Mycroft, Richard

PY - 2015/9

Y1 - 2015/9

N2 - The celebrated Hajnal-Szemerédi theorem gives the precise minimum degreethreshold that forces a graph to contain a perfect K_k-packing. Fischer’s conjecture states that the analogous result holds for all multipartite graphs except for those formed by a single construction. Recently, we deduced an approximate version of this conjecture from new results on perfect matchings in hypergraphs. In this paper, we apply a stability analysis to the extremal cases of this argument, thus showing that the exact conjecture holds for any sufficiently large graph.

AB - The celebrated Hajnal-Szemerédi theorem gives the precise minimum degreethreshold that forces a graph to contain a perfect K_k-packing. Fischer’s conjecture states that the analogous result holds for all multipartite graphs except for those formed by a single construction. Recently, we deduced an approximate version of this conjecture from new results on perfect matchings in hypergraphs. In this paper, we apply a stability analysis to the extremal cases of this argument, thus showing that the exact conjecture holds for any sufficiently large graph.

KW - graph theory

KW - perfect packing

U2 - 10.1016/j.jctb.2015.04.003

DO - 10.1016/j.jctb.2015.04.003

M3 - Article

SN - 0095-8956

VL - 114

SP - 187

EP - 236

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

A Multipartite Hajnal-Szemerédi Theorem

Abstract

Keywords

Access to Document

Fingerprint

Cite this