0
$\begingroup$

Let $G=(V,E)$ be a simple, undirected graph. If $S, T\subseteq V$ are disjoint sets, we say that $S,T$ are connected to each other if there are $s\in S, t\in T$ such that $\{s,t\}\in E$. We say a graph $G_1 = (V_1, E_1)$ is an induced minor of $G$ if there is a collection ${\cal S} \subseteq {\cal P}(V)$ such that every member of ${\cal S}$ is connected and there is a bijection $\varphi:V_1\to {\cal S}$ such that for all $a\neq b\in V_1$ we have

$\{a, b\} \in E_1$ if and only if $\varphi(a), \varphi(b)\in {\cal S}$ are connected to each other.

Question. Is there a countable graph with $2^{\aleph_0}$ pairwise non-isomorphic induced minors?

$\endgroup$
1
  • 5
    $\begingroup$ An infinite path has $2^{\aleph_0}$ pairwise nonisomorphic induced subgraphs. $\endgroup$
    – bof
    Commented Sep 16 at 9:08

1 Answer 1

5
$\begingroup$

Yes, even for induced subgraphs (which are in particular induced minors). For Rado universal countable graph (a.k.a. Erdős—Renyi countable random graph), every countable graph is its induced subgraph. Since there are continuum many non-isomorphic countable graphs (for example, consider an infinite path and for a subset $V_1$ of the vertex set take an edge outside from every vertex $v\in V_1$; different subsets give non-isomorphic graphs), it is an example.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .