# Ascending chain of vertex-transitive graphs

For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x, y\in X\text{ and } x\neq y\big\}$.

Let $G=(V,E)$ be a simple, undirected graph, and suppose ${\cal V}$ is a collection of subsets of $V$ such that for all $W, W' \in {\cal V}$ we have either $W\subseteq W'$ or $W' \subseteq W$.

If for all $W\in {\cal V}$ the induced subgraph $(W,E\cap [W]^2)$ is vertex-transitive, is the induced subgraph $(\bigcup {\cal V}, E\cap [\bigcup{\cal V}]^2)$ necessarily vertex-transitive as well?

(Applying Zorn's Lemma, which is equivalent to the Axiom of Choice, a positive answer would imply that every graph has a maximal vertex-transitive subgraph.)

Let $Q$ be a chain (totally ordered set). Let $Y_Q$ be the graph whose set of vertices is the set of pairs $(x,y)$ with $x,y\in Q$ and $x<y$, and an edge between $(x,y)$ and $(x',y')$ iff the intervals $]x,y[$ and $]x',y'[$ are disjoint.

If $Q$ is a 2-transitive chain then $Y_Q$ is a vertex-transitive graph.

Let $D$ be an "open right" long line, so $D$ is locally order-isomorphic to the reals, for every $x$, the set $\{y\in D:y<x\}$ is order-isomorphic to $\mathbf{R}$ and every countable subset has an upper bound;

Let $X$ be obtained by concatenation $D\sqcup\{x_0\}\sqcup\mathbf{R}$ of a copy of $D$, a singleton $x_0$, and a copy of $\mathbf{R}$.

I claim that $Y_X$ is not vertex-transitive. Indeed, if $x<x_0<y$, then any complete subgraph in $Y_X$ containing the vertex $(x,y)$ is countable. On the other hand, there is an uncountable complete subgraph (consider uncountably may disjoint nonempty open intervals in $D$).

Write $D=\bigcup D_\alpha$, ascending union of a chain of intervals all order-isomorphic to $\mathbf{R}$, and $X_\alpha=D_\alpha\cup\{x_0\}\cup\mathbf{R}$; then $X_\alpha$ is order-isomorphic to $\mathbf{R}$. Then $X=\bigcup X_\alpha$, and $Y_X=\bigcup Y_{X_\alpha}$, union of a chain of vertex-transitive subgraphs.

• Lovely example, nicely written down - thanks! – Dominic van der Zypen May 7 '18 at 13:07
• I'd like a countable example, anyway. – YCor May 8 '18 at 19:54