%0 Journal Article
%T Noncrossing Monochromatic Subtrees and Staircases in 0-1 Matrices
%A Siyuan Cai
%A Gillian Grindstaff
%A Andr¨¢s Gy¨¢rf¨¢s
%A Warren Shull
%J Journal of Discrete Mathematics
%D 2014
%I Hindawi Publishing Corporation
%R 10.1155/2014/731519
%X 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 geometric ? 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 0-1 matrix contains zeros or 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. 1. Introduction A geometric 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 graph is a geometric graph, whose vertices are in two disjoint -element sets and , and its edges are some segments with and . The following representation, apparently studied first in [2], seems to be a more natural subclass of balanced geometric bipartite graphs (in fact a standard way of drawing bipartite graphs). The partite sets of in are and and the edge is the line segment joining and . This representation is called a simple . Analogues of Tur¨¢n and Ramsey theories have been considered for geometric graphs, see; [1, 3¨C9] and its references. Our starting point is the following Ramsey-type problem for simple -s. Problem 1 (see [5]). Find , the order of the largest monochromatic noncrossing subtree that exists in every -coloring of the edges of a simple geometric . The lower bound is and the upper bound is for even and for odd . Noncrossing subgraphs of simple -s can be easily characterized. Proposition 2 (see [10]). Every connected component of a noncrossing subgraph of simple is a caterpillar (a tree in which the vertices of degree larger than one form a path). In fact, the lower bound is proved in a stronger form. Theorem 3 (see [5]). In every -coloring of the simple there is a noncrossing monochromatic double star with at least vertices. This bound is asymptotically best possible. Since Theorem 3 is asymptotically sharp, it was asked in [5] whether one can separate and . Here, we answer this question positively, although with a small margin. Theorem 4. Consider , where . We give a new construction showing that the upper
%U http://www.hindawi.com/journals/jdm/2014/731519/