The forbidden-configuration bound for binary matrices

Less than 1 year old · traced to

Let tt be given, and let forb(m,F(0,2t−2+1,1,0)){\mathrm{forb}}(m,F(0,2^{t-2}+1,1,0)) denote the maximum number of columns in an mm-rowed binary matrix avoiding the configuration F(0,2t−2+1,1,0)F(0,2^{t-2}+1,1,0). Forbidden-configuration bound conjecture.

forb(m,F(0,2t−2+1,1,0))≤2t−1tm+1,{\mathrm{forb}}(m,F(0,2^{t-2}+1,1,0))\leq \frac{2^{t}-1}{t}m+1,

with equality when m≡0(modt)m\equiv 0\pmod{t}. The conjecture is motivated by constructions using the matrix KtK_t and the matrices Bi=Kt\1tB_i=K_t\backslash \mathbf{1}_t, which attain the stated bound in the displayed cases; its validity for arbitrary tt is not established in the supplied text.

References

Primary source

Richard P. Anstee, Oakley Edens, Arvin Sahami, Jaehwan Seok and Attila Sali, “Exact Bounds for Forbidden Configurations and the Extremal Matrices”, arXiv:2601.04084 (2026).

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.