On the spectrum and number of convex sets in graphs

A subset S of vertices of a graph G is g-convex if whenever u and v belong to S, all vertices on shortest paths between u and v also lie in S. The g-spectrum of a graph is the set of sizes of its g-convex sets. In this paper we consider two problems - counting g-convex sets in a graph, and determining when a graph has g-convex sets of every cardinality (such graphs are said to have the continuum property). We show that the problem of counting g-convex sets of a graph whose components have diameter at most 2 is #P-complete, but for the class of cographs these sets can be enumerated in linear time. The problem of determining whether or not the g-convexity of a graph has the continuum property is proven to be NP-complete. While every graph is shown to be an induced subgraph of a graph whose g-convexity possesses the continuum property, graphs with the continuum property are rare since for any fixed ϵ∈(0,1) it is shown that almost all n-vertex graphs have a gap in their g-spectrum of size at least Ω(n1−ϵ). Moreover, it is shown that for almost all graphs, every g-convex set is a clique, from which it follows that the number of g-convex sets in a random graph is at least nclnn for some constant c. The graph convexity under discussion fits within the class of alignments on a finite set, namely those set systems on a finite set V that contain the whole set, the empty set, and are closed under intersection. Finite topologies are perhaps the most famous examples of alignments, and our results here are compared and contrasted with what can be said for topologies on a finite set.