# Hypergraph cuts above the average

Conlon D, Fox J, Kwan MA, Sudakov B. 2019. Hypergraph cuts above the average. Israel Journal of Mathematics. 233(1), 67–111.

Download (ext.)

*Journal Article*|

*Published*|

*English*

**Scopus indexed**

Author

Conlon, David;
Fox, Jacob;
Kwan, Matthew Alan

^{IST Austria}; Sudakov, BennyAbstract

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.

Publishing Year

Date Published

2019-08-01

Journal Title

Israel Journal of Mathematics

Volume

233

Issue

1

Page

67-111

ISSN

eISSN

IST-REx-ID

### Cite this

Conlon D, Fox J, Kwan MA, Sudakov B. Hypergraph cuts above the average.

*Israel Journal of Mathematics*. 2019;233(1):67-111. doi:10.1007/s11856-019-1897-zConlon, D., Fox, J., Kwan, M. A., & Sudakov, B. (2019). Hypergraph cuts above the average.

*Israel Journal of Mathematics*. Springer. https://doi.org/10.1007/s11856-019-1897-zConlon, David, Jacob Fox, Matthew Alan Kwan, and Benny Sudakov. “Hypergraph Cuts above the Average.”

*Israel Journal of Mathematics*. Springer, 2019. https://doi.org/10.1007/s11856-019-1897-z.D. Conlon, J. Fox, M. A. Kwan, and B. Sudakov, “Hypergraph cuts above the average,”

*Israel Journal of Mathematics*, vol. 233, no. 1. Springer, pp. 67–111, 2019.Conlon, David, et al. “Hypergraph Cuts above the Average.”

*Israel Journal of Mathematics*, vol. 233, no. 1, Springer, 2019, pp. 67–111, doi:10.1007/s11856-019-1897-z.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Link(s) to Main File(s)**

Access Level

Open Access

### Export

Marked PublicationsOpen Data IST Research Explorer

### Sources

arXiv 1803.08462