Question about Posa rotation.

Question

I’m reading a text that discusses Posa rotation, which is defined as follows.

Given a graph $G$ and a vertex $x_{0} \in V(G)$ suppose that $P=x_{0} x_{1} \ldots x_{k}$ is a longest path in $G$ starting at $x_{0}$. Given an edge $\left(x_{k}, x_{i}\right) \in E(G)$ a rotation of $P$ is a new path $P^{\prime}=$ $x_{0} x_{1} \ldots x_{i} x_{k} x_{k-1} \ldots x_{i+1}$. We say that a path $P^{\prime}$ is a transform of $P$ if it can be obatined from $P$ by a sequence of rotations. Let $U$ be the set of endvertices of all possible transforms of $P$ and let $$ N=\left\{x_{i}:\left\{x_{i+1}, x_{i-1}\right\} \cap U \neq \emptyset\right\} $$ be the set of neighbours of this set in $P$. Finally let $R=V(P) \backslash(U \cup N)$ be the rest of the vertices in $P$.

Note that, since by assumption $P$ is a longest path, the neighbourhood of $U$ is a subset of $V(P)$. Posá observed that in fact it had to be a subset of $U \cup N$

Lemma 7.4. Let $G$ be a graph, $x_{0} \in V(G)$ and $P$ a longest path in $G$ starting at $x_{0}$. If $U, N$ and $R$ are defined as above then there are no edges in $G$ between $U$ and $R$.

Proof. Omitted.

We note then that $ U \cup N(U) \subset U \cup N=U \cup\left\{x_{k-1}\right\} \bigcup_{x_{j} \in U, j \neq k}\left\{x_{j-1}, x_{j+1}\right\}$. Hence $|U \cup N(U)| \leq 3|U|-1$. That is, in some ways $U$ has small 'expansion'. We will show that in a sufficiently dense random graph, all 'small' subsets have large expansion and so, in particular, $U$ must be large.

I have two questions:

1. Where does the $x_{k-1}$ in that last expression for $U \cup N$ come from?
2. The lemma seems to say that the condition $|U \cup N(U)| \leq 3|U|-1$ always holds, irrespectively of the size of $U$. So I don’t get how we can have the situation where $U$ have large expansion, given the lemma.

Answer 1

The $x_{k-1}$ in the expression $$ U \cup N(U) \subset U \cup N=U \cup\left\{x_{k-1}\right\} \cup\bigcup_{x_{j} \in U, j \neq k}\left\{x_{j-1}, x_{j+1}\right\} $$ comes from treating $x_k$ as a special case. We'd like to say that $$ N = \bigcup_{x_j \in U} \{x_{j-1}, x_{j+1}\} $$ but this is not quite accurate. One of the elements of $U$ is $x_k$, and we can't take the union with $\{x_{k-1}, x_{k+1}\}$, because $x_{k+1}$ is nonsense. The expression $$ N = \{x_{k-1}\} \cup \bigcup_{x_j \in U, j \ne k} \{x_{j-1}, x_{j+1}\} $$ corrects for this: whenever $x_j \in U$ and $j \ne k$, we take both $x_{j-1}$ and $x_{j+1}$, but for $x_k$ we take only $x_{k-1}$. (Note that $x_0$ can never be an element of $U$, so $x_{j-1}$ always exists for all $x_j \in U$.)

---

As for expansion properties: it's true that we've proved $|U \cup N(U)| \le 3|U|-1$ for all $U$. However, when we prove expansion properties of a random graph, we don't prove them for all sets $U$. (We can't hope to prove that $|U \cup N(U)| \ge 3 |U|$ for all $U$, no matter what kind of graph we have: when $|U| > \frac13|V(G)|$, this is automatically false!)

In practice, we prove something like "W.h.p. $G_{n,p}$ has the property that for every $U$ with $|U| \le \frac{n}{10000}$, $|U \cup N(U)| \ge 3|U|$" (for a suitably chosen $p$). From the Pósa rotation argument, we conclude that if $U$ is the set of all endvertices, then $|U \cup N(U)| \le 3|U|-1$. Together, these two facts imply that if $U$ is the set of all endvertices, then $|U| > \frac{n}{10000}$.