4.5 Odd graph

TL;DR: Odd graph is not cayley.

Def. Let $\Omega =\{1,2,\cdots ,2k+1\}$ and let $V={\Omega }^{\{k\}}$. Define a graph with vertex set $V$ s.t. two vertices are adjacent iff they are disjoint. This graph is called an odd graph, denoted by $O_k$.

Note that the number of vertices is $|\Omega |=\left(\genfrac{}{}{0ex}{}{2k+1}{k}\right)$, and the valency of $O_k$ is $k+1$.

For a graph $\Gamma =(V,E)$, an independent set of $V$ is the maximal set whose vertices are nonadjacent pairwise. The independence number is cardinal number of a independent set.

The independent set of $O_k$ is $\left(\genfrac{}{}{0ex}{}{2k}{k-1}\right)$. For example, $\{\{1,i_1,\cdots ,i_k\}:i_j\in \Omega \}$ is an independent set and it corresponds to a unique element $1$.

So we get a proposition:

Prop. $Aut(O_k)=S_{2k+1}$.

When $k=2$, $O_k$ is Petersen graph and so is not Cayley. In fact, every odd graph with $k\ge 2$ is not Cayley.

Thm. If $k\ge 2$, then $O_k$ is vertex-transitive, edge-transitive but not Cayley.

Proof. $O_2$ is Petersen, so it suffices to show the case of $k\ge 3$. Suppose $O_k$ is a Cayley graph of $R$. Note that $R$ is $k$-homogeneous. Assume $R$ is $k$-transitive. Consider the sequence $$ R>R_{\omega_1}>R_{\omega_1,\omega_2}>\cdots>R_{\omega_1,\cdots,\omega_{k-1}},

we have $|R|/|R_{\omega_1}|=|\omega_1^R|=2k+1,\cdots,|R_{\omega_1\cdots,\omega_{k-2}}|/|R_{\omega_1,\cdots,\omega_{k-1}}|=k+3$ and so $|R|\geq (2k+1)!/(k+2)!>{2k+1\choose k}=|R|$ if $k\geq 3$, which is impossible. Therefore, *$R$ is $k$-homogeneous but not $k$-transitive*. By [Kantor's theorem](https://www.semanticscholar.org/paper/k-Homogeneous-groups-Kantor/80f56524d6a4cefc1c71a0727b331120811115b8), there are only finitely many group satisfying the condition. Compute orders of them and then we know all of them are impossible. ![[Pasted image 20240430190559.png]]