Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2016: Pattern Avoidance

G
Topic
First Poster
Last Poster
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
No more topics!
a