Symmetry and connectivity of graphs

Definition 3.6   An undirected graph $X=(V,E)$ is connected if every pair of vertices is connected by a path. It is $k$-connected if it remains connected after removing any $k-1$ vertices (except the complete graph $K_n$ which is $n-1$-connected by convention). Let $\kappa(X)$ be the maximum $k$ such that $X$ is $k$-connected. $\kappa(X)$ is called the vertex-connectivity of $X$.

Example 3.7   The cycle graph has $\kappa(C_n)=2$ for all $n\ge 3$. One should think of this as a topological invariant and all cycles have the same shape. This requires the convention that $\kappa(C_3)=\kappa(K_3)=2$.

Definition 3.8   If $s,t$ are vertices in a graph $X$, then the $s$-$t$-connectivity $\kappa(X;s,t)$ is the minimum number of vertices to delete to prevent there from being a path from $s$ to $t$. (If there's a direct edge from $s$ to $t$, count deleting it as deleting a vertex.) Then $\kappa(X)=\min_{s,t}\{\kappa(X;s,t)\}$. There is a similar notion $\kappa^+(X;s,t)$ for directed graphs and directed paths from $s$ to $t$. There is also the edge $s$-$t$-connectivity $\rho(X;s,t)$, the minimum number of edges to delete to prevent there from being a path from $s$ to $t$. This has a global version $\rho(X)=\min_{s,t}\{\rho(X;s,t)\}$ and a directed version $\rho^+$.

Theorem 3.9 (Menger)   $\kappa(X;s,t)$ is also the number of vertex-disjoint paths from $s$ to $t$. $\rho(X;s,t)$ is also the number of edge-disjoint paths from $s$ to $t$. The analogous directed versions are also true.

Definition 3.10   $X$ is a vertex-transitive graph if its automorphism group acts transitively on its vertices. Similarly, it is edge-transitive if the automorphism group acts transitively on the edges. It is vertex- or edge-primitive if the automorphism group acts primitively on the set of vertices (edges, respectively).

Theorem 3.11 (Mader-Watkins)   If $X$ is an undirected, connected, vertex-transitive graph, regular of degree $d$, then

1. $\kappa(X)\ge\lceil\frac{2d+1}3\rceil$;
2. $\rho(X)=d$;
3. if $X$ is edge-transitive or vertex-primitive, then $\kappa(X)=d$.

Definition 3.12   A directed graph is strongly connected if for every pair of vertices $s$ and $t$, there is a directed path from $s$ to $t$. It is weakly connected if it is a connected as an undirected graph when we ignore the orientation of the edges.

Definition 3.13   A directed graph $X$ satisfies the Euler condition if for each vertex the in-degree is equal to the out-degree.

Theorem 3.14 (Hamidoune)   If $X$ a finite, connected vertex-transitive digraph then

1. $\kappa^+(X)\ge\lceil\frac{d+1}2\rceil$;
2. $\rho^+(X)=d$;
3. if $X$ is edge-transitive or vertex-primitive, then $\kappa^+(X)=d$.

A typesetting command error (a signle omitted backslash) rendered a paragraph unintelligible in the previous handout. It was the paragraph connecting two theorems. Here we reproduce the two theorems with the corrected paragraph inbetween.

Theorem 3.15 (B-Seress)   Let $S$ generate $S_n$. $\mathop{\rm diam}\nolimits (S_n,S)< m_n^{1+o(n)}$.

This result suffers from the ``element-order bottleneck.'' The two tricks used are commutators and raising elements to powers. A recent result gives a polynomial upper bound under the condition that one of the generators fixes 70% of the permutation domain. So now all is left to prove is that we can reach such a permutation in a polynomially bounded number of steps. Somebody in this audience may be able to do this with a fresh idea.

Theorem 3.16 (B-Beals-Seress)   Let $S$ generate $S_n$. If $\exists s\in S$ with the $\deg s<0.3n$ then $\mathop{\rm diam}\nolimits (S_n,S)<n^C$ ($C=12$?). (Recall that the degree of a permutation is size of its support, the set of elements that it actually moves.)