A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs

DOI10.1017/S096354831200048XzbMATH Open1257.05130arXiv1108.4184MaRDI QIDQ4903264FDOQ4903264

Authors: Allan Lo, Klas Markström 

Publication date: 21 January 2013

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: A perfect $K_t$-matching in a graph $G$ is a spanning subgraph consisting of vertex disjoint copies of $K_t$. A classic theorem of Hajnal and Szemer'edi states that if $G$ is a graph of order $n$ with minimum degree $delta(G)ge(t-1)n/t$ and $t|n$, then $G$ contains a perfect $K_t$-matching. Let $G$ be a $t$-partite graph with vertex classes $V_1$,..., $V_t$ each of size $n$. We show that if every vertex $xin{V}_i$ is joined to at least $((t-1)/t+gamma)n$ vertices of $V_j$ for $iej$, then $G$ contains a perfect $K_t$-matching, thus verifying a conjecture of Fisher asymptotically. Furthermore, we consider a generalisation to hypergraphs in terms of the codegree.

Full work available at URL: https://arxiv.org/abs/1108.4184

Recommendations

• A multipartite Hajnal-Szemerédi theorem
• A multipartite Hajnal-Szemerédi theorem
• On multipartite Hajnal-Szemerédi theorems
• Hypergraph regularity and the multidimensional Szemerédi theorem
• A Harary-Sachs theorem for hypergraphs
• A hypergraph version of the Gallai-Edmonds Theorem
• A generalization of the Hajnal-Szemerédi theorem for uniform hypergraphs
• Multipartite Turán problem for connected graphs and hypergraphs
• Erdős-Hajnal-type theorems in hypergraphs
• Multipartite hypergraphs achieving equality in Ryser's conjecture

zbMATH Keywords

perfect \(K_t\)-matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (23)

• Powers of Hamiltonian cycles in multipartite graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Cyclic triangle factors in regular tournaments
• A geometric theory for hypergraph matching
• Proof of a tiling conjecture of Komlós
• Tiling tripartite graphs with 3-colorable graphs: the extreme case
• A multipartite Hajnal-Szemerédi theorem
• Approximate multipartite version of the Hajnal-Szemerédi theorem
• Quadripartite version of the Hajnal-Szemerédi theorem
• Transversal factors and spanning trees
• Rainbow spanning structures in graph and hypergraph systems
• Transversal C_k-factors in subgraphs of the balanced blow-up of C_k
• Triangle‐factors in pseudorandom graphs
• \(F\)-factors in hypergraphs via absorption
• An asymptotic bound for the strong chromatic number
• Almost perfect matchings in \(k\)-partite \(k\)-graphs
• Spanning trees in graphs without large bipartite holes
• Completion and deficiency problems
• Asymptotic multipartite version of the Alon-Yuster theorem
• Clique decompositions of multipartite graphs and completion of Latin squares
• Sufficient conditions for perfect mixed tilings
• An asymptotic multipartite Kühn-Osthus theorem
• On sufficient conditions for spanning structures in dense graphs

This page was built for publication: A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4903264)