A discrepancy version of the Hajnal-Szemerédi theorem

DOI10.1017/S0963548320000516zbMATH Open1466.05174arXiv2002.12594OpenAlexW3096772174MaRDI QIDQ4993133FDOQ4993133

Authors: József Balogh, Béla Csaba, András Pluhár, Andrew Treglown 

Publication date: 15 June 2021

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

Abstract: A perfect $K_r$-tiling in a graph $G$ is a collection of vertex-disjoint copies of the clique $K_r$ in $G$ covering every vertex of $G$. The famous Hajnal--Szemer'edi theorem determines the minimum degree threshold for forcing a perfect $K_r$-tiling in a graph $G$. The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph $G$ labels from $-1,1$, and one seeks substructures $F$ of $G$ that have `high' discrepancy (i.e. the sum of the labels of the edges in $F$ is far from $0$). In this paper we determine the minimum degree threshold for a graph to contain a perfect $K_r$-tiling of high discrepancy.

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

Recommendations

• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• A degree sequence version of the Kühn-Osthus tiling theorem
• Minimum degree thresholds for bipartite graph tiling
• Tilings in randomly perturbed dense graphs
• A degree sequence Hajnal-Szemerédi theorem

zbMATH Keywords

Hajnal-Szemerédi theoremperfect \(K_r\)-tiling

Mathematics Subject Classification ID

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

Cites Work

• Proof of the Seymour conjecture for large graphs
• \(H\)-factors in dense graphs
• An Ore-type theorem on equitable coloring
• A degree sequence Hajnal-Szemerédi theorem
• On the Complexity of General Graph Factor Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• Title not available (Why is that?)
• Proof of the Alon-Yuster conjecture
• Title not available (Why is that?)
• Packings of graphs and applications to computational complexity
• Blow-up lemma
• Title not available (Why is that?)
• A multipartite Hajnal-Szemerédi theorem
• Critical chromatic number and the complexity of perfect packings in graphs
• Title not available (Why is that?)
• Robustness of graph properties
• Tiling directed graphs with tournaments
• On the discrepancies of graphs

Cited In (13)

• Tilings in randomly perturbed dense graphs
• A proof of Sanov's theorem via discretizations
• Oriented discrepancy of Hamilton cycles
• An oriented discrepancy version of Dirac's theorem
• Minimum degree threshold for \(H\)-factors with high discrepancy
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• A note on color-bias Hamilton cycles in dense graphs
• A note on color-bias perfect matchings in hypergraphs
• Powers of Hamilton cycles of high discrepancy are unavoidable
• Discrepancies of spanning trees and Hamilton cycles
• Sufficient conditions for perfect mixed tilings
• Color‐biased Hamilton cycles in random graphs
• Unbalanced spanning subgraphs in edge labeled complete graphs

This page was built for publication: A discrepancy version of the Hajnal-Szemerédi theorem

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