Ordered graphs and large bi-cliques in intersection graphs of curves. (December 2019)

• Record Type: Journal Article
• Authors: Pach, János; Tomon, István
• Is Part Of: European journal of combinatorics. Volume 82(2019)
• Publication Date: 2019-12
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2019.07.005
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: An ordered graph G < is a graph with a total ordering < on its vertex set. A monotone path of length k − 1 is a sequence of vertices v 1 < v 2 < … < v k such that v i v j is an edge of G < if and only if | j − i | = 1 . A bi-clique of size m is a complete bipartite graph whose vertex classes are of size m . We prove that for every positive integer k, there exists a constant c k > 0 such that every ordered graph on n vertices that does not contain a monotone path of length k as an induced subgraph has a vertex of degree at least c k n, or its complement has a bi-clique of size at least c k n ∕ log n . A similar result holds for ordered graphs containing no induced ordered subgraph isomorphic to a fixed ordered matching. As a consequence, we give a short combinatorial proof of the following theorem of Fox and Pach. There exists a constant c > 0 such the intersection graph G of any collection of n x -monotone curves in the plane has a bi-clique of size at least c n ∕ log n or its complement contains a bi-clique of size at least c n . (A curve is called x -monotone if every vertical line intersects it in at most one point.) We also prove that if G has at most 1 4 − ϵ n 2 edges for some ϵ > 0, then G ¯ contains a linear sized bi-clique. We show that this statement does not remain true if we replace 1 4 by any larger constants.