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