transitive (thing)

(Graph Theory:)

A graph G=(V,E) is transitive if for every pair of vertices x,y∈V, there exists some automorphism of G α∈Aut(G) for which α(x)=y. (Note that, since any automorphism is invertible, this implies β(y)=x for β=α^-1).

Transitivity is a symmetry of the graph: every vertex of the graph looks exactly the same as every other vertex. If asked whether you were located at x or at y above, you'd be unable to determine which just by looking at vertices and their edges!

This form of transitivity is sometimes called vertex transitivity, to distinguish it from other forms which preserve other parts of the graph:

• G is edge transitive if for any pair of edges e={u,v}, f={w,x}, there exists an automorphism α∈Aut(G) for which α(e)=f (i.e. either α(u)=w and α(v)=x, or α(u)=x and α(v)=w).
• A flag is a pair (u,{u,v}), with u∈V a vertex and {u,v}∈E an edge from u. G is flag transitive if for any pair of flags (u, {u,v}) and (w, {w,x}), there exists an automorphism α∈Aut(G) with α(u)=w and α({u,v})=α({w,x}).

  Note that this implies both edge- and vertex-transitivity, if in addition every vertex has at least one edge connected to it.

Examples

• The d-dimensional grid Z^d is vertex-transitive, edge-transitive, and flag-transitive: we have automorphisms moving any vertex to any other, moving any edge to any other, or even redirecting any flag to any other.
• The d-dimensional hypercube H^d={0,1}^d is also vertex-, edge-, and flag-transitive.
• Define a tree T as follows: Let {d_j}_j=0,1,... be some fixed sequence. Take a root vertex v, and define V₀={v}. To define V_k, create d_k-1-1 new vertices for each vertex in V_k-1, connecting each one with an edge to that vertex. So T is a tree where a vertex at distance l from the root has degree d_l.

  If d₀=d₁=...=d is some fixed constant, then T is a (d+1)-regular tree, and is vertex-, edge-, and flag-transitive.

  If d₀=d₂=...=d and d₁=d₃=...=d' are two (different) constants, the T is edge-transitive: any edge connects a vertex of degree d with a vertex of degree d', and we can find an automorphism to transfer any edge to any other edge. But T is not vertex-transitive: an graph automorphism cannot transfer a vertex of degree d to a vertex of degree d'≠d.

     ...--*--...               ...--*--...
           \                       /
            *                     *
             \                   /
              \                 /
               *-------*-------*
              /                 \
             /                   \
            *                     *
           /                       \
     ...--*--...               ...--*--...
  

  So T is also not flag-transitive.

• Take some d-regular tree T. As seen above, T is vertex-, edge- and flag-transitive. Replace each vertex of T with a cycle of length d, letting each edge of T depart from a different vertex of the cycle. The resulting graph S is vertex-transitive, but clearly T is not edge-transitive: an edge between 2 cycles participates in no cycles, whereas an edge inside a cycle does participate in some cycle -- thus, no automorphism of S can transfer the one to the other. S is also not flag-transitive, since it is not edge-transitive.

          ...    ...
           \     /
            *---*
             \ /
              *
              |
              *
             / \
    ...     *---*     ...
     \     /     \     /
      *---*       *---*
       \ /         \ /
        *           *
        |           |
       ...         ...