This topic is linked to Problem 1.
Y by
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?
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?
This post has been edited 1 time. Last edited by TropicalBlast, Aug 14, 2024, 6:11 PM
Reason: not sure whether the method used is correct.
Reason: not sure whether the method used is correct.