Journal article icon

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:
Publisher copy:
10.1007/s11856-019-1897-z

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Oxford college:
Wadham College
Role:
Author
ORCID:
0000-0001-5899-1829
More from this funder
Funding agency for:
Conlon, D
Grant:
676632
More from this funder
Funding agency for:
Conlon, D
Grant:
676632
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
Source identifiers:
940936
Language:
English
Pubs id:
pubs:940936
UUID:
uuid:36932992-ff54-4cb1-a89c-a07519b732a2
Local pid:
pubs:940936
Deposit date:
2018-11-11

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP