Judicious partitions of uniform hypergraphs

DOI10.1007/S00493-014-2916-7zbMATH Open1340.05196arXiv0911.0563OpenAlexW1971692513MaRDI QIDQ484549FDOQ484549

Authors: John Haslegrave 

Publication date: 7 January 2015

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

partitionsuniform hypergraphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Judicious partitions of hypergraphs
• Bipartite subgraphs of integer weighted graphs
• Exact bounds for judicious partitions of graphs
• The Bollobás-Thomason conjecture for \(3\)-uniform hypergraphs
• Judicious partitions and related problems
• Title not available (Why is that?)
• Problems and results on judicious partitions
• Judicious partitions of 3-uniform hypergraphs
• On a bottleneck bipartition conjecture of Erdős
• Judicious partitions of graphs
• Title not available (Why is that?)
• Graph partitions. II

Cited In (19)

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

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)