A discrepancy version of the Hajnal-Szemerédi theorem

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • University of Szeged
  • University of Illinois

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.

Details

Original languageEnglish
Pages (from-to)444-459
Number of pages16
JournalCombinatorics, Probability and Computing
Volume30
Issue number3
Early online date30 Oct 2020
Publication statusPublished - May 2021