← All problems

Anstee–Sali conjecture on forbidden configuration growth

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

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.

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

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.