Steiner-system extremal conjecture for constant-column-weight disjunct matrices

Let MM be an n×mn\times m tt-disjunct matrix with constant column weight bb. Set

p=b+t1t,p=\frac{b+t-1}{t},

and assume that pp is an integer. A Steiner system S(n,b,p)\mathfrak{S}(n,b,p) is a family of bb-subsets of an nn-element set such that every pp-subset is contained in exactly one member; the maximum such family is denoted by S(n,b,p)\mathfrak{S}(n,b,p). Steiner-system conjecture. The maximum S(n,b,p)\mathfrak{S}(n,b,p) Steiner system gives a matrix MM' that is no worse than MM, equivalently,

S(n,b,p)m.|\mathfrak{S}(n,b,p)|\ge m.

The conjecture proposes that Steiner-system constructions are at least as efficient as arbitrary constant-column-weight tt-disjunct matrices with the same parameters. The surrounding discussion notes that the Steiner construction yields a b1p1\left\lfloor\frac{b-1}{p-1}\right\rfloor-disjunct matrix, but the supplied text gives no resolution of this conjecture.

Sources & referencesView supporting material

Primary source

Rasagna Chigullapally, Harshithanjani Athi, Nikhil Karamchandani and V. Lalitha, “On Distributed Multi-User Secret Sharing with Multiple Secrets per User”, arXiv:2312.15763 (2024).

Additional references

3 papers in this index state this conjecture (2016–2023). The statement above is taken from the most recent of them; the others are arXiv:2204.03964, arXiv:1607.04813.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.