---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: David
foaf_name: Conlon, David
foaf_surname: Conlon
- foaf_Person:
foaf_givenName: Jacob
foaf_name: Fox, Jacob
foaf_surname: Fox
- foaf_Person:
foaf_givenName: Matthew Alan
foaf_name: Kwan, Matthew Alan
foaf_surname: Kwan
foaf_workInfoHomepage: http://www.librecat.org/personId=5fca0887-a1db-11eb-95d1-ca9d5e0453b3
- foaf_Person:
foaf_givenName: Benny
foaf_name: Sudakov, Benny
foaf_surname: Sudakov
bibo_doi: 10.1007/s11856-019-1897-z
bibo_issue: '1'
bibo_volume: 233
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0021-2172
- http://id.crossref.org/issn/1565-8511
dct_language: eng
dct_publisher: Springer@
dct_title: Hypergraph cuts above the average@
...