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...
| Hauptverfasser: | , , , |
|---|---|
| Format: | Journal article |
| Sprache: | English |
| Veröffentlicht: |
Hebrew University Magnes Press
2019
|