Ordered graphs and large bi-cliques in intersection graphs of curves

Pach, János and Tomon, I. (2019) Ordered graphs and large bi-cliques in intersection graphs of curves. EUROPEAN JOURNAL OF COMBINATORICS, 82. ISSN 0195-6698

Preview

Text 190209810.pdf Available under License Creative Commons Attribution. Download (199kB) | Preview

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 v10 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 ckn, or its complement has a bi-clique of size at least ckn∕logn. 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 nx-monotone curves in the plane has a bi-clique of size at least cn∕logn or its complement contains a bi-clique of size at least cn. (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 [Formula presented] edges for some ϵ>0, then G¯ contains a linear sized bi-clique. We show that this statement does not remain true if we replace [Formula presented] by any larger constants. © 2019 Elsevier Ltd

Actions (login required)

Edit Item