transitive

'Chaining'. A relation is transitive if it applies to each path formed by the relation.

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.

In discrete mathematics, a relation is transitive if there is a relation from a->b, b->c, there must also be a relation from a->c. See also Warshall's algorithm, transitive closure.

A set A is said to be transitive if whenever x is in A and y is in x then y is in A. In other words, every member of A is a subset of A.

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

In general, transitivity is a property of a relation: if whenever a~b and b~c , then a~c , the relation is transitive. Equality is a transitive relation, so is (set-wise) containment.

In group theory, when a group has a permutation action on a set, the action is called transitive if there are group elements whose permutation action is to exchange any given pair of elements of the set. Such an action is called doubly-transitive if any two ordered pairs can be exchanged by the permutation action of some group element, triply-transitive if any two ordered triples can be exchanged, etc.

--back to combinatorics--

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

[R.]

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.