A discrepancy version of the Hajnal-Szemerédi theorem

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

Research output: Contribution to journalArticlepeer-review

Abstract

A perfect Kr-tiling in a graph G is a collection of vertex-disjoint copies of the clique Kr in G covering every vertex of G. The famous Hajnal-Szemerédi theorem determines the minimum degree threshold for forcing a perfect Kr-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 Kr-tiling of high discrepancy.

Original languageEnglish (US)
JournalCombinatorics Probability and Computing
DOIs
StateAccepted/In press - 2020

Keywords

  • 05C35
  • 05C70
  • 2020 MSC Codes:

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A discrepancy version of the Hajnal-Szemerédi theorem'. Together they form a unique fingerprint.

Cite this