1
$\begingroup$

Let $K$ be an infinite cardinal. Then, by the Robertson–Seymour theorem, the set of graphs with fewer than $K$ vertices and edges form a well-quasi-order.

In terms of $K$, what is the maximal order type of this well-quasi-order?

(The maximal order type of a well-quasi-order $(X,\le_X$) is the supremum of the ordinals that embed into $\le_X$.)

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This question rests on a false premise: the second sentence in the OP is false: by [Robin Thomas, A counter-example to 'Wagner' conjecture' for infinite graphs, Math. Proc. Camb. Phil. Soc. (1988), 103, 55-57], if $K=2^{\aleph_0}$, then your set of graphs $G$ with at most $K$ vertices is not a well-quasi-order. The question will have to be corrected. I don't know how though. An obvious idea would be to impose an upper bound on $K$, but making it $K<2^{\aleph_0}$ would be rather uninformative, for reasons related to forcing and the unnknown size of the cardinality of the continuum. $\endgroup$
    – Peter Heinig
    Commented Feb 22, 2018 at 11:27
  • $\begingroup$ Also worth pointing out: to say "with fewer than $K$ vertices and edges" is redundant, because by basic cardinal arithmetic, a graph having at most $K$ vertices, necessarily has at most $K$ edges. $\endgroup$
    – Peter Heinig
    Commented Feb 22, 2018 at 13:28

0

Reset to default

You must log in to answer this question.