One of the difficulties of extending results from finite graphs to infinite ones is that it is not always obvious how to extend the definitions. A single class of finite graphs may correspond, in the infinite graph world, to several different natural classes of infinite graphs. One of the ways this can happen is through orderings: if a class of graphs has a natural ordering on its vertices (say, through a construction in which graphs in this class are built up by adding one vertex at a time) then we might get several classes of infinite graphs with different ways of restricting or not restricting this vertex ordering.

Threshold graph

As an example of this phenomenon, consider the threshold graphs, one of the simplest classes of finite graphs. An example is shown above. These can be defined in multiple equivalent ways:

  • The finite threshold graphs are the graphs that can be built up by repeatedly adding either a universal vertex or an isolated vertex to a smaller graph. In the example, the vertices have been added in left-to-right order, with isolated vertices depicted in yellow and universal vertices in blue. This can be formalized in a way that extends to infinite graphs by saying that they are the graphs in which every nonempty induced subgraph contains either a universal vertex or an isolated vertex. Let’s call these graphs the “inductive threshold graphs”.

  • We can also construct graphs in the reverse ordering, by repeatedly adding a vertex whose neighbors form a clique and whose non-neighbors form an independent set. More concisely, the vertex is both simplicial and cosimplicial. The example above can be constructed in this way by adding the vertices in right-to-left order, with the blue neighbors of each added vertex forming a clique and the yellow neighbors forming an independent set. This can be formalized in a way that extends to infinite graphs by requiring that every induced subgraph has a vertex that is simplicial and cosimplicial. Let’s call a graph with this property a “coinductive threshold graph”.

  • The finite threshold graphs are the \((P_4,C_4,2K_2)\)-free finite graphs, meaning that no four vertices form an induced subgraph that is a path, cycle, or perfect matching.

  • The finite threshold graphs get their name from the following property: they are the graphs that we can generate by assigning weights in the interval \([0,1]\) to the vertices and connecting two vertices by an edge whenever their sum of weights is at least one. Let’s call a graph with this property a “real threshold graph”.

All four of these properties are hereditary: if a graph has the property, so do all its induced subgraphs. Because the three forbidden subgraphs \(P_4\), \(C_4\), and \(2K_2\) have no universal or isolated vertex, have no simplicial and cosimplicial vertex, and have no valid weight assignment, the inductive threshold graphs, coinductive threshold graphs, and real threshold graphs are all subclasses of the \((P_4,C_4,2K_2)\)-free graphs.

If a graph is \((P_4,C_4,2K_2)\)-free, we can define a relation \(\le\) on its vertices by saying that \(u\le v\) if there is no vertex \(w\) with \(vuw\) forming an induced path or complement of a path. It follows from the nonexistence of the forbidden subgraphs that this is a total preorder, that every vertex \(v\) is universal or isolated among the vertices \(\{u\mid u\le v\}\), and that every vertex \(v\) is simplicial and cosimplicial among the vertices \(\{w\mid v\le w\}\). In the example above, two vertices are in the same equivalence class of the ordering if they are in a contiguous block of vertices with the same color, and otherwise their ordering according to \(\le\) is the same as their left-to-right ordering. Because every finite total preorder has a minimal and a maximal element, every finite \((P_4,C_4,2K_2)\)-free graph is an inductive threshold graph and a coinductive threshold graph.

However, these properties differ for infinite graphs. In an infinite inductive threshold graph, the total preorder must obey the ascending chain condition that there be no strictly-increasing infinite sequence of vertices, for the subgraph induced by the vertices of such a sequence would have no isolated or universal vertex. Conversely, if the order does obey the ascending chain condition, one could find an isolated or universal vertex in any subgraph by starting from an arbitrary vertex and repeatedly moving upwards in the order until getting stuck. So the inductive threshold graphs are exactly the ones whose order obeys the ascending chain condition. Similarly, the coinductive threshold graphs are exactly the ones whose order obeys the descending chain condition. But it is easy to construct orders that violate one or both of these conditions. A graph can only be a real threshold graph if the total order on the equivalence classes of its preorder can be embedded into \([0,1]\), and again this is not true of all total orders.

One consequence of this difference between classes of infinite graphs is the construction of natural statements in the first-order logic of graphs that are true for all finite graphs but untrue for some infinite graphs. For instance, the statements that a \((P_4,C_4,2K_2)\)-free graph has an isolated or universal vertex, and that a \((P_4,C_4,2K_2)\)-free graph has a simplicial and cosimplicial vertex, are both true of all finite graphs, but untrue of some infinite graphs.

(Discuss on Mastodon)