Anstee–Sali conjecture on forbidden configuration growth

About 14 years old · traced to

Let FF be a k×ℓk\times \ell matrix with F≠[01]F\ne \begin{bmatrix}0\\ 1\end{bmatrix}. Let IkI_k be the k×kk\times k identity matrix, IkcI_k^c its (0,1)-complement, and TkT_k the k×kk\times k upper triangular matrix whose iith column has 1's in rows 1,2,…,i1,2,\ldots,i. For matrices A1,…,ApA_1,\ldots,A_p, let A1×⋯×ApA_1\times\cdots\times A_p be their product configuration formed by stacking one column from each factor in every possible combination. Define forb⁡(m,F)\operatorname*{forb}(m,F) as the maximum number of columns in an mm-rowed simple matrix avoiding FF. Let X(F)X(F) be the largest pp for which there are choices A1,A2,…,Ap∈{Im/p,Im/pc,Tm/p}A_1,A_2,\ldots,A_p\in\{I_{m/p},I^c_{m/p},T_{m/p}\} such that F⊀A1×A2×⋯×ApF\nprec A_1\times A_2\times\cdots\times A_p. Anstee–Sali conjecture. Then

forb⁡(m,F)=Θ(mX(F)).\operatorname*{forb}(m,F)=\Theta(m^{X(F)}).

This conjecture predicts the precise polynomial order of the extremal function for every forbidden matrix other than the excluded two-row column. It is a central proposed framework for forbidden configuration problems, but the supplied source does not state whether it has been resolved in full.

References

Primary source

Attila Sali and Sam Spiro, “Forbidden Families of Minimal Quadratic and Cubic Configurations”, arXiv:1703.05602 (2017).

Additional references

3 papers in this index state this conjecture (2012–2017). The statement above is taken from the most recent of them; the others are arXiv:1307.1148, arXiv:1210.8189.

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.