Judicious partitions of 3-uniform hypergraphs (Q1972352): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q591728 |
||
Property / author | |||
Property / author: Q222637 / rank | |||
Revision as of 00:46, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Judicious partitions of 3-uniform hypergraphs |
scientific article |
Statements
Judicious partitions of 3-uniform hypergraphs (English)
0 references
26 April 2000
0 references
A conjecture of Bolloás and Thomason asserts that, for \(r\geq 1\), the vertex set of every \(r\)-uniform hypergraph can be partitioned into \(r\) classes so that every class meets at least \(rm/(2r- 1)\) edges. This paper offers some partial results in support of this conjecture. It is proved that the vertices of a 3-uniform hypergraph with \(m\) edges can be partitioned into 3 classes such that every class meets at least \((5m- 1)/9\) edges. It is also proved that for \(r>3\) the vertex set of an \(r\)-uniform hypergraph can be partitioned into \(r\) classes such that each class meets at least \(0.27m\) edges. The paper concludes with two related conjectures. A factor of \(m\) was inadvertently omitted from the last conjectured bound on page 299.
0 references
partitions
0 references
hypergraph
0 references