Step 3 : Characterization of P
Consider what kinds of patterns P would force the number of ones to be sparse.
Single ones: If P is a single 1 x 1 matrix with a single "1", ex(n, P) can be as large as n^2, since any placement of ones would avoid P trivially.
Row or column patterns: If P consists of a single row or a single column of ones then any n x n matrix with more than kn ones would necessarily contain a submatrix that matches P.
I am not sure whether this is method is correct? Can someone clarify?
alternative method for proving the Stanley-Wilf conjecture
JGeneson3
NJul 20, 2017
by yugrey
The Stanley-Wilf conjecture states that for any fixed permutation of , there exists a constant such that the number of permutations of that avoid is at most .
Furedi and Hajnal made another conjecture that implies the Stanley-Wilf conjecture: for every permutation matrix . CrowdMath problem 2 is to improve the bounds on for every permutation matrix .
Klazar made another conjecture about partition avoidance that implies the Stanley-Wilf conjecture. We say that a partition of contains a partition of if there exists a subpartition of that has the same relative order as . Klazar conjectured that if avoids and , where denotes a separation between parts, then there exists a constant such that the number of partitions of avoiding is at most .
Marcus and Tardos proved the Stanley-Wilf conjecture by proving the Furedi-Hajnal conjecture. Klazar's conjecture remains open, and was recently listed with several other conjectures in the paper below:
If you have ideas or questions about these papers or the conjectures, please post them here. A solution to Klazar's conjecture could imply improved bounds on the constants in the Stanley-Wilf conjecture.