Conlon, David and Fox, Jacob and Kwan, Matthew and Sudakov, Benny (2019) Hypergraph cuts above the average. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190819-170914451
![]() |
PDF
- Submitted Version
See Usage Policy. 719kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190819-170914451
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 Ω(m^(5/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.
Item Type: | Report or Paper (Discussion Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||
ORCID: |
| ||||||||||||
Additional Information: | Conlon research supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. Fox research supported by a Packard Fellowship and by NSF Career Award DMS-1352121. Sudakov research supported in part by SNSF grant 200021-175573. | ||||||||||||
Funders: |
| ||||||||||||
Record Number: | CaltechAUTHORS:20190819-170914451 | ||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190819-170914451 | ||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
ID Code: | 98027 | ||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||
Deposited By: | Melissa Ray | ||||||||||||
Deposited On: | 20 Aug 2019 19:49 | ||||||||||||
Last Modified: | 03 Oct 2019 21:37 |
Repository Staff Only: item control page