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.

Review text

It is known that the vertices of any graph with \(m\) edges may be partitioned into two parts so that each part meets at least \(\frac{2}{3} m\) edges. \textit{B. Bollobás} et al. [Contemp. Math. 147, 161--165 (1993; Zbl 0787.05053)] conjectured that the vertices of any \(r\)-uniform hypergraph with \(m\) edges may be partitioned into \(r\) classes such that each part meets at least \(\frac{r}{2r-1} m\) edges. The author recently proved the conjecture for the case \(r=3\), see [the author, Combinatorica 32, No. 4, 451--471 (2012; Zbl 1299.05184)]. In this paper, a weaker result is established: for each \(r \geq 4\), a partition into \(r\) classes may be found in which each class meets at least \(\frac{r}{3r-4} m\) edges. This is a significant improvement on previous bounds. All results obtained in this paper apply to hypergraphs with repeated edges.

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

• Bipartite subgraphs of integer weighted graphs
• Exact bounds for judicious partitions of graphs
• Graph partitions. II
• 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?)
• 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

(21)

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

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)