Hypergraph cuts above the average
Conlon, David
Fox, Jacob
Kwan, Matthew Alan
Sudakov, Benny
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.
Springer
2019
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.app.ist.ac.at/record/9580
Conlon D, Fox J, Kwan MA, Sudakov B. Hypergraph cuts above the average. <i>Israel Journal of Mathematics</i>. 2019;233(1):67-111. doi:<a href="https://doi.org/10.1007/s11856-019-1897-z">10.1007/s11856-019-1897-z</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/s11856-019-1897-z
info:eu-repo/semantics/altIdentifier/issn/0021-2172
info:eu-repo/semantics/altIdentifier/issn/1565-8511
info:eu-repo/semantics/altIdentifier/arxiv/1803.08462
info:eu-repo/semantics/openAccess