# Noncrossing Monochromatic Subtrees and Staircases in 0-1 Matrices

Authors: Siyuan Cai; Gillian Grindstaff; András Gyárfás; Warren Shull
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

The following question is asked by the senior author (Gyárfás (2011)). What is the order of the largest monochromatic noncrossing subtree (caterpillar) that exists in every 2-coloring of the edges of a simple geometricKn,n? We solve one particular problem asked by Gyárfás (2011):  separate the Ramsey number of noncrossing trees from the Ramsey number of noncrossing double stars. We also reformulate the question as a Ramsey-type problem for 0-1 matrices and pose the following conjecture. Every n×n 0-1 matrix contains n−1 zeros or n−1 ones, forming a staircase: a sequence which goes right in rows and down in columns, possibly skipping elements, but not at turning points. We prove this conjecture in some special cases and put forward some related problems as well.


---

## Body

## 1. Introduction

Ageometric graph (see [1]) is a graph whose vertices are in the plane in general position and whose edges are straight-line segments joining the vertices. A subgraph of a geometric graph is noncrossing if no two edges have a common interior point. A geometric bipartite graphG(n,n) is a geometric graph, whose 2n vertices are in two disjoint n-element sets A and B, and its edges are some segments ab with a∈A and b∈B. The following representation, apparently studied first in [2], seems to be a more natural subclass of balanced geometric bipartite graphs G(n,n) (in fact a standard way of drawing bipartite graphs). The partite sets of G in R2 are A={a1=(1,0),a2=(2,0),…,an=(n,0)} and B={b1=(1,1),b2=(2,1),…,bn=(n,1)} and the edge aibj is the line segment joining ai∈A and bj∈B. This representation is called a simpleG(n,n).Analogues of Turán and Ramsey theories have been considered for geometric graphs, see; [1, 3–9] and its references. Our starting point is the following Ramsey-type problem for simple G(n,n)-s.Problem 1 (see [5]).
Findf(n), the order of the largest monochromatic noncrossing subtree that exists in every 2-coloring of the edges of a simple geometric Kn,n. The lower bound is 4n/5 and the upper bound is n for even and n+1 for odd n.Noncrossing subgraphs of simpleG(n,n)-s can be easily characterized.Proposition 2 (see [10]).
Every connected component of a noncrossing subgraph of simpleG(n,n) is a caterpillar (a tree in which the vertices of degree larger than one form a path).In fact, the lower bound4n/5≤f(n) is proved in a stronger form.Theorem 3 (see [5]).
In every2-coloring of the simple Kn,n there is a noncrossing monochromatic double star with at least 4n/5 vertices. This bound is asymptotically best possible.Since Theorem3 is asymptotically sharp, it was asked in [5] whether one can separate f(n) and 4n/5. Here, we answer this question positively, although with a small margin.Theorem 4.
Consider(4/5+ε)n≤f(n), where ε=1/880.We give a new construction showing that the upper bound in Problem1 can be decreased by one when n is odd.Proposition 5.
Considerf(n)≤n for n≥2.Theorem3 and Proposition 5 show that the noncrossing condition is important because it is easy to see that for odd n there is a monochromatic tree of order n+1 in every 2-coloring of the edges of Kn,n. We suspect that the bound of Proposition 5 is best possible and risk the following conjecture.Conjecture 6.
For everyn≥2, f(n)=n.We also reformulate Conjecture6 (and Problem 1) into a more attractive (and perhaps more inspiring) form. Let A be an n×n 0-1 matrix. A 0-staircase is a sequence of zeroes in A which goes right in rows and down in columns, possibly skipping elements, but zero at each turning point. A 1-staircase is defined similarly on ones of A. A homogeneous staircase in A is either a 0- or a 1-staircase. The length of a homogeneous staircase is the number of elements in it. Let st(A) be the maximum among the lengths of the homogeneous staircases of A. Finally, set
(1)st(n)=min⁡{st(A):Aisann×n0-1matrix}.
An example with n=7 is the matrix A below where a 1-staircase of length 6 is shown:
(2)1010011010111010101010101100101011001011001011001One can easily computest(A) for any n×n matrix with the following procedure. We define an n×n matrix B=[bi,j], the staircase matrix ofA, where bi,j is the length of the longest homogeneous staircase of A ending in position (i,j). The matrix B can be easily computed recursively from A, following a linear order of the elements of B, such that bi,j comes after all elements of L(i,j)={bi,l:1≤l<j,ai,l=ai,j} and also after all elements of U(i,j)={bk,j:1≤k<i,ak,j=ai,j}. Note that L(i,1)=U(1,j)=∅ for all i and j. A natural linear order with this property can be defined by taking the first row left to right then the first column downwards starting at b2,1 and repeating this for the remaining (n-1)×(n-1) matrix. Under this linear ordering, we define inductively
(3)bi,j=1+max⁡{max⁡L(i,j),max⁡U(i,j)},
where the maximum of the empty set is defined to be zero; for example,
(4)b1,1=1+max⁡{max⁡L(1,1),max⁡U(1,1)}=1+max⁡{max⁡∅,max⁡∅}=1+max⁡{0,0}=1.
With the example matrix A, we get the following staircase matrix B, showing that st(A)=8 and providing an easy way to trace back the 0-staircase of length 8 in A ending at a6,7. The 0-values are shown in bold:
(5)1122334112234322334452233556334467733447684456577The following easy but important observation shows that the Ramsey-type problems for noncrossing subtrees in simple geometricKn,n and for staircases in n×n 0-1 matrices are the same problems in different formulations.Theorem 7.
Considerst(n)=f(n)-1.Proof.
A2-coloring of the edges of a simple geometric Kn,n can be considered as an n×n 0-1 matrix where the element in row i and column j is zero or one according to the color of the edge aibj. By Proposition 2, every noncrossing monochromatic subtree is a caterpillar. The edges of the base path of the caterpillar correspond to turning points of a homogeneous staircase and the pending edges of the caterpillar correspond to elements in the same row or column between consecutive turning points (except at the beginning and the end). Thus, a monochromatic noncrossing subtree on m vertices (m-1 edges) corresponds to a homogeneous staircase of length m-1. The correspondence works backward as well, proving the theorem.Theorem7 allows to put forward Conjecture 6 in a more challenging form.Conjecture 8.
Everyn×n 0-1 matrix has a homogeneous staircase of size n-1.Another advantage of the staircase formulation is that it gives “a proof without words” to Proposition5. Indeed, let A be the n×n matrix with ai,j=1 if i+j≤n or i=j=n and zero otherwise (see below for n=7):
(6)1111110111110011110001110000110000010000000000001
One can immediately see that the longest homogeneous staircase of A has n-1 elements, proving Proposition 5.We have the following propositions supporting Conjecture8 for various special matrices.Proposition 9.
Assumea1,1=an,n=0 for the n×n matrix A=[ai,j] and there is no 0-staircase from a1,1 to an,n. Then there is a 1-staircase of size at least n-1.The next proposition settles Conjecture8 for four of the 16 corner configurations of the lower left 2×2 submatrix of A.Proposition 10.
Suppose that then×n matrix A=[ai,j] satisfies an,1≠an,2 and an,1≠an-1,1. Then st(A)≥n-1.The next special case is when there are two consecutive columns whose binary sum is the all 1 vector (switching columns).Proposition 11.
Suppose thatA=[ai,j] is an n×n 0-1 matrix with switching columns; that is, there exists 1≤j<n such that for every 1≤k≤n, one has ak,j≠ak,j+1. Then st(A)≥n-1.Finally, we prove Conjecture8 for n=8 and note that its proof method still works for n=9 but would be much longer. On the other hand, the cases where n<8 are obvious and left to the reader.Proposition 12.
Every8×8 0-1 matrix has a monochromatic staircase of length at least 7.These propositions will be proved in Section2, and Theorem 4 is proved in Section 3.


## 2. Proofs of Special Cases of Conjecture6

Proof of Proposition9.
First, observe thata1,n=an,1=1, because otherwise there exists a 0-staircase connecting a1,1 to an,n. Suppose there are a,  b,  c,  d zeroes in the first row, first column, last row, and last column, respectively. A zero from the first row and a zero from the last row cannot share the same column, because otherwise a 0-staircase connecting a1,1 and an,n would be present. Therefore, a+c≤n; similarly b+d≤n. Since a1,n=1, the ones in the first row and in the last column form a 1-staircase of length (n-a)+(n-d)-1=2n-a-d-1. In the same way, there is a 1-staircase consisting of all ones in the first column and in the last row, of length 2n-b-c-1. The two lengths add up to (2n-a-d-1)+(2n-b-c-1)=4n-(a+c)-(b+d)-2≥2n-2, so at least one of them must be at least n-1.Proof of Proposition10.
Without loss of generality, assumean,1=0, an-1,1=an,2=1. Consider two cases as follows.
Case  1.
a
n
-
1,2
=
0. Define a to be the number of zeroes in column 1, b to be the number of zeroes in column 2, c to be the number of zeroes in row n-1, and d to be the number of zeroes in row n. The following homogeneous staircases therefore exist:(i)
the0-staircase in column 1 and row n, turning at an,1 with length a+d-1;(ii)
the0-staircase in column 2 and row n-1, turning at an-1,2 with length b+c-1;(iii)
the1-staircase in column 1 and row n-1, turning at an-1,1 with length (n-a-2)+(n-c-2)+1;(iv)
the1-staircase in column 2 and row n, turning at an,2 with length (n-b-2)+(n-d-2)+1. The sum of lengths of these four staircases is
(7)a+d-1+b+c-1+(n-a-1)+(n-c-1)+1+(n-b-1)+(n-d-1)+1=4n-4,
so their average length is n-1; thus at least one of them must have length n-1 or more.
Case  2.
a
n
-
1,2
=
1. Define a to be the number of zeroes in column 1 and b to be the number of zeroes in row n. The following homogeneous staircases therefore exist:(i)
the0-staircase in column 1 and row n, turning at an,1 with length a+b-1;(ii)
The1-staircase in column 1 and row n, an-1,2, turning at an-1,1,an-1,2,an,2 with length (n-a-2)+3(n-b-2).The sum of lengths of these two staircases is 2n-2 so at least one of them must have length n-1 or more.Proof of Proposition11.
Assume columnsj,  j+1 are switching columns. Let r and s be the smallest and largest values of i for which ai,j=0, and likewise let p and q are the smallest and largest values of i for which ai,j=1. We may assume r,s,p and q all exist and are different, otherwise, column j contains at most one 1 or at most one 0 and the proof is finished.
Definea to be the number of zeroes to the left of ar,j in row r, so there are j-1-a ones there. Define c to be the number of zeroes to the right of as,j+1 in row s, so there are n-j-1-c ones there.
Defined to be the number of ones to the left of ap,j in row p, so there are j-1-d zeroes there. Define e to be the number of ones to the right of q,j+1 in row q, so there are n-j-1-e zeroes there.
Definef to be the number of zeroes in column j, so there are n-f ones in column j, and there are n-f zeroes and f ones in column j+1.
The0-staircase in row r, column j, and row s, which turns at (r,j) and (s,j), contains a+f+c zeroes.
The1-staircase in row r, column j+1, and row s, which turns at (r,j+1) and (s,j+1), contains (j-1-a)+f+(n-j-1-c) ones.
The1-staircase in row p, column j, and row q, which turns at (p,j) and (q,j), contains d+(n-f)+e ones.
The0-staircase in row p, column j+1, and row q, which turns at (p,j+1) and (q,j+1), contains (j-1-d)+(n-f)+(n-j-1-e) zeroes.
The length sum of these homogeneous staircases isa+f+c+(j-1-a)+f+(n-j-1-c)+d+(n-f)+e+(j-1-d)+(n-f)+(n-j-1-e) = 4n-4, so the average length is n-1. Therefore, one of them has length at least n-1.Proof of Proposition12.
LetA be an 8×8 0-1 matrix; without loss of generality, suppose a8,8=0. By contradiction, assume all homogeneous staircases have length 6 or less. In the first row and last column combined, there can be at most 6 zeroes, so there must be at least 9 ones. Without loss of generality, assume the first row has at least as many ones as the last column, by assumption at most 6.
Case  1. First row contains 6 ones. The column of the rightmost 1 must contain either 7 zeroes or a 1, both giving a homogeneous staircase of length 7, a contradiction.
Case  2. First row contains 5 ones; consequently, the last column contains at least 4 ones. Let J be the set of indices j with a1,j=1 and let I be the set of indices i for which ai,8=1. We have |I|≥4, |J|=5. Then ai,j=0, if i is the smallest element of I and j is one of the last 4 elements of J (otherwise we get a 1-staircase of length at least 7). Similarly ai,j=0, if i is one of the first 4 elements of I and j is the largest element of J. This gives seven elements of A with ai,j=0, forming a 0-staircase, a contradiction finishing the proof.


## 3. Proof of Theorem4

Proof of Theorem4.
Consider an arbitrary red-blue coloring of the edges of a balanced geometric bipartite graphG=[A,B]. Let GR and GB denote the red and blue subgraphs of G. Set
(8)D=max⁡{dGR(a1),dGR(bn),dGB(a1),dGB(bn)}.
We will show that there is a noncrossing subtree inGR or in GB with (4/5+ε)n vertices, where ε is computed during the proof.
Assume first thatD≥(6/10+2ε)n; without loss of generality, the maximum is attained at bn in the red color. Let i denote the smallest index for which aibn is red. If ai has at least (2/10-ε)n red neighbors in B, we have a red noncrossing double star on aibn spanning at least (4/5+ε)n vertices. Otherwise ai has at least (8/10+ε)n blue neighbors in B giving a blue star that is as large as required.
From now on we consider the caseD<(6/10+2ε)n; assume (w.l.o.g.) that edge a1bn is red. Now—from the definition of D—both dGR(a1) and dGR(bn) are strictly greater than (4/10-2ε)n; therefore, we have a noncrossing red double star T on a1bn with more than (4/10-2ε)n vertices in both A and B. We may assume that T has less than (4/10+3ε)n vertices on both A and B; otherwise T has at least (8/10+ε)n vertices. Therefore, a1 is adjacent in blue to a set B1⊂B such that |B1|>(6/10-3ε)n. Similarly, bn is adjacent in blue to a set A1⊂A such that |A1|>(6/10-3ε)n. Let i be the smallest index for which ai∈A1 and j is the largest index for which bj∈B1.
Observe that edges fromai to B1 must be red apart from an initial segment B2⊂B1 such that |B2|<(2/10+4ε)n because otherwise we have a noncrossing double star in blue of the required size. Similarly, edges from bj to A1 must be red apart from an end segment of A2⊂A1 such that |A2|<(2/10+4ε)n. Thus we have a red double star T1 on the red edge aibj containing vertices of A1-A2∪B1-B2. Thus T1 has at least (4/10-7ε)n vertices in both A and B (and also at most (4/10+8ε)n; otherwise we have the required large noncrossing red subtree). Note also that we may assume that |A2|,|B2|>(2/10-11ε)n; otherwise if |A2|≤(2/10-11ε)n, then
(9)(|A1-A2|)+(|B1-B2|)>((610-3ε)-(210-11ε))n+(410-7ε)n=(810+ε)n.
We note next that there are less than(2/10+4ε)n blue edges from ai to B; otherwise the blue star A1∪{bn} can be extended to a noncrossing double star on (6/10-3ε+2/10+4ε)n vertices. Thus more than (1-(2/10+4ε))n=(8/10-4ε)n red edges go from ai to B.
SetS={bk:j<k≤n}, R={bk:1≤k<j} and observe that there are less than (15ε)n red edges from ai to R-(B1-B2); otherwise we can extend T1 to a noncrossing red double star with (8/10-14ε+15ε)n=(8/10+ε)n vertices.
The two previous statements and|B1|-|B2|≤(4/10+8ε)n imply that at least ((8/10-4ε)-15ε-(4/10+8ε))n=(4/10-27ε)n red edges go from ai to S. The same argument shows that at least (4/10-27ε)n red edges go from bj to the set S1={ak:1≤k<ai}. In particular, |S|,|S1|≥(4/10-27ε)n.
Sinceai sends at most (15ε)n red edges to B2, it sends at least (|B2|-15ε)n≥(2/10-26ε)n blue edges to set B3⊂B2. Suppose that the first vertex of B3 (bt∈B3 with smallest t) sends x blue edges to S1. Then we have a blue noncrossing tree with at least
(10)x+|B3|+|A1|≥x+(210-26ε)n+(610-3ε)n=x+(810-29ε)n.
Vertices; thus we may assume x≤(30ε)n. We conclude that some vertex of B3 sends at least (|S1|-30ε)n≥(4/10-57ε)n red edges to U⊂S1.
Now, we define a noncrossing blue treeT2 as follows. Let bl be the first element of B1-B2. Take the blue star from a1 to {bp∈B:p≤l}; it has at least |B2|≥(2/10-11ε)n edges. Continue with the sequence of blue edges from bl to U ending with the blue edge blak, ak∈U. This sequence must contain at least |U|-(15ε)n≥(4/10-72ε)n vertices because at most 15εn red edges go from bl to U; otherwise T1 would be extended. Finally, we add blue edges from ak to a subset of {bl,bl+1,…,bn}. To estimate how many, observe that there is a red star T3 with center ai with at least (4/10-7ε)n leaves in B1-B2 and at least (4/10-27ε)n leaves in S, thus altogether at least (8/10-34ε)n leaves. If there is a red edge from ak to the mth vertex of T3 (from left), then we have a noncrossing red tree with at least |U|+(8/10-34ε)n-m≤(8/10+ε)n vertices. This gives that (4/10-57ε)n+(8/10-34ε)n-m≤(8/10+ε)n and we conclude (4/10-92ε)n≤m. Altogether, T2 has at least
(11)(210-11ε)n+(410-72ε)n+(410-92ε)n=(1-175ε)n=(810+ε)n
vertices when ε=1/880.



---

*Source: 731519-2014-01-23.xml*