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
i CrowdMath paper: pattern containment algorithms
JGeneson   1
N Apr 19, 2017 by JGeneson
Hi everyone,

Here is a draft of the third CrowdMath paper about algorithms for detecting pattern containment in 0-1 matrices. This paper was written by CrowdMath mentor Peter Tian.

If you see any typos, errors, improvements, or places where you can add a figure or more explanation, then please edit the tex file and post it in this thread. This paper will be open to edit until the end of March.

Anyone is welcome to edit this paper. If you edit it, then please edit the version attached to the most recent post in this thread.

Thank you very much for your help.
1 reply
JGeneson
Jan 22, 2017
JGeneson
Apr 19, 2017
i CrowdMath paper: pattern avoidance game
JGeneson   2
N Apr 19, 2017 by JGeneson
Hi everyone,

Here is a draft of the second CrowdMath paper about the pattern avoidance game in 0-1 matrices. This paper was written by CrowdMath mentor Ben Yang.

If you see any typos, errors, improvements, or places where you can add a figure or more explanation, then please edit the tex file and post it in this thread. This paper will be open to edit until the end of March.

Anyone is welcome to edit this paper. If you edit it, then please edit the version attached to the most recent post in this thread.

Thank you very much for your help.
2 replies
JGeneson
Jan 22, 2017
JGeneson
Apr 19, 2017
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