Judicious partitions of uniform hypergraphs (Q484549): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Import241208061232 (talk | contribs)
Normalize DOI.
 
(One intermediate revision by one other user not shown)
Property / DOI
 
Property / DOI: 10.1007/s00493-014-2916-7 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1007/S00493-014-2916-7 / rank
 
Normal rank

Latest revision as of 18:56, 9 December 2024

scientific article
Language Label Description Also known as
English
Judicious partitions of uniform hypergraphs
scientific article

    Statements

    Judicious partitions of uniform hypergraphs (English)
    0 references
    0 references
    7 January 2015
    0 references
    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.
    0 references
    uniform hypergraphs
    0 references
    partitions
    0 references

    Identifiers