← All problems

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 22, then its vertex set has a bipartition such that each class meets edges of total weight at least w1−Δ12+2w23\frac{w_1-\Delta_1}{2}+\frac{2w_2}{3}, where wiw_i is the total weight of the edges of size ii and Δ1\Delta_1 is the maximum weight of an edge of size 11. (2) If a hypergraph has all edges of size at most 33, then, writing mim_i for the number of edges of size ii, its vertex set has a bipartition such that each class meets at least m12+3m24+7m38+o(m1+m2+m3)\frac{m_1}{2}+\frac{3m_2}{4}+\frac{7m_3}{8}+o(m_1+m_2+m_3) edges. (3) For every integer k≥4k\ge 4, every graph with m≥2(k−1)(k−2)m\ge 2(k-1)(k-2) edges has a partition into kk vertex classes, each of which meets at least 2m2k−1\frac{2m}{2k-1} edges. (4) For all sufficiently large mm, every 44-uniform hypergraph with mm edges has a partition into four vertex classes, each of which meets at least 4m7\frac{4m}{7} edges.

References

Progress summary

Refreshed
Open · progress reported

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 g(m)g(m) was confirmed asymptotically in the cited bipartition work.
  • For 33-uniform hypergraphs, a Bollobás–Thomason-type bound of 5m−19\frac{5m-1}{9} was reported, but a later source notes a subtle error in that proof.
  • For r≥4r\ge 4, Haslegrave proved the weaker lower bound r3r−4m\frac{r}{3r-4}m, versus the conjectured r2r−1m\frac{r}{2r-1}m.
  • A separate preprint claims the Bollobás–Scott upper bound mk3+Ok(m2/3)\frac{m}{k^3}+O_k(m^{2/3}) for fixed kk in the 33-uniform case.

October 2026 preprint claims

Lin and Zeng claim proofs of the first three stated Bollobás–Scott conjectures and the 44-uniform Bollobás–Thomason conjecture in the specified regimes. Separately, the 33-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.

Sources

Solutions 0

No solutions have been posted yet.