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

At least 9 years old · documented by

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

p=b+t−1t,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 M′M' 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 ⌊b−1p−1⌋\left\lfloor\frac{b-1}{p-1}\right\rfloor-disjunct matrix, but the supplied text gives no resolution of this conjecture.

References

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.