Journal article
Hypergraph cuts above the average
- 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 simila...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Accepted manuscript, pdf, 590.1KB)
-
- Publisher copy:
- 10.1007/s11856-019-1897-z
Authors
Funding
Bibliographic Details
- Publisher:
- Hebrew University Magnes Press Publisher's website
- Journal:
- Israel Journal of Mathematics Journal website
- Volume:
- 233
- Issue:
- 1
- Pages:
- 67–111
- Publication date:
- 2019-07-09
- Acceptance date:
- 2018-11-08
- DOI:
- EISSN:
-
1565-8511
- ISSN:
-
0021-2172
Item Description
- Language:
- English
- Pubs id:
-
pubs:940936
- UUID:
-
uuid:36932992-ff54-4cb1-a89c-a07519b732a2
- Local pid:
- pubs:940936
- Source identifiers:
-
940936
- Deposit date:
- 2018-11-11
Terms of use
- Copyright holder:
- Hebrew University of Jerusalem
- Copyright date:
- 2019
- Rights statement:
- Copyright © 2019 The Hebrew University of Jerusalem.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Hebrew University Magnes Press at http://dx.doi.org/10.1007/s11856-019-1897-z
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record