MathDB

The universal-cycle conjecture for pairwise balanced designs

About 2 years old · traced to

Let a (v,K,λ)(v,K,\lambda)-pairwise balanced design be a vv-vertex hypergraph whose 22-degree is λ\lambda and whose edge cardinalities belong to a set of integers KK. A base block is called regular when it satisfies the regularity condition used in the design's construction; otherwise it is non-regular. Universal-cycle conjecture. Every (v,K,λ)(v,K,\lambda)-PBD with min⁡K≥3\min K\geq 3 and a sufficient number of non-regular base blocks admits a universal cycle of rank two. This conjecture concerns ordering the blocks of a design so that consecutive blocks overlap in one point; the source does not quantify “a sufficient number” or provide evidence resolving the conjecture, so its status remains open.

References

Primary source

Amin Bahmanian and Songling Shan, “Spanning Euler Tours in Hypergraphs”, arXiv:2403.12713 (2024).

design-theoryhypergraphsuniversal-cycles
Posted

Progress summary

Refreshed
Claimed progress

A 2024 paper settles most known cases of the conjecture but leaves a substantial family of designs unresolved.

The conjecture is attributed to Dewar and Stevens and asserts that sufficiently non-regular pairwise balanced designs with blocks of size at least 33 have a cyclic ordering in which consecutive blocks overlap in one point.

Known results

  • Earlier work covers pairwise balanced designs with maximum block size at most twice the minimum block size.
  • Earlier work also covers pairwise balanced designs with minimum block size at least 33.
  • Dewar studied universal cycles for block designs; Graham first raised the existence question for Steiner triple systems in 19871987.

2024 near-resolution

The paper “Spanning Euler Tours in Hypergraphs” says its main theorem settles rank-two universal cycles for the vast majority of designs. In particular, it proves the conjectured conclusion when λ≥max⁡K\lambda\geq\max K and there are sufficiently many points. The remaining gap is for 22-designs with index λ<max⁡K\lambda<\max K; no complete proof, counterexample, or subsequent verification was found.

Current status (as of August 2026): A substantial partial result is established, but the universal-cycle conjecture remains open for 22-designs with λ<max⁡K\lambda<\max K.

Sources

Solutions 0

No solutions have been posted yet.