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
Fulek: Forbidden Patterns in 0-1 Matrices - Exercise B
j B k k N
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Plasma_Vortex
268 posts
#1 • 2 Y
This topic is linked to Fulek: Forbidden Patterns in 0-1 Matrices - Exercise B.
Y by Adventure10, Mango247
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}
\]
This post has been edited 4 times. Last edited by Plasma_Vortex, Dec 23, 2015, 5:33 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
msinghal
725 posts
#2 • 9 Y
Y by devenware, dantx5, azmath333, whatshisbucket, bobacadodl, yrnsmurf, bstrauch24, Adventure10, Mango247
Construction
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awe-sum
154 posts
#3 • 2 Y
Y by Adventure10, Mango247
msinghal wrote:
Construction
Couldn't we expand this to the whole matrix and make the entire matrix 1, except every fourth column? that would work too wouldn't it?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
msinghal
725 posts
#4 • 4 Y
Y by devenware, yrnsmurf, Adventure10, Mango247
A submatrix is a matrix formed by deleting any set of rows and columns; the rows and columns that comprise a submatrix need not be consecutive. See https://proofwiki.org/wiki/Definition:Submatrix
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
somepersonoverhere
1313 posts
#5 • 2 Y
Y by Adventure10, Mango247
There's no construction greater than the minimal value $ex(n, L_1)$ can be?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathymath
64 posts
#6 • 1 Y
Y by Adventure10
msinghal wrote:
Construction

I think there is a larger maximum for $n  \ge 4$. We use this.
New Construction
This post has been edited 2 times. Last edited by mathymath, Dec 27, 2015, 5:52 PM
Reason: Edit typo
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathwizard888
1635 posts
#7 • 6 Y
Y by MSTang, msinghal, devenware, phi_ftw1618, liopoil, Adventure10
The rows and columns in a submatrix are not necessarily consecutive, so your construction does not work.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathymath
64 posts
#8 • 3 Y
Y by devenware, Adventure10, Mango247
Then that means there can't be more than two filled rows (the first and the last) and there can't be more than 3 columns completely filled right?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
whatshisbucket
975 posts
#9 • 4 Y
Y by devenware, msinghal, Adventure10, Mango247
Essentially yes. In order to create a matrix avoiding $L1$ or $L2$ with more than 5n-6 or 6n-8 ones, respectively, we will have to be more creative.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thkim1011
3135 posts
#10 • 2 Y
Y by Adventure10, Mango247
The upper bound can be improved slightly ( I think)
This post has been edited 3 times. Last edited by thkim1011, Dec 30, 2015, 9:13 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
talkon
276 posts
#11 • 2 Y
Y by kuerqing1024, Adventure10
Not a good way to do, but a computer search gives us $ex(5,L_1)<20$.

Therefore we have $ex(5,L_1)=19$

(Feel free to correct me if my code is wrong; I'm not very good at C)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
QuantumandMath
4 posts
#12 • 2 Y
Y by Adventure10, Mango247
looks like when n=4, solution is 14:
1 1 0 1
1 1 0 1 as only having one zero would allow
1 1 1 1 the submatrix not containing that zero to be used
1 1 1 1

n=5:
must have at least 3 zeroes for similar reasons.
20 solution
1 1 0 1 1
1 1 0 1 1
1 1 0 1 1
1 0 1 1 1
1 0 1 1 1
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
QuantumandMath
4 posts
#13 • 2 Y
Y by Adventure10, Mango247
also there are (n(n-1)(n-2)(n-3))/24*(n(n-1)(n-2))/6 submatrices. Each of these must have a zero somewhere on it's positions. that means that for a zero at (i,j), the submatrices with
first row i and second column j,
first row i and third column j,
second row i and first column j,
second row i and fourth column j,
first row i and second column j,
will be banned. This produces a upper bound on the number of subs banned, and this can be used to calculate an lower bound on the number of 0s.

as each coordinate bans an defined set of submatrices, this is a set cover problem, which happens to be NP hard, so more clever approaches that exploit the basic properties of these sets are needed. As each submatrix is banned by at most 5 positions, the minimum number of zeroes can be approximated to a multiple of 5 by this algorithm.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
whatshisbucket
975 posts
#14 • 2 Y
Y by devenware, Adventure10
That matrix is not valid, as the submatrix with the first three rows, and all columns except the third is completely filled, and this contains L1
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
VivekA
694 posts
#15 • 1 Y
Y by Adventure10
Does the problem mean that a copy of L1 cannot appear in the matrix?
Z K Y
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
No more topics!
H
J
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