Bollobás–Scott and Bollobás–Thomason judicious partition conjectures
Let a hypergraph edge be met by a vertex class if the edge intersects that class. The Bollobás–Scott and Bollobás–Thomason partition conjectures comprise the following assertions. (1) If a hypergraph has nonnegative edge weights and every edge has size at most , then its vertex set has a bipartition such that each class meets edges of total weight at least , where is the total weight of the edges of size and is the maximum weight of an edge of size . (2) If a hypergraph has all edges of size at most , then, writing for the number of edges of size , its vertex set has a bipartition such that each class meets at least edges. (3) For every integer , every graph with edges has a partition into vertex classes, each of which meets at least edges. (4) For all sufficiently large , every -uniform hypergraph with edges has a partition into four vertex classes, each of which meets at least edges.
References
- On several judicious partitioning problems of graphs and hypergraphs — arXiv — Siwei Lin, Qinghou Zeng
Source: arXiv
Progress summary
A new unrefereed preprint claims to settle several sharp partition conjectures, but the broader collection remains open and the claims have not been independently checked.
The Bollobás–Scott and Bollobás–Thomason conjectures seek sharp partitions of graphs and hypergraphs with optimal edge-distribution bounds. The latest claim covers several specified regimes, not every uniformity or formulation.
Known results
- The graph Bollobás–Scott conjecture concerning was confirmed asymptotically in the cited bipartition work.
- For -uniform hypergraphs, a Bollobás–Thomason-type bound of was reported, but a later source notes a subtle error in that proof.
- For , Haslegrave proved the weaker lower bound , versus the conjectured .
- A separate preprint claims the Bollobás–Scott upper bound for fixed in the -uniform case.
October 2026 preprint claims
Lin and Zeng claim proofs of the first three stated Bollobás–Scott conjectures and the -uniform Bollobás–Thomason conjecture in the specified regimes. Separately, the -uniform asymptotic result reports assistance from ChatGPT 5.5 with proof strategies, checking, and exposition; the mathematical claims remain unverified.
Current status (as of October 2026): Several subcases are claimed solved in unrefereed preprints, but no independent verification is recorded and the full collection remains open.
Solutions 0
No solutions have been posted yet.