Judicious partitions of uniform hypergraphs

DOI10.1007/S00493-014-2916-7MaRDI QIDQ484549zbMATH OpenOpenAlexFDO

Authors John Haslegrave

Publication date 7 January 2015

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.0563

zbMATH Keywords

partitionsuniform hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The vertices of any graph with $m$ edges can be partitioned into two parts so that each part meets at least $frac2m3$ edges. Bollob'as and Thomason conjectured that the vertices of any $r$-uniform graph may be likewise partitioned into $r$ classes such that each part meets at least $cm$ edges, with $c=fracr2r-1$. In this paper, we prove this conjecture for the case $r=3$. In the course of the proof we shall also prove an extension of the graph case which was conjectured by Bollob'as and Scott.

Recommendations

• On judicious partitions of uniform hypergraphs
• Judicious partitions of 3-uniform hypergraphs
• Partitioning 3-uniform hypergraphs
• Judicious partitions of hypergraphs
• Judiciously 3-partitioning 3-uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 475586 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1787231 (Why is no real title available?)
• Bipartite subgraphs of integer weighted graphs
• Exact bounds for judicious partitions of graphs
• Graph partitions. II
• Judicious partitions and related problems
• Judicious partitions of 3-uniform hypergraphs
• Judicious partitions of graphs
• Judicious partitions of hypergraphs
• On a bottleneck bipartition conjecture of Erdős
• Problems and results on judicious partitions
• The Bollobás-Thomason conjecture for \(3\)-uniform hypergraphs

Cited in

(19)

• Balanced judicious bipartition is fixed-parameter tractable
• On judicious partitions of uniform hypergraphs
• Optimal bisections of directed graphs
• 4-books of three pages
• Judicious bisection of hypergraphs
• Judicious partitioning of hypergraphs with edges of size at most 2
• Judiciously 3-partitioning 3-uniform hypergraphs
• Defective coloring of hypergraphs
• Counting connected partitions of graphs
• Problems and results on judicious partitions
• The partition of a uniform hypergraph into pairs of dependent hyperedges
• Erdős-Pyber theorem for hypergraphs and secret sharing
• The Bollobás-Scott conjecture for 4-uniform hypergraphs
• Partitioning 3-uniform hypergraphs
• On a problem of judicious \(k\)-partitions of graphs
• The Bollobás-Thomason conjecture for \(3\)-uniform hypergraphs
• Graph partitioning: an updated survey
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• Hypergraph cuts above the average

This page was built for publication: Judicious partitions of uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q484549)