On Unit Distances in a Convex Polygon

Amol Aggarwal
November 19, 2018
arXiv:1009.2216v3 [[Link]] 21 Oct 2014

Abstract
In 1959, Erdős and Moser asked for the maximum number of unit distances that may
occur among the vertices of a convex n-gon. Until now, the best known upper bound has been
2πn log2 n+O(n), achieved by Füredi in 1990. In this paper we examine two properties that any
convex polygon must satisfy and use them to prove several facts related to the above question.
In particular, we improve upon Füredi’s result, obtaining a bound of n log2 n+O(n); we exhibit
a new class of “cycles” formed by unit distances that are forbidden in convex polygons; and we
provide a lower bound that shows the limitations of our methods. The second result answers
a question of Fishburn and Reeds in the negative.

1 Introduction
1.1 Background
Let d(v, u) denote the Euclidean distance between any two points v and u in the plane. If d(v, u) = 1,
we say that v and u form a unit distance and we call the edge vu a unit distance. For any set of
points S in the plane, let U (S) denote the number of unit distances formed among the elements of
S. In 1946, Erdős asked for the value of U (n) = max U (S), where S ranges over all sets of n points
in the plane [4]. He conjectured that U (n) = o(n1+ε ) for any ε > 0 and proved that U (n) ≤ n3/2
using the fact that any two unit circles may have at most two points in common. In [11], Spencer,
Szemerédi and Trotter improved this bound to U (n) = O(n4/3 ).
In 1959, Erdős and Moser posed a variant of the original question. Identifying convex polygons
with their vertex sets, they asked for the value of Uc (n) = max U (P), where P ranges over all convex
n-gons in the plane [5]. They conjectured that Uc (n) = Θ(n) and showed that Uc (n) ≥ ⌊5(n−1)/3⌋.
In [3], Edelsbrunner and Hajnal improved the lower bound to Uc (n) ≥ 2n − 7. The upper bound
on Uc (n) was improved from O(n4/3 ) to 2πn log2 n + O(n) by Füredi, who used 0 − 1 matrices to
represent convex polygons [7].
Let us describe the relationship between 0 − 1 matrices and unit distances. Different authors
have done this in different ways; in what follows, we outline a variant of the method given by
Fishburn and Reeds in [6]. A real matrix is a matrix with real entries and a 0 − 1 matrix is a matrix
whose entries are either 0 or 1. Observe that a 0 − 1 matrix may be recovered from a real matrix
by replacing all entries not equal to 1 with 0; the resulting 0 − 1 matrix is called the skeleton of the
original matrix.
For any convex n-gon P = v1 v2 . . . vn , vertices listed in clockwise order, we say that two vertices
vi and vj (with 1 ≤ i < j ≤ n) are antipodal with respect to P if there exist parallel lines l1 through

1
vi and l2 through vj such that P is contained in the strip of the plane bounded by l1 and l2 . Taking
indices modulo n, consider the convex polygons P1 = vi vi+1 . . . vj−1 and P2 = vj vj+1 . . . vn+i−1 .
The partition P = P1 ∪ P2 is called an antipodal cut of P. We remark that Pach and Brass used
antipodal cuts in [2] to inductively prove that Uc (n) ≤ 9.65n log2 n.
Let a = j − i and b = n − a; relabel the vertices of P1 and P2 by setting uk = vi+k−1 for
1 ≤ k ≤ a and wk = vi−k for 1 ≤ k ≤ b. Consider the a × b distance matrix DP = DP,i,j whose
(r, c) entry is d(ur , wc ) for each (r, c) ∈ [1, a] × [1, b]. Let MP be the skeleton of DP ; we call MP
a 0 − 1 cut matrix associated with P. Let U (MP ) denote the number of entries in MP equal to 1;
then U (MP ) is equal to the number of unit distances uw with u ∈ P1 and w ∈ P2 . This implies
that U (P) = U (P1 ) + U (P2 ) + U (MP ). It may be shown (see Proposition 1 of Section 2) that
U (P1 ) + U (P2 ) ≤ 2n; thus, showing Uc (n) = Θ(n) amounts to proving U (MP ) = O(n).
Several authors have attempted to prove this upper bound through the use of forbidden matrices.
Let A = {ai,j } be an n1 × n2 real matrix; we call a k1 × k2 real matrix B = {bi,j } a submatrix
of A if there are integers 1 ≤ i1 < i2 < · · · < ik1 ≤ n1 and 1 ≤ j1 < j2 < · · · < jk2 ≤ n2 such
that br,c = air ,jc for each (r, c) ∈ [1, k1 ] × [1, k2 ]. Following Tardos in [12], we say that A contains
B if there exist integers i1 , i2 , . . . , ik1 and j1 , j2 , . . . , jk2 as above such that br,c = 1 implies that
air ,jc = 1 for each (r, c); otherwise A avoids B. We call a real matrix forbidden if any 0 − 1 cut
matrix avoids it. Examples of known (see [6]) forbidden matrices are shown below
   
  1 1 1 1
1 1
S2 = T 2 = ; G= 1 ; H =  1 
1 1
1 1 1 1
 
    1 1
1 1 1 1  1 
S3 =  1 1  ; T3 =  1 1 ; C =  
 1 
1 1 1 1
1 1
     
1 1 1 1 1 1
 1   1   1 
C1 =   ; C2 =   ; C3 =  ,
 1   1   1 
1 1 1 1 1 1

where the blank entries denote zeroes. We remark that Brass, Károlyi, and Valtr used the fact that
C is forbidden to show that Uc (n) ≤ 7n log2 n in [1].
Observe that S2 , S3 , and T3 are elements of a larger class of matrices known as staircase
matrices. For any integer n, let Sn = {si,j } denote the n × n 0 − 1 matrix satisfying sn,n = s1,n =
si,n−i = si+1,n−i = 1 for all integers 1 ≤ i ≤ n − 1 and si,j = 0 for all other i and j. For any integer
n, let Tn = {ti,j } denote the n × n 0 − 1 matrix satisfying t1,1 = tn,1 = ti,n−i+1 = ti+1,n−i+1 = 1
for all integers
S∞ 1 ≤ i ≤ n − 1 and ti,j = 0 for all other i and j. The set of staircase matrices is
the union i=2 {Si , Ti }. Following Fishburn and Reeds, we call a 0 − 1 matrix pattern feasible if it
avoids each of the nine matrices above as well as each staircase matrix; it may be shown that if a
0 − 1 matrix is not pattern feasible, then it is forbidden [6]. In the same paper Fishburn and Reeds
asked whether any pattern feasible matrix is in fact a 0 − 1 cut matrix.

1.2 Results
Our first result is an improvement upon Füredi’s bound on Uc (n) by a multiplicative factor of 2π;
we achieve this by combining various results about 0 − 1 matrices (see Sections 2.1 and 2.2).

2
Theorem 1. For each positive integer n, Uc (n) ≤ n log2 n + 4n.
Our next two results answer and generalize the question asked by Fishburn and Reeds. The novel
aspect of this paper that allows us to accomplish this is our analysis of the distance matrix, which
contains more refined information than does the 0 − 1 cut matrix. We will use two properties, which
we call the diagonal property and the obtuse angle property, in order to perform this analysis. Before
stating our remaining results, let us introduce these two properties and describe their relationship
with pattern feasible matrices.
A real matrix has the diagonal property if it has positive entries and has no 2 × 2 submatrix
M = {mi,j } satisfying m1,1 + m2,2 ≥ m1,2 + m2,1 . Proposition 2 of the next section states that any
distance matrix has the diagonal property.
For any 2 ≤ d, e ≤ 4, a d × e real matrix M = {mi,j } is called an acute angle matrix if there
are integers r1 , ∈ [2, d], c1 ∈ [2, e], r2 ∈ [1, d − 1], and c2 ∈ [1, e − 1] such that m1,1 ≥ m1,c1 , mr1 ,1
and md,e ≥ mr2 ,e , md,c2 . For instance, any real matrix whose skeleton is one of the matrices
{S2 , G, H, C, C1 , C2 , C3 } from Section 1.1 is an acute angle matrix; however, neither S3 nor T3 is
an acute angle matrix. A matrix with positive entries that has no acute angle submatrix is said to
have the obtuse angle property; Proposition 3 of the next section states that any distance matrix
has the obtuse angle property.
We remark that the diagonal property has been used by Pach and Tardos in [10] to obtain
another proof of the bound U (n) = O(n4/3 ). Some specific cases of the obtuse angle property have
also been discussed in previous works such as [1] and [6]. However, we have not seen it used in
generality until now.
A real matrix that has both the diagonal property and the obtuse angle property is called a
distance-like matrix; any distance matrix is distance-like. One may verify that any distance-like
matrix has a pattern feasible skeleton. However, there exists a pattern feasible matrix that is not
the skeleton of any distance-like matrix. Let us describe a class of real matrices that contains such
an element.
Suppose that k1 and k2 are integers greater than 1. A k1 × k2 real matrix M = {mi,j } is a
cycle with an intersection-free edge if there exist positive integers r1 = 1; r2 , . . . , rl 6= 1 less than or
equal to k1 and c1 = 1; c2 , . . . , cl 6= 1 less than or equal to k2 such that ri 6= ri+1 and ci 6= ci+1 for
each 1 ≤ i ≤ l − 1 and such that mri ,ci = 1 = mri ,ci+1 for each 1 ≤ i ≤ l, where indices are taken
modulo l. For instance, the staircase matrix Tk is a cycle with an intersection-free edge for any
integer k ≥ 2. Moreover, any real matrix whose skeleton is the pattern feasible matrix E below is
a cycle with an intersection-free edge.
 
1 1
 1 1 
E= 
 1 1 
1 1
We have the following result on cycles with an intersection-free edge.
Theorem 2. No cycle with an intersection-free edge is a distance-like matrix.
In particular, Theorem 2 implies that there is no distance-like matrix whose skeleton is E; thus
the pattern feasible matrix E is not a 0−1 cut matrix. This yields a negative answer to the question
posed by Fishburn and Reeds.
Our final result shows the limitations of the diagonal and obtuse angle properties; they alone
will not suffice to obtain Uc (n) = Θ(n).

3
Theorem 3. For any positive integer m, there exists a 2m ×2m distance-like matrix with 2m−1 (m+
1) entries equal to 1.

2 Proofs of Theorems 1, 2, and 3

2.1 Preliminary Facts
In this subsection we collect several facts that will be used later in the article. The first fact is
about antipodal cuts and is due to Brass and Pach [2].
Proposition 1. Let P be a convex n-gon and let the partition P = P1 ∪ P2 be an antipodal cut.
Then U (P1 ) + U (P2 ) ≤ 2n.
The next two facts together show that any distance matrix is distance-like. A proof of Proposition 2
is given in [10], and a special case of Proposition 3 is used in [1].
Proposition 2. Any distance matrix satisfies the diagonal property.
Proposition 3. Any distance matrix satisfies the obtuse angle property.
Proof. Suppose to the contrary that there exist convex polygons P, P1 = u1 u2 . . . ua , and P2 =
w1 w2 . . . wb such that the partition P = P1 ∪ P2 is an antipodal cut and such that the distance
matrix DP associated with this cut does not have the obtuse angle property. By replacing it
with one of its acute angle submatrices if necessary, we will assume that DP is an acute angle
matrix. Then there exist integers r1 ∈ [2, a], c1 ∈ [2, b], r2 ∈ [1, a − 1], and c2 ∈ [1, b − 1] such that
d(u1 , w1 ) ≥ d(ur1 , w1 ), d(u1 , wc1 ) and d(ua , wb ) ≥ d(ur2 , wb ), d(ua , wc2 ). The first inequality implies
that ∠w1 u1 ur1 ≤ ∠w1 ur1 u1 , so ∠w1 u1 ua ≤ ∠w1 u1 ur1 < π/2. All other angles of the quadrilateral
w1 u1 ua wb are acute by similar reasoning; this is a contradiction.
The next two facts are about 0 − 1 matrices. Before stating these facts, let us define some
relevant terminology. For positive integers a and b and a 0 − 1 matrix M, let ex(a, b, M) denote
the maximum number of entries equal to 1 in an a × b 0 − 1 matrix avoiding M.
For an r1 × c1 0 − 1 matrix M = {mi,j } whose bottom-right entry equals 1 and an r2 × c2
0 − 1 matrix N = {ni,j } whose top-left entry is equal to 1, define the amalgam of M and N to
be the (r1 + r2 − 1) × (c1 + c2 − 1) 0 − 1 matrix L = {li,j } formed by attaching the bottom-right
corner of M to the top-left corner of N. Specifically, set li,j = mi,j for all (i, j) ∈ [1, r1 ] × [1, c1 ];
li,j = ni−r1 +1,j−c1 +1 for all (i, j) ∈ [r1 , r1 + r2 − 1] × [c1 , c1 + c2 − 1]; and all other li,j = 0. The
following two lemmas are due to Keszegh [8, 9] and Tardos [12], respectively.
Lemma 1. Let M and N be 0 − 1 matrices whose amalgam exists and is equal to L. For all positive
integers a and b, ex(a, b, L) ≤ ex(a, b, M) + ex(a, b, N).
Lemma 2. Let
 
1 1  
1 1
A= 1 ; B= .
1 1
1

For all positive integers a and b, ex(a, b, A) ≤ ( a+b a+b

2 ) log2 (a + b) + 2b and ex(a, b, B) ≤ ( 2 ) log2 (a +
b) + 2a.

4
2.2 Proof of Theorem 1
Let P be a convex n-gon and let MP be a 0 − 1 cut matrix associated with P; suppose that MP
has a rows and b columns. Define the 0 − 1 matrices
 
  1 1
1 1  
; B = 1 1  1
; C′ = 

A= 1 .
1 1  1 1 
1
1 1

Since no real matrix containing C′ has the obtuse angle property, Proposition 3 implies that MP
avoids C′ . Hence, U (MP ) ≤ ex(a, b, C′ ) ≤ ex(a, b, A) + ex(a, b, B) by Lemma 1. By Lemma 2 and
the fact that a + b = n, this quantity is at most n log2 n + 2n. It follows from Proposition 1 that
U (P) ≤ 2n + U (MP ) ≤ n log2 n + 4n.

2.3 Proof of Theorem 2

Suppose that M = {mi,j } is an n1 × n2 cycle with an intersection-free edge. Then there exist
integers r1 = 1; r2 , r3 , . . . , rl 6= 1 and c1 = 1; c2 , c3 , . . . , cl 6= 1 such that ri 6= ri+1 , ci 6= ci+1 , and
mri ,ci = 1 = mri ,ci+1 for each 1 ≤ i ≤ l, where indices are taken modulo l. We will deduce that M
is not distance-like by showing that M does not have the obtuse angle property; hence it suffices
to find an acute angle submatrix of M.
Let s be the minimal integer greater than 1 such that m1,s ≤ 1. The minimality of s implies that
c2 ≥ s. Let j ∈ [2, l] be the minimal integer satisfying cj+1 < s ≤ cj ; since cl+1 = c1 = 1 < s ≤ c2 ,
such a j exists. Moreover, let h be the largest integer in [1, j − 1] such that rh+1 > rh and let k be
the largest integer in [1, j − 1] such that ck+1 > ck . The acute angle submatrix we find will depend
on whether k ≤ h or h < k.
Suppose first that k ≤ h. The maximality of h implies that rh+1 ≥ rj ; the maximality of k and
the fact that k ≤ h implies that ch+1 > ch+2 and that ch+1 ≥ cj ≥ s. The minimality of j then yields
ch+2 ≥ cj+1 . Thus intersecting the first, rj th, rh th, and rh+1 st rows with the cj+1 st, sth, ch+2 nd,
and ch+1 st columns yields an acute angle submatrix of M because m1,cj+1 ≥ 1 ≥ m1,s , mrj ,cj+1 and
mrh+1 ,ch+1 = 1 = mrh ,ch+1 , mrh+1 ,ch+2 .
If h < k holds instead, then intersecting the first, rj th, rk+1 st, and rk th rows with the cj+1 st,
sth, ck th, and ck+1 st columns yields an acute angle submatrix by similar reasoning. Thus in either
case, M has an acute angle submatrix and hence cannot be distance-like.

2.4 Proof of Theorem 3

We will create this distance-like matrix through a recursion. For each positive integer m, define the
m
2m × 2m matrix Xm = {xm,i,j } to satisfy xm,i,j = 0 if i + j = 2m + 1; xm,i,j = i + (2m+j − i)2 5−10 if
m
i + j > 2m + 1; and xm,i,j = −210 −2i−2j otherwise. Also define the 2m × 2m matrix Ym = {ym,i,j }
m
to satisfy ym,i,j = −510 ij for all integers 1 ≤ i, j ≤ 2m . Recursively define the 2m × 2m matrices
Zm = {zm,i,j } through the relations
r
10−1000 Zr−1
   
1/4 0 r Xr−1
Z1 = ; Zr = 10−1000 r
0 −1/2 10−1000 Zr−1 Yr−1

5
for all integers r ≥ 2. For each positive integer m, let Dm denote the 2m × 2m matrix formed by
adding 1 to each entry of Zm . We claim that Dm satisfies the conditions of Theorem 3.
By induction on m, one can see that the magnitude of each entry in Zm is less than 1 for each
positive integer m. Hence each entry of Dm is positive. Furthermore, there are 2r−1 entries equal
to 0 in Xr−1 and no such entries in Yr−1 for each integer r ≥ 2; induction on m then yields that
there are 2m−1 (m + 1) entries equal to 0 in Zm . Therefore, there are 2m−1 (m + 1) entries equal to
1 in Dm .
It remains to show that Dm has the obtuse angle property and the diagonal property for each
positive integer m. Let us first verify the obtuse angle property; it suffices to check that Zm contains
no acute angle submatrix. Suppose this is false, and let s ≥ 2 be the minimal positive integer such
that Zs has an acute angle submatrix. Then there exist integers i1 , i2 , i3 , i4 , j1 , j2 , j3 , j4 ∈ [1, 2s ]
such that i2 ∈ [i1 + 1, i4 ]; j2 ∈ [j1 + 1, j4 ]; i3 ∈ [i1 , i4 − 1]; j3 ∈ [j1 , j4 − 1]; zs,i1 ,j1 ≥ zs,i2 ,j1 , zs,i1 ,j2 ;
and zs,i4 ,j4 ≥ zs,i3 ,j4 , zs,i4 ,j3 . Observe that the entries of Ys−1 decrease from top to bottom in
any fixed column, decrease from left to right in any fixed row, and are less than zs,i,j for any
(i, j) ∈ / [2s−1 + 1, 2s ] × [2s−1 + 1, 2s ]. This implies that (i4 , j4 ) ∈ / [2s−1 + 1, 2s ] × [2s−1 + 1, 2s ] and
s−1
thus that either i4 ≤ 2 or j4 ≤ 2 . We will only consider the case i4 ≤ 2s−1 because the
s−1

reasoning for the case j4 ≤ 2s−1 is similar. It follows that j1 ≤ 2s−1 or else Zs−1 would contain an
acute angle matrix, contradicting the minimality of s; therefore, (i1 , j1 ), (i2 , j1 ) ∈ [1, 2s−1 ]×[1, 2s−1 ].
However, the entries of any fixed column of Xs−1 are increasing from top to bottom; this implies
that zs,i1 ,j1 < zs,i2 ,j1 , which is a contradiction. Thus Zm has no acute angle submatrix for all
positive integers m, so Dm has the obtuse angle property.
Next, suppose that there exists some positive integer m such that Dm does not satisfy the
diagonal property; let s ≥ 2 be the minimal such integer. Then there exist integers i1 , j1 , i2 , j2 ∈
[1, 2s ] with i1 < i2 and j1 < j2 such that zs,i1 ,j1 + zs,i2 ,j2 ≥ zs,i2 ,j1 + zs,i1 ,j2 . First suppose that
j2 ≤ 2s−1 and i2 > 2s−1 both hold. If we moreover had that i1 > 2s−1 , then the entries zs,i1 ,j1 ,
s
zs,i2 ,j2 , zs,i2 ,j1 , and zs,i1 ,j2 would lie in the bottom-left 2s−1 ×2s−1 corner of Zs . Then 10−1000 Zs−1
would not satisfy the diagonal property, which contradicts the minimality of s; hence i1 ≤ 2s−1 .
Now, the difference between any two unequal entries of Xs−1 has magnitude greater than the
s
difference between any two entries of 10−1000 Zs−1 . Since the entries of Xs−1 are increasing from
left to right in any fixed row, this yields that zs,i1 ,j2 − zs,i1 ,j1 = |zs,i1 ,j2 − zs,i1 ,j1 | > zs,i2 ,j2 − zs,i2 ,j1 .
This is a contradiction, which implies that either j2 > 2s−1 or i2 ≤ 2s−1 . By similar reasoning, one
may show that either j2 ≤ 2s−1 or i2 > 2s−1 . It follows that zs,i2 j2 is contained either in the top
left 2s−1 × 2s−1 corner of Zs , which is a copy of Xs−1 , or in the bottom right 2s−1 × 2s−1 corner of
Zs , which is a copy of Ys−1 . By similar reasoning, one may deduce the same statement for zs,i1 ,j1 .
Observe that any entry of Ys−1 is negative and has magnitude greater than 3 times the mag-
nitude of any entry of Xs−1 ; furthermore, any entry of Xs−1 has greater magnitude than any
s
entry of 10−1000 Zs−1 . Hence if zs,i1 ,j1 is in Xs−1 and zs,i2 ,j2 is in Ys−1 , then zs,i1 ,j1 + zs,i2 ,j2 <
−2|zs,i1 ,j1 | < −|zs,i2 ,j1 | − |zs,i1 ,j2 | ≤ zs,i2 ,j1 + zs,i1 ,j2 , which is a contradiction. Thus the entries
zs,i1 ,j1 , zs,i2 ,j2 , zs,i2 ,j1 , and zs,i1 ,j2 are either all in Xs−1 or all in Ys−1 .
The inequality i1 j1 + i2 j2 > i1 j2 + i2 j1 implies that the latter case is impossible, so all four
entries are in Xs−1 . If i1 + j1 < 2s−1 + 1, then zs,i1 ,j1 is negative and one may show that
|zs,i1 ,j1 |/3 > |zs,i2 ,j2 |, |zs,i1 ,j2 |, |zs,i2 ,j1 |. This implies that zs,i1 ,j1 < −|zs,i1 ,j2 | − |zs,i2 ,j1 | − |zs,i2 ,j2 | ≤
r
zs,i2 ,j1 + zs,i1 ,j2 − zs,i2 ,j2 , which is a contradiction. If i1 + j1 = 2s−1 + 1, then 101000 (zs,i1 ,j2 −
1000r s−1
zs,i1 ,j1 ) ≥ 1 > 10 (zs,i2 ,j2 − zs,i2 ,j1 ), which is a contradiction. Hence i1 + j1 > 2 + 1, so
the inequality (2s+j1 −1 − i1 )2 + (2s+j2 −1 − i2 )2 < (2s+j1 −1 − i2 )2 + (2s+j2 −1 − i1 )2 implies that
zs,i1 ,j1 + zs,i2 ,j2 < zs,i1 ,j2 + zs,i2 ,j1 . This is again a contradiction, which implies that Dm has the

6
diagonal property and is thus distance-like.

We conclude this article by asking whether there exists a distance-like matrix whose skeleton
is forbidden. In view of Theorem 3, a negative answer implies the existence of a counterexample
to the conjecture that Uc (n) = Θ(n). On the other hand, a positive answer may lead to a better
understanding of unit distances between vertices of a convex polygon.

3 Acknowledgements
The author heartily thanks János Pach for his guidance; Joseph O’Rourke for his suggestions on
publication; and Alok Aggarwal, Balázs Keszegh, Jacob Fox, Andrew Suk, and the referees for their
valuable suggestions.

References
[1] P. Brass, G. Károlyi, and P. Valtr, A Turán-type extremal theory of convex geometric graphs,
The Goodman-Pollack Festschrift, (2003), 275–300.
[2] P. Brass and J. Pach, The maximum number of times the same distance can occur among the
vertices of a convex n-gon is O(n log n), J. Combin. Theory Ser. A, 94 (2001), 178–179.

[3] H. Edelsbrunner and P. Hajnal, A lower bound on the number of unit distances between the
vertices of a convex polygon, J. Combin. Theory Ser. A, 56 (1991), 312–316.
[4] P. Erdős, On sets of distances of n points, Amer. Math. Monthly, 53 (1946), 248–250.
[5] P. Erdős and L. Moser, Problem 11, Canadian Math. Bulletin, 2 (1959), 43.
[6] P. C. Fishburn and J. A. Reeds, Unit distances between vertices of a convex polygon, Compu-
tational Geometry: Theory and Applications, 2 (1992), 81–91.
[7] Z. Füredi, The maximum number of unit distances in a convex n-gon, J. Combin. Theory Ser.
A, 55 (1990), 316–320.
[8] B. Keszegh, Forbidden submatrices in 0 − 1 matrices, Master’s thesis, Eötvös Loránd University,
(2005).
[9] B. Keszegh, On linear forbidden submatrices, J. Combin. Theory Ser. A, 116 (2009), 232–241.
[10] J. Pach and G. Tardos, Forbidden paths and cycles in ordered graphs and matrices, Israel J.
Math., 155 (2006), 359–380.
[11] J. Spencer, E. Szemerédi, and W. T. Trotter, Unit Distances in the Euclidean Plane, in: Graph
Theory and Combinatorics (B. Bollobás, ed.), Academic Press, New York, 1984, 293–303.
[12] G. Tardos, On 0-1 matrices and small excluded submatrices, J. Combin. Theory Ser. A, 111
(2005), 266–288.