Hypergraph cuts above the average
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, the...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Hebrew University Magnes Press
2019
|
| _version_ | 1826267033107431424 |
|---|---|
| author | Conlon, D Fox, J Kwan, M Sudakov, B |
| author_facet | Conlon, D Fox, J Kwan, M Sudakov, B |
| author_sort | Conlon, D |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T20:48:00Z |
| format | Journal article |
| id | oxford-uuid:36932992-ff54-4cb1-a89c-a07519b732a2 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T20:48:00Z |
| publishDate | 2019 |
| publisher | Hebrew University Magnes Press |
| record_format | dspace |
| spelling | oxford-uuid:36932992-ff54-4cb1-a89c-a07519b732a22022-03-26T13:38:52ZHypergraph cuts above the averageJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:36932992-ff54-4cb1-a89c-a07519b732a2EnglishSymplectic Elements at OxfordHebrew University Magnes Press2019Conlon, DFox, JKwan, MSudakov, BAn 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. |
| spellingShingle | Conlon, D Fox, J Kwan, M Sudakov, B Hypergraph cuts above the average |
| title | Hypergraph cuts above the average |
| title_full | Hypergraph cuts above the average |
| title_fullStr | Hypergraph cuts above the average |
| title_full_unstemmed | Hypergraph cuts above the average |
| title_short | Hypergraph cuts above the average |
| title_sort | hypergraph cuts above the average |
| work_keys_str_mv | AT conlond hypergraphcutsabovetheaverage AT foxj hypergraphcutsabovetheaverage AT kwanm hypergraphcutsabovetheaverage AT sudakovb hypergraphcutsabovetheaverage |