0
$\begingroup$

Let $[\omega]^2 =\big\{\{x,y\}:x\neq y \in \omega\big\}$ denote the collection of all 2-element subsets of the non-negative integers. Let $$E=\big\{\{p,q\} : p,q \in [\omega]^2 \text{ and } \max(p)=\min(q)\big\}.$$

Letting $G=([\omega]^2, E)$, it is easily verified that $G$ is triangle free, and a bit more work shows that $\chi(G) = \aleph_0$.

Question. Does $G$ have an infinite complete minor?

$\endgroup$
3
  • 2
    $\begingroup$ I do not see how an infinite matching would give an infinite complete minor, but it looks like the graph is infinitely vertex connected, so a greedy construction will even give you an infinite topological minor. $\endgroup$ Commented Jul 10 at 22:57
  • $\begingroup$ What's the definition of a topological minor? $\endgroup$ Commented Jul 12 at 4:44
  • 1
    $\begingroup$ $H$ is a topological minor of $G$ if $G$ has a subgraph which is isomorphic to a subdivision of $H$ $\endgroup$ Commented Jul 12 at 10:59

1 Answer 1

1
$\begingroup$

It seems to me that an infinite minor can be constructed as follows. For any $i\ge 1$, let $$V_i=\{(2i-1,2i)\}\cup\{(2i,j):j>2i\}.$$ The sets $V_i$ are all disjoint and each set $V_i$ is connected (as $(2i-1,2i)$ is adjacent to all vertices $(2i,j)$ with $j>2i$). Observe that for any $i<j$ there is an edge with one endpoint in $V_i$ and one endpoint in $V_j$ (namely between $(2i,2j)$ and $(2j,2j+1)$). So contracting every set $V_i$ into a single vertex gives an infinite complete minor.

Now, to complement Florian Lehner's comments to the OP, observe that each $V_i$ induces a star and that the edges connecting the sets $V_i$ actually connect the leaves of the corresponding stars (and in the definition above, each leaf $(2i,2j)$ of $V_i$ only connects to a leaf $(2j,2j+1)$ of a single $V_j$). So what we have obtained is actually stronger than an infinite complete minor: it is a 2-subdivision of the infinite complete graph (i.e. it is obtained from the infinite complete graph by replacing each edge by a 3-edge path).

$\endgroup$

You must log in to answer this question.

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