A discrepancy version of the Hajnal-Szemerédi theorem

DOI10.1017/S0963548320000516MaRDI QIDQ4993133zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1182903 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 4000052 (Why is no real title available?)
• scientific article; zbMATH DE number 881162 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A degree sequence Hajnal-Szemerédi theorem
• A multipartite Hajnal-Szemerédi theorem
• An Ore-type theorem on equitable coloring
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• Blow-up lemma
• Critical chromatic number and the complexity of perfect packings in graphs
• On the Complexity of General Graph Factor Problems
• On the discrepancies of graphs
• Packings of graphs and applications to computational complexity
• Proof of the Alon-Yuster conjecture
• Proof of the Seymour conjecture for large graphs
• Robustness of graph properties
• Tiling directed graphs with tournaments
• \(H\)-factors in dense graphs

Cited in

(14)

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

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)