On the complexity of finite subgraphs of the curve graph (Q1626407)

Let \(S\) be a hyperbolic surface of genus \(g\) with \(p\) punctures. Let \(\mathcal{P}_{g,p}\) indicate the property that a graph is an induced subgraph of the curve graph \(\mathcal{C}(S)\) of \(S\) (an infinite graph whose vertices correspond to isotopy classes of essential simple closed curves on \(S\) such that two vertices are connected by an edge if and only if they are disjoint). The chromatic and clique numbers are two well known invariants which can provide obstructions to \(\mathcal{P}_{g,p}\). The authors introduce \textit{nested complexity length}, a new invariant of a graph, which gives an obstruction to \(\mathcal{P}_{g,p}\), and show that for the curve graph this invariant captures the topological complexity of the surface since it equals twice the size of a maximal multicurve on \(S\) which is \(6g-6+2p\). Furthermore, their result also holds for clique graphs (whose vertices are multicurves on \(S\) such that two vertices are connected by an edge if they can be realized disjointly). This result yields that chromatic and clique numbers are not sufficient to determine if a finite graph has \(\mathcal{P}_{g,p}\) since it is shown quantitatively that almost all finite graphs which pass the chromatic and clique tests do not have \(\mathcal{P}_{g,p}\). The authors additionally reinterpret their obstruction in terms of right-angled Artin subgroups of the mapping class group of \(S\) (group of isotopy classes of orientation preserving homeomorphisms of \(S\)) since the question of which finite graphs have \(\mathcal{P}_{g,p}\) and when it is obstructed is closely related with the question of which RAAG subgroups embed in the mapping class group of \(S\) following results of Koberda and Kim. Finally, by showing that large multipartite graphs can't have \(\mathcal{P}_{g,p}\) they explicitly calculate the upper density of the curve graph and conclude that clique size, chromatic number and the nested complexity length are not sufficient to determine \(\mathcal{P}_{g,p}\).