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.
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.
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?