HYPERGRAPH CUTS ABOVE THE AVERAGE

Author: 

Conlon, D
Fox, J
Kwan, M
Sudakov, B

Publication Date: 

August 2019

Journal: 

ISRAEL JOURNAL OF MATHEMATICS

Last Updated: 

2019-11-14T22:17:53.333+00:00

Issue: 

1

Volume: 

233

DOI: 

10.1007/s11856-019-1897-z

page: 

67-111

abstract: 

© 2019, The Hebrew University of Jerusalem. An r-cut of a k-uniform hypergraph H is a partition of the vertex set of H into r parts and the size of the cut is the number of edges which have a vertex in each part. A classical result of Edwards says that every m-edge graph has a 2-cut of size m/2+Ω(m) and this is best possible. That is, there exist cuts which exceed the expected size of a random cut by some multiple of the standard deviation. We study analogues of this and related results in hypergraphs. First, we observe that similarly to graphs, every m-edge k-uniform hypergraph has an r-cut whose size is Ω(m) larger than the expected size of a random r-cut. Moreover, in the case where k = 3 and r = 2 this bound is best possible and is attained by Steiner triple systems. Surprisingly, for all other cases (that is, if k ≥ 4 or r ≥ 3), we show that every m-edge k-uniform hypergraph has an r-cut whose size is Ω(m5/9) larger than the expected size of a random r-cut. This is a significant difference in behaviour, since the amount by which the size of the largest cut exceeds the expected size of a random cut is now considerably larger than the standard deviation.

Symplectic id: 

940936

Download URL: 

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article