On the complexity of finite subgraphs of the curve graph

Abstract

We say a graph has property ${\mathcal{P}}_{g,p}$ when it is an induced subgraph of the curve graph of a surface of genus $g$ with $p$ punctures. Two well-known graph invariants, the chromatic and clique numbers, can provide obstructions to ${\mathcal{P}}_{g,p}$. We introduce a new invariant of a graph, the 'nested complexity length', which provides a novel obstruction to ${\mathcal{P}}_{g,p}$. For the curve graph this invariant captures the topological complexity of the surface in graph-theoretic terms; indeed we show that its value is $6g-6+2p$, i.e. twice the size of a maximal multicurve on the surface. As a consequence we show that large half-graphs do not have ${\mathcal{P}}_{g,p}$, and we deduce quantitatively that almost all finite graphs which pass the chromatic and clique tests do not have ${\mathcal{P}}_{g,p}$. We also reinterpret our obstruction in terms of the first-order theory of the curve graph, and in terms of RAAG subgroups of the mapping class group (following Kim and Koberda). Finally, we show that large multipartite subgraphs cannot have ${\mathcal{P}}_{g,p}$. This allows us to compute the upper density of the curve graph, and to conclude that clique size, chromatic number, and nested complexity length are not sufficient to determine ${\mathcal{P}}_{g,p}$.

15 pages, 2 figures

References in corpus (1)

• Anti-trees and right-angled Artin subgroups of braid groups

Cited by in corpus (2)

• Actions of right-angled Artin groups in low dimensions
• The RAAGs on the complement graphs of path graphs in mapping class groups