The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2016: Pattern Avoidance

G
Topic
First Poster
Last Poster
Step 3 : Characterization
TropicalBlast   0
Aug 14, 2024
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?
0 replies
TropicalBlast
Aug 14, 2024
0 replies
alternative method for proving the Stanley-Wilf conjecture
JGeneson   3
N Jul 20, 2017 by yugrey
The Stanley-Wilf conjecture states that for any fixed permutation $\pi$ of $1, \ldots, k$, there exists a constant $c$ such that the number of permutations of $1, \ldots, n$ that avoid $\pi$ is at most $c^{n}$.

Furedi and Hajnal made another conjecture that implies the Stanley-Wilf conjecture: $ex(n, P) = O(n)$ for every permutation matrix $P$. CrowdMath problem 2 is to improve the bounds on $ex(n, P)$ for every permutation matrix $P$.

Klazar made another conjecture about partition avoidance that implies the Stanley-Wilf conjecture. We say that a partition $\sigma$ of $[n]$ contains a partition $\tau$ of $[k]$ if there exists a subpartition $\sigma'$ of $\sigma$ that has the same relative order as $\tau$. Klazar conjectured that if $\tau$ avoids $123$ and $12 / 34$, where $/$ denotes a separation between parts, then there exists a constant $c$ such that the number of partitions of $[n]$ avoiding $\tau$ is at most $c^{n}$.

http://kam.mff.cuni.cz/~klazar/cpfsp1.pdf page 4

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:

https://arxiv.org/pdf/1608.02279v1.pdf

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.
3 replies
JGeneson
Sep 8, 2016
yugrey
Jul 20, 2017
Question
Thothdragonfly2   5
N Feb 11, 2017 by Thothdragonfly2
For a matrix A to contain a pattern B, could we both find a submatrix of A and change 1 entries to 0 entries, or just one of the two?

I am new to this, so thanks!
5 replies
Thothdragonfly2
Feb 10, 2017
Thothdragonfly2
Feb 11, 2017
No more topics!
a