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
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
No more topics!
a