MathDB

The universal-cycle conjecture for pairwise balanced designs

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.

Sources & referencesView supporting material

Primary source

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

design-theoryhypergraphsuniversal-cycles

Progress summary

Refreshed
Partially solved

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.