transitive

For example, 'being interconnected' and 'being on the same continent' are transitive relations. 'Love' isn't: if you love me, and I love Betsy, that doesn't mean you love Betsy.

The axiom of foundation implies that any transitive set must contain the empty set.

Examples of useful transitive sets are:

• Every natural number is transitive
• More generally, every ordinal (and therefore every cardinal) is transitive
• Each member V_a of the cumulative heirachy of sets (sets formed from the empty set by repeatededly taking power sets) is transitive

(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.

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

Tran"si*tive (?), a. [L. transitivus: cf. F. transitif. See Transient.]

1.

Having the power of making a transit, or passage.

Bacon.

2.

Effected by transference of signification.

By far the greater part of the transitive or derivative applications of words depend on casual and unaccountable caprices of the feelings or the fancy. Stewart.

3. Gram.

Passing over to an object; expressing an action which is not limited to the agent or subject, but which requires an object to complete the sense; as, a transitive verb, for example, he holds the book.

-- Tran"si*tive*ly, adv. -- Tran"si*tive*ness, n.

© Webster 1913.