A Sharper Ramsey Theorem for Constrained Drawings

ABSTRACT Given a graph and a collection of subsets of indexed by the subsets of vertices of , a constrained drawing of is a drawing where each edge is drawn inside some set from , in such a way that nonadjacent edges are drawn in sets with disjoint indices. In this paper we prove a Ramsey‐type result for such drawings. Furthermore, we show how the results can be used to obtain Helly‐type theorems. More precisely, we prove the following. For each and , there is with the following properties: If is a drawing of a graph on vertices and is a collection of sets of such that each ‐tuple of vertices lies in a set indexed by , and contains at least one edge in , then in , we can find a constrained copy of the complete graph . As a direct consequence we obtain the following Helly‐type result: For each , there is a polynomial of degree at most such that the following holds. For every family of sets in , its Helly number is at most , provided that the intersection of any nonempty subfamily has at most path‐connected components, and trivial homology groups , . This dramatically improves the original theorem by Matoušek which had stronger assumption and a tower‐like bound on . Under the same assumptions, our technique can also be used to bound Radon numbers.