Minimal Non-linear Patterns and Linear Extremal Function of Forbidden Submatrices
Consider a 0-1 matrix A and another 0-1 matrix P. After deleting certain rows and columns in A, we get A'. If every 1 entry in P corresponds to a 1 entry in A' at the same position, we say that matrix A contains matrix P. If A does not contain P, we say A avoids P. Normally, we call P the forbidden pattern. The number of 1 entries in a matrix is the weight of the matrix. We define ex(n, P) as the maximum weight of an n by n matrix, that is, the maximum number of 1 entries, when this matrix avoids P. We say ex(n, P) is an extremal function. When ex(n,P) = O(n), it is linear. The minimal non-linear pattern refers to removing any 1 entry in this pattern, and the extremal function of the new matrix obtained is linear. In the article by Keszegh, he found the first smallest nonlinear pattern with a weight greater than 4. He proposed three conjectures in the fourth chapter. Conjecture 1 is that ex(n,Gk) = O(n) (k is greater than or equal to 0) for a certain pattern Gk. In conjecture 2, he claims that there are infinitely many minimal non-linear patterns, and a certain pattern Hk is such a pattern. Conjecture 3 is about the extremal functions in permutation matrices, which is proved by Geneson. This thesis will first explain some basic concepts, and then prove conjecture 3 by expanding and illustrating some lemmas in Geneson. Additionally, we prove conjecture 1 by using conjecture 3. Finally, for conjecture 2, we prove the existence of infinitely many minimal non-linear patterns, if Hk is such a pattern remains an open problem.