Back to Search
Start Over
A discrepancy version of the Hajnal–Szemerédi theorem
- Source :
- Combinatorics, Probability and Computing. 30:444-459
- Publication Year :
- 2020
- Publisher :
- Cambridge University Press (CUP), 2020.
-
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.
- Subjects :
- Statistics and Probability
Vertex (graph theory)
Forcing (recursion theory)
Degree (graph theory)
Applied Mathematics
010102 general mathematics
0102 computer and information sciences
Clique (graph theory)
01 natural sciences
Theoretical Computer Science
Combinatorics
Computational Theory and Mathematics
010201 computation theory & mathematics
Graph (abstract data type)
0101 mathematics
Mathematics
Subjects
Details
- ISSN :
- 14692163 and 09635483
- Volume :
- 30
- Database :
- OpenAIRE
- Journal :
- Combinatorics, Probability and Computing
- Accession number :
- edsair.doi...........aa806d7ba4d9a1d2b7c62aa882e79789