Happy Thanksgiving! Please note that there are no classes November 25th-December 1st.

MIT PRIMES/Art of Problem Solving

CROWDMATH 2016: Pattern Avoidance

a
p
Pattern Avoidance J
Step 3 : Characterization
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TropicalBlast
1 post
#1
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?
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.
Z K Y
N Quick Reply
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
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
J
H
Problem 1 Important Results
iamgauss   25
N Jul 17, 2016 by JGeneson
As you may know, there is a thread for Problem 7 that lists all the important results discovered by CrowdMath for that problem. I thought it might be helpful to have a similar thread for the rest of the problems. Please add all important discoveries that have been made that are topical to Problem 1 here. Make sure to say where the theorems were proved and by whom. There are also threads for Problems 2-9. Thanks!
25 replies
iamgauss
Apr 29, 2016
JGeneson
Jul 17, 2016
J
H
CrowdMath Problem 1 Fulek's paper
JGeneson   23
N Jun 19, 2016 by JGeneson
There are 3 patterns $L_{3}, L_{4}, L_{5}$ at the end of Fulek’s paper.

http://dcg.epfl.ch/files/content/sites/dcg/files/users/former%20members/fulek/forbiddenPatterns.pdf

$ex(n, L_5) = O(n)$ was proved in http://www.sciencedirect.com/science/article/pii/S0097316509000466

It is still an open problem to show that $ex(n, L_3) = O(n)$ and $ex(n, L_4) = O(n)$.

The bar visibility graph method from Fulek’s paper was also used in a different paper to show linear bounds on the extremal functions of other 0-1 matrices:

http://arxiv.org/pdf/1410.3147v1.pdf

Can this method be used to bound the extremal functions of other patterns?
23 replies
JGeneson
Mar 1, 2016
JGeneson
Jun 19, 2016
J
No more topics!
H
J
H
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
J