MIT PRIMES/Art of Problem Solving
CROWDMATH 2016: Pattern Avoidance
Pattern Avoidance
CrowdMath project forum
CrowdMath project forum
3
M
G
BBookmark
VNew Topic
kLocked
Pattern Avoidance
CrowdMath project forum
CrowdMath project forum
3
M
G
BBookmark
VNew Topic
kLocked
No tags match your search
MProblem 2
matrix
linear algebra
Problem 3
Marcus - Excluded Permutation Matrices
Fulek: Forbidden Patterns in 0-1 Matrices
Problem 1
extremal functions
function
Keszegh - Forbidden Submatrices
Guth - Joints Problem
Problem 2
crowdmath
H. Cohn et al. - D_4 Not Optimal
H. Cohn et al. - D_4 Not Optimal - null
Problem 7
Klazar, Marcus - Füredi-Hajnal conjecture
Klazar, Marcus - Füredi-Hajnal conjecture - null
Problem 8
Problem 9
Fox - Typically Exponential Limits
geometry
inequalities
mitprimes
pattern avoidance
Sequences
Weidert - Extremal Problems
algorithms
Fulek: Forbidden Patterns in 0-1 Matrices - Exercise A
Marcus - Excluded Permutation Matrices - Exercise B
pattern
pigeonhole principle
polymath
polynomial
Problem 4
0-1 swap
algebra
algorithm
AM-GM
avoidance
Binary
calculus
combinatorics
crowdmath 2017
data points
Dimensions
Foundation mathematics
Fox - Typically Exponential Limits - Exercise A
Fulek Forbidden Patterns in 0-1 Matrices
Fulek: Forbidden Patterns in 0-1 Matrices - Exercise B
Fulek: Forbidden Patterns in 0-1 Matrices - Exercise C
No tags match your search
MG
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.
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
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.
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
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 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 .
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.
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 .
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
No more topics!