---
_id: '9580'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: David
full_name: Conlon, David
last_name: Conlon
- first_name: Jacob
full_name: Fox, Jacob
last_name: Fox
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
- first_name: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: 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-z
apa: Conlon, 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-z
chicago: Conlon, 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.
ieee: 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.
ista: Conlon D, Fox J, Kwan MA, Sudakov B. 2019. Hypergraph cuts above the average.
Israel Journal of Mathematics. 233(1), 67–111.
mla: 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.
short: D. Conlon, J. Fox, M.A. Kwan, B. Sudakov, Israel Journal of Mathematics 233
(2019) 67–111.
date_created: 2021-06-21T13:36:02Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2021-08-09T12:25:11Z
day: '01'
doi: 10.1007/s11856-019-1897-z
extern: '1'
external_id:
arxiv:
- '1803.08462'
intvolume: ' 233'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.08462
month: '08'
oa: 1
oa_version: Preprint
page: 67-111
publication: Israel Journal of Mathematics
publication_identifier:
eissn:
- 1565-8511
issn:
- 0021-2172
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Hypergraph cuts above the average
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 233
year: '2019'
...