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
is a k by l not-all-zero matrix then
.
Proof: We give the construction of a n by n matrix A that avoids pattern P with exactly
1 entries. Let
be some 1 entry in P. Note that P is not all zeros matrix.
Then A contains
1 entries in the first
columns and in the last
columns,
and additional
1 entries in the first
rows and the last
rows. Q.E.D.
I'm probably missing something obvious, but how does Fulek logically derive that "A contains
1 entries in the first
columns and in the last
columns,
and additional
1 entries in the first
rows and the last
rows" by letting
be a 1 value in P? I would appreciate it if somebody could help me understand his proof. Thank you!