Anstee–Sali conjecture on forbidden configuration growth

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 FA1×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.

Sources & referencesView supporting material

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.