Wikipedia article on forbidden graph substructures

Question

I apologies if this is too trivial a question or if I am over complicating anything here. But I was hoping for some clarification in an article I was reading about forbidden graph substructures on Wikipedia.

To explain, for any class of graphs $C$ let $\neg C$ be the class of all graphs not in $C$. Now given any pre-order $\leq$ on the class of all graphs we say that a class $F$ obstructs $C$ under $\leq$ iff for every graph $G$ we have the equivalence $G\not\in C\iff \text{There exists }H\leq G\text{ isomorphic to a graph in }F$.

For example if we write that $H\leq G$ when a graph $H$ is a minor of a graph $G$ then $\leq$ is a pre-order and by Wagner's theorem if $C$ is the class of planar graphs then $\{K_5,K_{3,3}\}$ obstructs $C$ under $\leq$.

With all that said, isn't it true that there exists an inclusion minimal obstruction class for any class of graphs $C$ under any pre-order $\leq$ if and only if $(1)$ membership in $C$ is closed under isomorphisms, $(2)$ $C$ is an ideal of $\leq$ and $(3)$ every chain in the pre-order $P=(\neg C,\leq)$ has some lower bound.

Since if $(1)$ and $(2)$ are true then defining $\preceq$ to be $(\leq/\cong)$ we see $[A]_{\cong }\preceq [B]_{\cong}\iff A\preceq B$ and for any class $F$ that $(F/\cong)=\{[G]_{\cong}:G\in F\}$ is cofinal in $P'=(\neg C/\cong,\succeq)$ if and only if $F$ obstructs $C$ under $\leq$. Thus when every chain in $P$ has a lower bound this means there exists an inclusion minimal class $F$ cofinal in $P'$ so that every complete set of representatives $T$ for the graph isomorphism classes in $F$ must be an inclusion minimal obstruction class of $C$ under $\leq$. In fact if at least one non-proper class (a set) obstructs $C$ under $\leq$ then the minimum cardinality of those sets obstructing $C$ (note the existence of a non-proper class obstructing $C$ may be guaranteed or even independent of the axioms we are using for example if $\leq$ is the induced subgraph pre-order then the existence of such a set is equivalent to Vopenka's principle which is currently not known to be inconsistent with ZFC) under $\leq$ is exactly $\text{cf}(P')$ (the cofinality of the pre-order $P'$). While note in particular for all $G\in T$ that $G\not\in C$ and $\forall H<G(H\in C)$ or as described on Wikipedia:

Now this seems trivial however https://en.wikipedia.org/wiki/Forbidden_graph_characterization (current revision) just assumes condition $(3)$ is always true. Which I don't think is correct, unless we're only working with finite graphs. Am I in the wrong here? Or is the author of the article?

Answer 1

First, I'll reiterate my comment that probably the Wikipedia article is focusing on finite graphs. So if some of the statements break down for classes of infinite graphs then it's really because of an unspecified convention, rather than an actual "error".

So if we make this assumption about the author's intent then the analogue of (3) would be that any class of finite graphs is well-founded, which is of course trivially true for the standard choices of $\leq$.

On the other hand, if we look at classes of infinite graphs, then things are more interesting. Throughout the answer, I will consider graphs as isomorphism types to make things simpler. Given an isomorphism-invariant preorder $\leq$ on graphs, and a class $\mathcal{F}$ of graphs, let $\text{Forb}_\leq(\mathcal{F})$ denote the class of graphs $G$ such that there is no $A\in\mathcal{F}$ satisfying $A\leq G$. If $\mathcal{C}=\text{Forb}_{\leq}(\mathcal{F})$ for some $\mathcal{F}$, then we say that $\mathcal{F}$ is an $\leq$-obstruction class for $\mathcal{C}$.

The following is an elaboration on the characterization of the existence of minimal obstruction classes suggested by the OP.

Proposition 1. Let $\mathcal{C}$ be a $\leq$-closed class of graphs. Then the following are equivalent.
$(i)$ $\mathcal{C}$ has a minimal $\leq$-obstruction class.
$(ii)$ $\mathcal{C}=\text{Forb}_{\leq}(\mathcal{F})$ for some $\leq$-anti-chain $\mathcal{F}$.
$(iii)$ $\mathcal{C}=\text{Forb}_{\leq}(\mathcal{E})$ for some $\leq$-well-founded class $\mathcal{E}$.
$(iv)$ Every descending $\leq$-chain in $\neg\mathcal{C}$ has a lower bound in $\neg\mathcal{C}$.

These equivalences should all be fairly straightforward.

---

The rest of this answer contains further remarks that I think are interesting and are motivated by earlier versions of the question and/or (possibly deleted) comments.

First, I'll just note that condition $(iv)$ of Proposition 1 does not require that the lower bound be in the chain or in the same equivalence class as something in the chain. So, in particular, this condition is not equivalent to saying that the antisymmetric quotient of the class of graphs not in $\mathcal{C}$ is well-founded. For example:

Example. Let $\leq$ denote the induced subgraph ordering and let $\mathcal{C}$ be the class of complete graphs. Then $\mathcal{C}$ has a unique minimal obstruction class, namely an independent graph of size $2$. This graph is an induced subgraph of any graph not in $\mathcal{C}$ and, in particular, is a lower bound for any descending chain. On the other hand, we can find an infinite descending chain in the antisymmetric quotient of the class of graphs not in $\mathcal{C}$. For example, given $n\geq 3$, let $H_n$ be the disjoint union of all cycles of length at least $n$. Then $H_n\not\in\mathcal{C}$ for all $n\geq 3$, and we have $H_3>H_4>H_5>\ldots$.

An earlier version of the question spoke of unique minimal obstruction classes, which I think is an interesting question. It is easy to find failures of uniqueness for minimal obstruction classes by considering graphs that are bi-embeddable but not isomorphic. In particular, given a choice of $\leq$, let $\equiv$ denote the induced equivalence relation.

Example. Let $\leq$ denote induced subgraph. Let $E$ and $F$ be graphs such that $E\equiv F$ but $E\neq F$. (For example, let $E$ be the disjoint union of the finite complete graph $K_n$ for all $n$, and let $F$ be the disjoint union of $K_n$ for even $n$.) Then $\mathcal{C}:=\text{Forb}_{\leq}(E)=\text{Forb}_{\leq}(F)$, but $\{E\}$ and $\{F\}$ are distinct minimal obstruction classes for $\mathcal{C}$.

This issue doesn't arise in the case of forbidding finite graphs under subgraph or induced subgraph, since $\equiv$ is the same as isomorphism for finite graphs. At any rate, by focusing on $\equiv$-invariant $\leq$-obstruction classes, we obtain the following characterization. Let $\leq^*$ denote the partial order obtained by the quotient of $\leq$ by $\equiv$.

Proposition 2. Let $\mathcal{C}$ be a $\leq$-closed class of graphs. Then the following are equivalent:
$(i)$ $\mathcal{C}$ has a unique minimal $\equiv$-invariant $\leq$-obstruction class.
$(ii)$ $\mathcal{C}$ has a minimal $\equiv$-invariant $\leq$-obstruction class.
$(iii)$ $\mathcal{C}=\text{Forb}_\leq(\mathcal{F})$ for some $\equiv$-invariant $\leq^*$-antichain $\mathcal{F}$.
$(iv)$ $\mathcal{C}=\text{Forb}_\leq(\mathcal{E})$ for some $\equiv$-invariant $\leq^*$-well-founded class $\mathcal{E}$.

Proof. $(i)\Rightarrow (ii)\Rightarrow (iii)\Rightarrow(iv)$ are straightforward.

$(iv)\Rightarrow(i)$. Assume $\mathcal{C}=\text{Forb}_{\leq}(\mathcal{E})$ for some $\leq^*$-well-founded $\mathcal{E}$. Let $\mathcal{H}$ be the class of graphs $H$ such that $H\not\in\mathcal{C}$, but if $H'<H$ then $H'\in\mathcal{C}$. Then $\mathcal{H}$ is $\equiv$-invariant. It also follows from the definition of $\mathcal{H}$ that $\mathcal{H}\subseteq\mathcal{E}'$ for any $\equiv$-invariant class $\mathcal{E}'$ such that $\mathcal{C}=\text{Forb}_{\leq}(\mathcal{E}')$. So to show that $\mathcal{H}$ is the unique minimal $\equiv$-invariant $\leq$-obstruction class for $\mathcal{C}$, we just need to verify that $\mathcal{C}=\text{Forb}_{\leq}(\mathcal{H})$. By the previous observation, we have $\mathcal{H}\subseteq\mathcal{E}$, so $\mathcal{C}=\text{Forb}_{\leq}(\mathcal{E})\subseteq\text{Forb}_{\leq}(\mathcal{H})$. Conversely, suppose $G\in\text{Forb}_{\leq}(\mathcal{H})$. Toward a contradiction, suppose $G\not\in\mathcal{C}$. Since $G\not\in\mathcal{H}$, there is some $H_1<G$ such that $H_1\not\in\mathcal{C}$. So there is some $E_1\in\mathcal{E}$ such that $E_1\leq H_1$. Note that $E_1\not\in\mathcal{C}$. Since $E_1\leq G$ and $G\in\text{Forb}_{\leq}(\mathcal{H})$, we have $E_1\not\in\mathcal{H}$, and so there is $H_2<E_1$ such that $H_2\not\in\mathcal{C}$. So there is $E_2\in\mathcal{E}$ such that $E_2\leq H_2$. Continuing this way we violate the assumption that $\mathcal{E}$ is $\leq^*$-well-founded.

Finally, one can ask about the existence of unique minimal obstruction classes (without imposing $\equiv$-invariance). Here is a first step. We say that a graph $G$ has the $\leq$-CSB property if $G'\equiv G$ implies $G'\cong G$. Then a class of graphs has the $\leq$-CSB property if every graph in the class does.

Proposition 3. Let $\mathcal{C}$ be a $\leq$-closed class of graphs. Then the following are equivalent:
$(i)$ $\mathcal{C}$ has a unique minimal $\leq$-obstruction class.
$(ii)$ $\mathcal{C}=\text{Forb}_\leq(\mathcal{F})$ for some $\leq$-antichain $\mathcal{F}$ with the $\leq$-CBS property.
$(iii)$ $\mathcal{C}=\text{Forb}_\leq(\mathcal{E})$ for some $\leq$-well-founded class $\mathcal{E}$ with the $\leq$-CSB property.

Proof. The proof is essentially the same as that of Proposition 2, once one makes the following observations:

1. Any class of graphs with the $\leq$-CSB property is $\equiv$-invariant.
2. If $\mathcal{C}$ has a unique minimal $\leq$-obstruction class $\mathcal{H}$, then $\mathcal{H}$ has the $\leq$-CSB property. Indeed if some $F\in\mathcal{H}$ fails the $\leq$-CSB property, witnessed by $F'\equiv F$, then either $F'\in\mathcal{H}$ and so $\mathcal{H}$ is not minimal, or $F'\not\in\mathcal{H}$ and so $\mathcal{H}$ is not unique.
3. If $\mathcal{H}$ is a class of graphs with the $\leq$-CSB-property, and $\mathcal{H}$ is contained in the $\equiv$-closure of some class $\mathcal{E}$, then $\mathcal{H}$ is contained in $\mathcal{E}$.

Of course this is just a first step. In particular, a classification of the graphs $F$ such that $\text{Forb}_{\leq}(F)$ has a unique minimal $\leq$-obstruction class amounts to a classification of graphs with the $\leq$-CSB property. I am not aware of any such classification (for standard choices of $\leq$).