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
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thothdragonfly2
616 posts
#1 • 2 Y
This topic is linked to Fulek: Forbidden Patterns in 0-1 Matrices.
Y by Adventure10, Mango247
For a matrix A to contain a pattern B, could we both find a submatrix of A and change 1 entries to 0 entries, or just one of the two?

I am new to this, so thanks!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
abk2015
3265 posts
#2 • 1 Y
Y by Adventure10
william122 wrote:
A 0-1 matrix is a matrix with its entries all equivalent to 0s or 1s, represented in this case by blanks and dots. To avoid a submatrix pattern is to not have a submatrix of our current matrix that is not equivalent to the submatrix pattern. (A submatrix is a matrix formed when certain columns and rows of a matrix are removed, thereby creating a new matrix.)
This post has been edited 1 time. Last edited by abk2015, Feb 10, 2017, 6:53 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thothdragonfly2
616 posts
#3 • 1 Y
Y by Adventure10
OK, but what about changing 1's to 0's?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
abk2015
3265 posts
#4 • 2 Y
Y by Adventure10, Mango247
See this transcript:
https://artofproblemsolving.com/school/mathjams-transcripts?id=408
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
abk2015
3265 posts
#5 • 2 Y
Y by Adventure10, Mango247
"We say that $A$ represents $B$ if either $A=B$ or $A$ can be turned into $B$ by changing some ones to zeroes."
This post has been edited 1 time. Last edited by abk2015, Feb 10, 2017, 7:34 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thothdragonfly2
616 posts
#6 • 2 Y
Y by Adventure10, Mango247
OK, I read the transcript and it answered my question completely! Thanks so much!
Z K Y
N Quick Reply
G
H
=
Page Feed | J
Linked Item Topics
G
Topic
First Poster
Last Poster
H
Fulek: Forbidden Patterns in 0-1 Matrices - Exercise B
Plasma_Vortex   72
N Feb 12, 2017 by Thothdragonfly2
What is the maximum number of ones in an $n\times n$ matrix avoiding $L1$?
\[
L1=\begin{pmatrix}
&\bullet&\bullet&\\
\bullet&&&\bullet\\
&\bullet&&
\end{pmatrix}
\]
72 replies
Plasma_Vortex
Dec 23, 2015
Thothdragonfly2
Feb 12, 2017
J
H
Question
Thothdragonfly2   5
N Feb 11, 2017 by Thothdragonfly2
For a matrix A to contain a pattern B, could we both find a submatrix of A and change 1 entries to 0 entries, or just one of the two?

I am new to this, so thanks!
5 replies
Thothdragonfly2
Feb 10, 2017
Thothdragonfly2
Feb 11, 2017
J
H
Maximum Number of Edges in a Bar Visibility Graphs
mssmath   12
N Apr 17, 2016 by JGeneson
What is the maximum number of edges in a Bar Visibility Graphs? (As a hint try to determine a method for counting edges that is "geometric in nature.")
12 replies
mssmath
Dec 23, 2015
JGeneson
Apr 17, 2016
J
H
Fulek: Forbidden Patterns in 0-1 Matrices - Exercise C
Plasma_Vortex   22
N Apr 17, 2016 by JGeneson
What is the maximum number of ones in an $n\times n$ matrix avoiding $L2$?
\[
L2=\begin{pmatrix}
&\bullet&\bullet&\bullet&\\
\bullet&&&&\bullet\\
&&\bullet&&
\end{pmatrix}
\]
22 replies
Plasma_Vortex
Dec 23, 2015
JGeneson
Apr 17, 2016
J
H
Proposition 1 of Fulek's paper
iamgauss   8
N Feb 23, 2016 by wlpj11
I am having trouble with R. Fulek's proof of Proposition 1 in his paper "Linear bound on extremal functions of some forbidden patterns in 0-1 matrices". I have reproduced this proof below.

Proposition 1: If $P = (p_{ij})$ is a k by l not-all-zero matrix then $ex(n, P) \ge n(k+l-2)-(k-1)(l-1)$.
Proof: We give the construction of a n by n matrix A that avoids pattern P with exactly $n(k+l-2)-(k-1)(l-1)$ 1 entries. Let $p_{l'k'}$ be some 1 entry in P. Note that P is not all zeros matrix.
Then A contains $(k-1)n$ 1 entries in the first $(k'-1)$ columns and in the last $(k-k')$ columns,
and additional $(n-k+1)(l-1)$ 1 entries in the first $(l'-1)$ rows and the last $(l-l')$ rows. Q.E.D.

I'm probably missing something obvious, but how does Fulek logically derive that "A contains $(k-1)n$ 1 entries in the first $(k'-1)$ columns and in the last $(k-k')$ columns,
and additional $(n-k+1)(l-1)$ 1 entries in the first $(l'-1)$ rows and the last $(l-l')$ rows" by letting $p_{l'k'}$ be a 1 value in P? I would appreciate it if somebody could help me understand his proof. Thank you!
8 replies
iamgauss
Dec 28, 2015
wlpj11
Feb 23, 2016
J
H
Other forbidden patterns
msinghal   4
N Dec 29, 2015 by thkim1011
I'm primarily interested in bounds for the maximum number of ones in an $n\times n$ matrix avoiding the following two patterns:

\[
L_6=\begin{pmatrix}
&&\bullet&\\
\bullet&&&\bullet\\
&\bullet&&
\end{pmatrix}
\qquad\qquad
L_7=\begin{pmatrix}
&\bullet&\bullet&\\
\bullet&&&\bullet\\
&\bullet&\bullet&
\end{pmatrix}
\]
4 replies
msinghal
Dec 24, 2015
thkim1011
Dec 29, 2015
J
No more topics!