Why is the SSCG function restricted to subcubic graphs?

250 Views Asked by At

$SSCG$$(k)=n$, where $G_1,G_2,\dots,G_n$ is the longest sequence of simple subcubic graphs such that $|G_i|\le i+k$ and no $G_i$ is a minor of $G_j$, where $i < j$. It grows quite fast.

My question is, given that the Robertson–Seymour theorem to all (undirected) graphs, why did Friedman choose to restrict this function to subcubic graphs? Why not use base it on sequences of simple graphs in general, or even all graphs?

1

There are 1 best solutions below

0
On

My question is, given that the Robertson–Seymour theorem to all (undirected) graphs, why did Friedman choose to restrict this function to subcubic graphs?

Short answer: For subcubic graphs, it has been proved that the condition $(|G_i|\le i+k)$ ensures the existence of a longest sequence of the kind being considered. As far as I know, similar conditions haven't (yet) been proved sufficient for that purpose in more-general cases.

Longer answer: The Robertson–Seymour theorem states that finite undirected graphs, quasi-ordered by the graph minor relation, form a well-quasi-ordering; i.e., there is no infinite sequence of such graphs that avoids having some element being a minor of some other element. Thus, every sequence that avoids such an embedding must be finite.

However, without further restrictions, such emdedding-free finite sequences can be arbitrarily long. Ensuring the existence of a maximum attainable length of such sequences is the purpose of the additional condition $(|G_i|\le i+k)$, which imposes a maximum size on each graph in the sequence -- but only for certain kinds of graph has it has been proved that this condition (or a similar condition) is indeed sufficient for this purpose.

Friedman showed the sufficiency of this condition for subcubic graphs (both simple and non-simple); so, for such kinds of graph, it is known that there exists a longest sequence $G_1,G_2,\dots,G_n$ such that $|G_i|\le i+k$ and no $G_i$ is a minor of $G_j$, where $i < j$.


An easier-to-understand special case of this is Higman's lemma applied to sequences of finite words on a finite alphabet. Every sequence that avoids having some element a subsequence of some other element must be finite, but such sequences can be arbitrarily long. However, if we impose the additional condition that the $i$th word in the sequence have length at most $i$, then it can be shown that there exists a maximum attainable length of such embedding-free sequences. (This is the basis of Friedman's "Block subsequence theorem". See also Higman's game.)