Hold the external endpoints fixed and distinguish the three Feynman diagrams by their left-to-right order in the source. Write for the divisor and for the multiplying combinatorial weight. Each line below includes external Feynman propagators; amputation leaves the same .
Left: two-point bubble. There are two cubic interaction vertices and two parallel internal lines. Interchanging those lines preserves the labelled external endpoints, giving . Direct Wick contraction counting gives two assignments of the external endpoints to the vertices, choices of their field slots, and pairings of the remaining slots:
With and external points , its contribution is
Middle: three-point triangle. The three labelled external endpoints fix their three adjacent cubic interaction vertices, so no nonidentity graph automorphism remains. Counting gives assignments of endpoints to vertices, choices of external field slots, and assignments of remaining slots to the two specified neighbours:
Its contribution is
The apparent rotational symmetry of an unlabelled triangle does not survive fixing three distinct external endpoints.
Right: two-point graph with a chord. There are four cubic interaction vertices: the left and right attachment vertices and the two chord ends . Its internal edges are . Reflection interchanges , fixes , and preserves the two external labels. This is the only nontrivial graph automorphism, so .
For a separate Wick contraction count, choose the ordered external attachment vertices in ways and their field slots in ways. Assign their two remaining slots to in ways. At each of , choose the slot joining and then the slot joining in ways; the last slots join each other. Thus
Its contribution is
Consequently the three multiplying weights are , or divisors . The central chord is a single internal line joining two vertices, not a vertex at the centre of the circle.
Here are the numbers of vertices, edges and graph automorphisms of . Vertex-disjoint ordered -tuples contribute to the factorial moment. Adding a copy overlapping the previous union in vertices and edges changes the power of by , strictly when the intersection is a proper nonempty subgraph. The first overlap is strict because is connected and the previous copies are disjoint. Finitely many overlap types therefore contribute . The factorial-moment criterion for Poisson convergence gives the result.
Quasi-transitive graph 2026-10-14
A graph is quasi-transitive if some group of graph automorphisms has finitely many vertex orbits. This is also called a graph of finite type. A connected graph that is infinite and a locally finite graph then has uniformly bounded degrees. Every orbit is infinite: a finite invariant orbit would have finite neighborhoods, and finitely many orbit types would put the entire graph in one such neighborhood. This permits finite sets to be moved arbitrarily far apart by graph automorphisms.
Symmetry group Created 2026-10-14 Updated 2026-10-14
A symmetry group collects bijections of an object to itself that preserve a specified structure in both directions, with function composition as the operation. For a geometric object one may require Euclidean distances to be preserved, giving an isometry group; for a graph, one preserves adjacency, giving a graph automorphism group. For an unstructured finite set, every permutation is allowed. The structure to be preserved is part of the definition.
For a square with its usual geometric structure, the symmetry group consists of four rotations and four reflections. These form the dihedral group of group order eight. The existing group action example shows how its eight elements move the vertices of a polygon; changing the object to its edges or a marked configuration changes the group action being studied.[ref]
Specifying the preserved data makes it possible to test a proposed symmetry exactly. After the preserved data are declared, function composition, the identity map, and inverse maps automatically preserve them too. Symmetry transformations therefore form a group, and questions about equivalent configurations become questions about group orbits, stabilizer subgroups, and group homomorphisms. This supplies reusable mathematics for comparing many different kinds of objects.
Traces is software for computing graph automorphisms and canonical graph labeling, developed by Adolfo Piperno and distributed with nauty. A canonical result permits two graphs to be compared without depending on their input vertex names. Traces uses individualization-refinement graph search, with strategies designed to reduce the explored search space.[ref]
Refinement groups vertices according to structural information, including their numbers of neighbors in existing vertex classes. When this does not distinguish all vertices, individualization temporarily gives a selected vertex its own class and refinement continues. Discovering equivalent choices and distinguishing branches can avoid repeated work; the validity of the framework and implementation strategies are developed with Brendan McKay.[ref]
An original example shows why a coarse invariant is insufficient. A cycle on6vertices and two separate triangles both have6vertices and every vertex has2neighbors. Starting with one vertex class, neighbor-count refinement leaves one class in both cases. Yet the graphs are not isomorphic: one is connected and the other is not. Their correct canonical graph encodings must therefore differ.
Conversely, two differently numbered copies of the same6-cycle should give the same canonical result when processed with the same canonicalization convention. The example illustrates the required behavior, not a benchmark of a particular Traces version.
Performance depends on the graph family and search strategy. The practical success of the program does not by itself establish a polynomial worst-case bound for graph isomorphism. A reproducible comparison should keep the canonicalization settings consistent rather than assume all programs must choose an identical representative.