Adolfo Piperno 2026-11-05
Adolfo Piperno is a computer scientist at Sapienza University of Rome whose work includes algorithms for graph isomorphism and graph canonical labeling. His institutional profile identifies him in the Department of Computer Science.[ref]
Adolfo Piperno profile at Sapienza University of Rome. Departmental profile and linked university research description
Piperno introduced the approach implemented in Traces graph isomorphism software, studying how to reduce the search needed for canonical labeling. His paper examines refinement of vertex classes, the choice of vertices to individualize, search order and the use of discovered graph automorphisms.[ref]
Search Space Contraction in Canonical Labeling of Graphs by Adolfo Piperno. Abstract and introduction, individualization/refinement and Traces
An original small example illustrates individualization-refinement graph search. For the four-vertex path , grouping vertices by their numbers of neighbors first gives classes and . Give vertex1 a unique marker. Neighbor counts relative to that singleton then distinguish vertex2 from vertex3, and further refinement separates the remaining vertices. Choosing vertex4 instead produces the reflected ordering. A canonical-labeling procedure must account for such equivalent choices rather than depend on the input vertex names.
This example explains the basic mechanism, not every heuristic in Traces. Piperno and Brendan McKay later described both nauty and Traces within a common framework and compared their behavior on graph families.[ref]
Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno. Abstract; framework and implementations
Brendan McKay 2026-11-05
Brendan McKay is a researcher in computational graph theory and an emeritus professor at the Australian National University. His institutional homepage identifies nauty as software for graph isomorphism and graph automorphisms.[ref]
Brendan McKay homepage at Australian National University. Biographical heading and Software
A graph automorphism is a relabeling that preserves adjacency within a graph. For an original cycle on four vertices, choose the image of one vertex in4 ways and then choose which of its two neighbors receives the next vertex in2 ways. The remaining images are forced, givingThese relabelings form a group. Computing such symmetries can avoid repeating equivalent branches of a structural search.
Graph canonical labeling addresses a complementary problem: assign a representative encoding so that isomorphic graphs receive the same canonical result. This makes it possible to compare structures whose input vertex names differ or to remove duplicate generated graphs. McKay's work on nauty made these tasks practical for many graph classes.
With Adolfo Piperno, he described the mathematical basis of individualization-refinement graph search and the implementations in nauty and Traces graph isomorphism software. Their paper connects the validity of the search framework with performance comparisons, while distinguishing the practical algorithms from a general worst-case efficiency claim.[ref]
Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno. Introduction, refinement-individualization framework and program comparisons
Canonical graph labeling 2026-11-05
Canonical graph labeling computes a standardized labeled representative of a graph, with a fixed convention that assigns identical representatives exactly to isomorphic graphs. For finite graphs, a labeling is a bijection from the original vertices to a standard set such as . A canonicalization procedure chooses a representative adjacency structure, not simply the order in which vertices happened to be supplied.
One explicit convention labels a finite undirected simple graph in every possible way and chooses the lexicographically least upper-triangular adjacency matrix string. The article complete graph invariant proves that this representative, together with vertex count, determines the graph up to graph isomorphism. Efficient software seeks the same kind of isomorphism-invariant representative without literally enumerating every permutation. The authors' nauty and Traces project identifies canonical labeling and graph-automorphism computation as supported tasks.[ref]
nauty and Traces by Brendan McKay and Adolfo Piperno. project overview and Documentation
An original three-vertex path makes a subtle distinction visible. In the edge-string order , the least string is . It puts the central vertex at label3 and the two leaves at labels1and2. Either assignment of the two original leaves gives the same canonical adjacency matrix. The representative is fixed, while the map from original vertices to labels need not be unique.
This ambiguity is forced by graph automorphisms. If an automorphism exchanges two indistinguishable vertices, no injective vertex-naming rule can both remain unchanged by that exchange and give the two vertices different names. More formally, requiring for every automorphism forces whenever is injective. A graph with a nontrivial automorphism therefore cannot have fully symmetry-invariant distinct names for all original vertices.
Canonical graph labeling instead requires the resulting labeled graph to be invariant under relabeling of the input. A returned vertex permutation may select one among equivalent choices. For a triangle, all six labelings give the same adjacency matrix, while six different input-to-label maps remain possible.
Vertex colors, directed edges or other attributes must be included in the structure if the desired isomorphisms are to preserve them. Comparing outputs from different canonicalization conventions or program options also needs care: identical invariance goals do not require every implementation to choose the same representative.
Cayley graph Created 2026-09-24 Updated 2026-10-14
A Cayley graph turns multiplication in a group into travel: the chosen generators of a group are the allowed one-step moves, and a word over an alphabet becomes a route. This lets us study a finitely generated group using graph distances, closed balls, and geodesics, rather than only equations between products.
Let be a group with a finite generating set of a group satisfying and . Such a symmetric subset of a group includes the inverse element of every allowed move. The Cayley graph has vertex set and joins to for each . We choose right multiplication for these moves. Reversing the move uses , so for graph distance we regard and as the two orientations of one undirected edge. An involution therefore gives one edge, not two parallel edges. Each edge has length one, regardless of its length in a drawing.[ref]
A sequence labels the walkIt ends at exactly when . Thus the Cayley graph is a connected graph precisely because generates , and its graph distance on vertices is the word metric. Left multiplication by sends the edge from to to the edge from to , preserving its generator label: this is a group action by graph automorphisms and isometries. Viewing groups as symmetries of geometric objects is the motivation of Clay and Margalit's introduction.[ref]
The useful geometric object includes its allowed moves, not just its drawing. Cayley graphs of the integers show how changing the moves adds shortcuts; word metric balls in the integer lattice show how the same group can acquire visibly different closed balls. Meier's book develops this passage from group operations to graphs as its central motivation.[ref]
https://api.pageplace.de/preview/DT0400.9780511421594_A23678234/preview-9780511421594_A23678234.pdf. Meier, Groups, Graphs and Trees, Preface and Chapter 1 introduction
Colour refinement 2026-11-05
Colour refinement repeatedly separates vertices of a graph according to the colours of their neighbours. Its colours are labels for classes of vertices with the same currently visible structure; they are not a proper vertex colouring requiring adjacent vertices to differ. In individualization-refinement graph search, colour refinement reduces ambiguity before the algorithm branches.[ref]
Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno. Section3.1, equitable refinement and Algorithm1
Let be a vertex's colour after round . One conceptual update assigns a common new colour exactly when both the previous colour and neighbour-colour multiset agree:The encoding must give distinct labels to distinct signatures. Retaining prevents old classes from merging. When no class splits, the resulting partition of a set is an equitable partition: vertices in the same cell have equal numbers of neighbours in every cell.
For an original example, start all vertices of the six-vertex path graph with the same colour. The first round separates endpoints from internal vertices . The next separates , which each have an endpoint neighbour, from , which do not. The three cellsare then stable. Reflection of the path exchanges the two vertices in each cell, so the remaining pairs are compatible with a genuine graph automorphism.
Colour refinement is invariant under vertex relabeling. To compare two graphs, colour signatures must be encoded consistently across both, for example by refining their disjoint union of graphs with shared initial colour meanings. A different count of vertices in a resulting colour class certifies graph non-isomorphism.
Agreement is weaker than isomorphism. Starting with one colour, both the complete bipartite graph and the triangular prism graph remain one six-vertex cell because every vertex has three neighbours. Yet the prism has triangles and has none. This failure motivates individualizing vertices and searching further; stable colour classes are not, in general, proof that all their vertices are related by graph automorphisms.
Distance-transitive action on a graph 2026-10-14
A subgroup of the graph automorphism group acts distance-transitively when it is transitive on the ordered pairs of vertices at each fixed graph distance. Thus two vertex pairs at the same distance can be matched by one automorphism from that subgroup. Existence of such a subgroup implies that the full automorphism group has the same property, making the graph a distance-transitive graph. The specified subgroup need not be the entire automorphism group.
Equitable partition 2026-11-05
An equitable partition of a finite graph groups vertices so that any two vertices in one cell have the same number of neighbours in each cell. For a simple graph with cells , this means that numbersdo not depend on which in is selected. Here denotes the set of neighbours of . These counts form the equitable quotient matrix . An equitable partition need not be a proper vertex colouring and need not have cells of equal sizes.[ref]
Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno. Section3.1 and footnote1, equitable-partition terminology
An original five-vertex path graph has an equitable partitionEach endpoint has one neighbour in ; each member of has one neighbour in and one in ; the middle vertex has two neighbours in . Although the graph is undirected, is not symmetric matrix, because its entries count neighbours per vertex rather than total edges between cells. Counting those edges from both ends gives .
The counts also compress an exact part of the adjacency matrix. Let be that matrix and let have one column per cell, with for and zero otherwise. ThenIndeed, counts neighbours of in , which is exactly . Hence implies . Since nonempty disjoint cells make the columns of linearly independent, gives : every eigenvalue of is an eigenvalue of . For the displayed example, these include and .
An equitable partition preserves neighbour counts, not all adjacency information. The disjoint union of graphs of a triangle and a four-vertex cycle has an equitable one-cell partition, since every vertex has two neighbours. Nevertheless, no graph automorphism can send a triangle vertex to a four-cycle vertex: their connected components of a graph are not isomorphic. This distinguishes equitable cells from symmetry orbits and explains why colour refinement may leave ambiguity.
Graph adjacency Created 2026-10-14 Updated 2026-10-14
Two vertices of a graph are adjacent if an edge joins them. A graph automorphism preserves this relation in both directions. In an intersection graph, adjacency can be defined by a prescribed dimension or cardinality of an intersection, so any ambient symmetry preserving that statistic acts by graph automorphisms.
Individualization-refinement graph search 2026-11-05
Individualization-refinement graph search explores possible vertex labelings while repeatedly distinguishing vertices by their adjacency structure. It combines inexpensive colour refinement with branching when refinement leaves indistinguishable vertices. This is a framework for canonical graph labeling and graph automorphism computation, rather than a claim that degree information alone decides graph isomorphism.[ref]
Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno. Sections2.3–2.4, search tree and canonical forms; §3.1, refinement
Start with an ordered partition of a set of the vertex set, representing any prescribed vertex colours. Within each cell, compare the number of neighbours each vertex has in every current cell. Split a cell whenever those count vectors differ, and repeat until no further split occurs. The result is an equitable partition. A discrete partition of a set, with one vertex per cell, gives a candidate vertex ordering.
If a cell still has several vertices, choose a target cell by a rule preserved under relabeling. For each possible chosen vertex in that cell, make that vertex a singleton, refine again and continue recursively. The leaves provide candidate encodings of the adjacency matrix. Choosing a fixed extremal encoding over the complete search gives a canonical representative. Implementations use valid node invariants and discovered graph automorphisms to prune branches without changing the result.[ref]
For an original example, label a six-vertex cycle graph temporarily as , with adjacency modulo6. Starting with one cell, every vertex has two neighbours, so colour refinement alone leaves one cell. Individualizing vertex0and refining givesVertices1and5remain indistinguishable because reflection fixing0exchanges them. Individualizing one of them resolves the remaining pairs. The temporary names explain the search; they cannot be used as invariant tie-breakers that silently discard the other possible labeling.
By contrast, two disjoint triangles also begin with six vertices of degree2, but after individualizing one vertex the refined cell sizes are1,2,3. The cycle's sizes are1,2,2,1. Thus this branch detects structure that initial degree refinement misses. Highly symmetric graphs can still require extensive search; refinement is a reduction of the search space, not a universal small bound on it.
nauty 2026-11-05
nauty is software for computing graph automorphisms and canonical graph labeling, originally developed by Brendan McKay. It is distributed with Traces graph isomorphism software and auxiliary graph-generation and manipulation tools.[ref]
nauty and Traces by Brendan McKay and Adolfo Piperno. Summary; Documentation; original and current algorithm references
An automorphism result describes relabelings that preserve adjacency. For an original example, the graph with6vertices and no edges permits every vertex permutation, so its automorphism group is the symmetric group of orderA compact generator description can use a transposition and a cycle . Conjugating the transposition by powers of the cycle produces adjacent transpositions, which generate the whole symmetric group. These are illustrative generators, not a claim about the exact generator list returned by a particular run.
A canonical result serves another purpose. If denotes the chosen canonical graph encoding, correctness requiresRenaming vertices changes the input representation but must not change that chosen result. This permits duplicate elimination when generating graphs and comparison of structures supplied with unrelated labels.
nauty combines structural refinement with a search over unresolved choices, exploiting discovered graph automorphisms to reduce equivalent work. Its theoretical framework and relationship to Traces are described in the authors' joint paper.[ref]
Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno. Introduction and individualization/refinement framework
A generating set for symmetries and a canonical encoding are different outputs. The first describes equivalences within a graph; the second makes equivalence between independently labeled graphs directly testable.
Equality in Harper theorem need not make a down-set a cube-automorphic image of a simplicial initial segment. In , take all sets of size at most one and the four two-element sets forming a four-cycle. This family has size nine and closed graph neighbourhood size fifteen, just like the size-nine simplicial order on the discrete cube initial segment. The induced degree of a vertex distributions differ, so they cannot be related by a graph automorphism.
Enumerate the vertices as and introduce a Boolean variable for each ordered pair of vertices. Its intended meaning is that a proposed graph automorphism sends to . Build four groups of Boolean clauses.
First require exactly one image for each vertex:Next require that distinct vertices have distinct images:Together and specify an injective function . Since is finite, this function is a bijection; a separate surjectivity condition is unnecessary.
Write when and otherwise. Prohibit every pair of images that would change adjacency:Checking both possible mismatches preserves both edges and nonedges. Finally require a moved vertex:The desired propositional formula is
If a Boolean valuation satisfies , selects a unique image for every vertex, makes the resulting function a bijection, preserves adjacency in both directions, and makes this graph automorphism different from the identity function. Conversely, given such a graph automorphism , set true exactly when . Each of is then satisfied.
There are Boolean variables, image and injectivity Boolean clauses, and at most adjacency Boolean clauses. With the graph stored by its adjacency matrix, testing a mismatch takes constant time. Thus the construction has polynomial time and output length with binary-indexed variable names. For , interpret the empty logical disjunction as false; for , and conflict. These cases correctly have no nonidentity graph automorphism.
Past exam of the mathematics course of the University of Cambridge 2003 iii Paper 30 4 c Solution Created 2026-10-03 Updated 2026-10-14
Let and . This connection event is the union over of . The union bound therefore supplies a graph vertex with connection probability at least .
Every boundary graph vertex has some coordinate equal to or . By applying a permutation and a graph automorphisms, which preserve both the law and the boundary, choose such a graph vertex in the form while retaining its probability bound. Now is a reflection of . Translation and reflection invariance givePositive association of random variables applied to the two connection events, whose intersection implies , proves the reflection comparison of random-cluster connections:Also , since any path to meets the box boundary. Consequentlyand henceHere , so . Both outside logarithmic connection rates converge to by part (b). Squeezing gives the rate for every box size, and therefore for the requested even subsequence:
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 10 1 Solution 2026-10-14
Identify the discrete cube with the subsets of , with hypercube graph adjacency given by changing one element. Write for the closed graph neighbourhood and for the external vertex boundary. The simplicial order on the discrete cube first orders by set size and then by lexicographic order, with the smallest differing coordinate belonging to the earlier set.
Harper theorem states that, for every set family ,Here is the simplicial section compression proof. Induct on , the one-dimensional case being immediate. Split by a coordinate into sections . Its neighbourhood sections areReplace by equally large simplicial initial segments . By induction . Also the neighbourhood of a simplicial initial segment is itself a simplicial initial segment: at its last occupied level the extra vertices form the upper shadow of a lexicographic initial segment, again lexicographically initial. Consequently the compressed unions have sizes and , no larger than the original unions. The compression preserves and cannot increase .
Repeat in every coordinate until all sections are initial. Every nontrivial compression strictly decreases the sum of the global simplicial positions, so the process terminates. To describe the terminal families for simplicial section compression, suppose an earlier absent vertex precedes a later present vertex . They cannot share a coordinate value: otherwise they lie in the same compressed section, contradicting its initiality. Thus . No vertex can lie strictly between them in the order, since it would make another absent/present pair that is not complementary. Hence the terminal family is either or that segment with its last vertex exchanged for its immediate complementary successor .
For odd , that exceptional exchange crosses the middle levels: and . For , all sets of size at most remain in the neighbourhood after the exchange, since an -set has at least two lower neighbours and only one was removed. The new can only add vertices of size .
For even , the only consecutive complementary pair in one level is and . The original segment contains all sets below size and all -sets containing 1. For , its neighbourhood contains all sets of size at most and all -sets containing 1; every such upper set still has an included lower neighbour after the single removal. The new can only add further neighbours. The cases follow directly, with the exceptional families related to the initial ones by a graph automorphism. Thus neither exception improves the neighbourhood, completing the induction.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 12 2 Solution Created 2026-10-03 Updated 2026-10-14
Take and , as required for the displayed sparse scaling and the later normalization. A strictly balanced graph satisfies for every proper nonempty subgraph . This forces to be connected and to have no isolated vertices: otherwise a component of at least the average density, or deletion of the isolated vertices, violates strict balance. Copies here are subgraphs, not induced subgraphs.
For fixed , the factorial moment counts ordered -tuples of distinct copies all present in the binomial random graph. The contribution of vertex-disjoint copies is exactlyThe factor removes the multiple embeddings of each copy coming from its graph automorphisms. For an overlapping tuple, let be its union. There are placements of each fixed union type, and the probability its edges are present is . When adding a copy meeting the earlier union in vertices and edges, the exponent changes byIt is strictly negative if this intersection is a proper nonempty subgraph, and zero only for an empty intersection or a whole copy. In particular the first vertex-overlapping copy has a proper nonempty intersection: the preceding copies are vertex-disjoint, and a connected copy contained in their union would have to equal one of them, contrary to distinctness. Its contribution is therefore strictly negative; later additions cannot undo that loss. Only finitely many union types occur for fixed , so their total contribution is . We have proved all the factorial moment limits, and the allowed factorial-moment criterion for Poisson convergence givesThis is the Poisson limit for strictly balanced subgraph counts.
The pendant-edge graph has density , whereas its proper core has density . Thus is not strictly balanced. The complete graph is strictly balanced, with 24 graph automorphisms, so at its copy count tends to .
Every copy has a unique four-vertex clique core and one selected edge joining it to a fifth vertex. For any four-set , let count the ambient edges between and its complement. Then , with mean . It is independent of the internal edges determining whether is a clique. Choose . A Chernoff bound and a union bound giveTherefore, simultaneously for every actual core, its number of pendant extensions is . Extra ambient edges cause no overcount: each selected seven-edge subgraph has exactly one core and one pendant edge. Summing over the cores yieldsbecause is uniformly tight. This is the pendant extensions of sparse clique copies mechanism. For , neither endpoint of is an integer, and its only nonnegative integer is . Convergence in distribution consequently givesThe positive- assumption matters: the quotient printed in the question is undefined when .
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 15 3 ii Solution Created 2026-10-03 Updated 2026-10-14
We first specify the standard hypotheses of percolation uniqueness on an amenable quasi-transitive graph. A locally finite graph has finite degree at every vertex; a quasi-transitive graph, or graph of finite type, has finitely many vertex orbits under the acting group of graph automorphisms. Here the site percolation law is invariant under and independent, with one parameter for each orbit. Initially suppose . This gives the finite-energy property of Bernoulli percolation: conditional on all states outside any finite set, every assignment inside that set has positive probability. An amenable graph has finite sets with , where denotes the external vertex boundary. Finite type bounds the degrees uniformly, so internal and external boundary conventions are equivalent here.
Let be the number of infinite percolation clusters, taking values in . Each event is invariant. Part (i), together with countability of these possibilities, shows that is an almost-sure constant.
Suppose first that this constant is a finite integer . Some finite connected set meets all infinite percolation clusters with positive probability, since increasing finite sets exhaust the graph. Make every vertex of open. This joins all the infinite clusters. Opening a finite set cannot produce a new infinite cluster from finite clusters: only finitely many clusters meet its finite boundary, and their finite union is finite. By the finite-energy property the modified event has positive probability, contradicting the almost-sure value . Thus a finite must be or .
Suppose instead that almost surely. Some finite connected set meets three distinct infinite percolation clusters with positive probability. Open all of . Its vertices belong to one open cluster, and deleting from that cluster leaves at least three infinite components. This is an encounter box in percolation. We use boxes rather than assume that the local geometry permits a single trifurcation vertex in percolation.
Here is the boundary-counting contradiction in detail. Translates of have the same positive encounter probability. Finite type and bounded degree allow a deterministic packing of mutually disjoint such translates whose centers have positive lower density in the interiors of the Følner sets : every vertex is within a fixed distance of one chosen orbit, and a bounded-radius greedy packing discards only a bounded number of possible centers per chosen center. Boundary layers of any fixed thickness have size . The expected number of encounter boxes wholly inside is consequently at least for a fixed and all large .
On the other hand, contract the open encounter boxes in each cluster to vertices and retain the part inside . Each contracted encounter box separates at least three branches that run to infinity, and each branch must leave . Choose a minimal forest connecting all these boundary exits. Every encounter junction has degree at least three in that forest: its three infinite branches remain in different components after deleting the junction, so none can be omitted. The leaves are boundary exits. For each nontrivial tree, the degree-sum identity gives at most the number of leaves minus two vertices of degree at least three. Thus the number of encounter boxes is at most a constant times , where the constant accounts for the bounded boundary degrees. Taking expected values contradicts amenability. This excludes and provesThere is a genuine endpoint qualification if different orbit parameters are allowed to be or . Subdivide each horizontal edge of the square lattice once. Open every original vertex deterministically and close every new midpoint deterministically. This is an invariant independent law on an amenable graph that is also a quasi-transitive graph, but its infinite open clusters are the distinct vertical columns. Thus the finite-energy property must be included when interpreting a general vector . The homogeneous endpoint laws themselves cause no problem: they give zero or one infinite cluster.
The conclusion is false for -independent laws, even with all site marginals equal to . Here is a fully specified monochromatic line-graph percolation counterexample. Form a graph by replacing each vertex of by a complete graph on ten vertices and putting every possible edge between the blocks of two neighboring lattice vertices. Every vertex of has degree . The graph is connected, periodic and amenable: a square of blocks has volume of order and boundary of order . Assign independent fair red/blue colors to the vertices of .
Call a block good when it contains both colors. Good-block indicators are independent, withThey percolate. To verify this without presupposing a site threshold, put . A finite nearest-neighbor good-block cluster around a good origin is surrounded by a circuit of bad blocks in the matching square graph, where horizontal, vertical and diagonal neighbors are allowed. A surrounding circuit of length has an anchor within . Overcounting its choices by gives the Peierls argumentThe sum bound follows directly from , with . An infinite good-block cluster therefore exists with positive probability, and by part (i) it exists almost surely. Inside each of its blocks the red vertices are connected to one another, as are the blue vertices; between adjacent good blocks the complete bipartite joining edges connect each color. Hence has both an infinite red component and an infinite blue component almost surely.
Now use site percolation on , the line graph of : its vertices are the edges of , two adjacent when they share an endpoint. Declare such a site open exactly when have the same color. Each site has open probability . Sets of sites at graph distance greater than one involve disjoint sets of underlying color variables, so this is a translation-invariant -independent law. The line graph is again connected, locally finite, amenable and of finite type. The infinite red and blue components of yield infinite open clusters in . An open path in cannot change color at a shared endpoint, so those two clusters are distinct. Thus almost surely. Local color constraints destroy the finite-energy property, precisely the ingredient missing from the uniqueness proof.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 15 3 i Solution Created 2026-10-03 Updated 2026-10-14
Independence or another ergodicity hypothesis is necessary. Read literally for an arbitrary translation-invariant site percolation measure, the assertion is false: the mixture assigning probability to the all-open configuration and to the all-closed configuration is translation-invariant, but the invariant event of an infinite percolation cluster has probability . We prove the zero–one law for the invariant independent law used in part (ii); the proof also works for the stated finite-range independent alternative.
Let be the group of translations, or the specified group of graph automorphisms, and let be invariant under it, up to null sets. An event determined by the states in a finite vertex set is a cylinder set. For every , approximation in the product sigma-algebra provides a cylinder set , supported on a finite set , with . Choose so that and are disjoint. Then and are independent events, have equal probabilities, and . HenceandLetting proves the zero–one law . This is translation ergodicity of Bernoulli percolation.
For a quasi-transitive graph, the required displacement exists: put in a ball about a vertex ; its orbit is infinite, so an automorphism can move , and therefore that whole ball, beyond any prescribed finite neighborhood. A -independent site percolation law means that the sigma-algebras generated by vertex sets at graph distance greater than are independent. Move far enough that and the same proof applies. Thus finite-range independence does give the zero–one law, although it will not give uniqueness.
Past exam of the mathematics course of the University of Cambridge 2010 iii Paper 4 4 iv Solution Created 2026-10-03 Updated 2026-10-14
The Grassmann graph is connected, and its distance can be determined directly. Put , , and . Choose vectors so thatThe vectors of a basis of , followed by all the and , are independent: a relation would identify a vector in the two chosen complements modulo , contradicting . For defineEach successive pair has an intersection of dimension . Thus and are joined by a path of length .
For the lower bound, if two vertices are adjacent, their common vector subspace has codimension one in each. Both and lie between and . Thus one edge can change the dimension of the intersection with by at most one. It must change from to along a path from to , requiring at least edges. Therefore
If two ordered pairs have equal distance, their intersections have equal dimension. Construct adapted bases for each pair as above and extend both to bases of the ambient vector space. The invertible linear map between them sends the first ordered pair to the second. It preserves intersection dimensions, so it is a graph automorphism. This proves that the Grassmann graph is distance-transitive, with the required simultaneous images. Its diameter is , because permits two disjoint -dimensional vector subspaces.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 10 3 Solution Created 2026-10-03 Updated 2026-10-07
Identify the hypercube graph with , joining two sets when their symmetric difference has size one. Write for the closed graph neighbourhood of , and for its radius- neighbourhood in Hamming distance. In the simplicial order on the discrete cube, smaller sets come first, with lexicographic order within each rank: the smallest differing coordinate belongs to the earlier set. Let be the first vertices in this order. Harper theorem isEquivalently, minimizes the external vertex boundary at fixed size. We will also obtain for every integer .
Here is a complete proof by simplicial section compression. First note two properties of the simplicial order on the discrete cube. Its restriction to either face obtained by fixing one coordinate is the corresponding order on the smaller hypercube graph. Also, the closed graph neighbourhood of an initial segment is an initial segment. To verify the latter, a nonempty initial segment contains every level below its last level , and a lexicographic prefix at level . For , its closed graph neighbourhood contains every set of size at most , and its only further members are the upper shadow of . An -set lies in this upper shadow exactly when its lexicographically earliest -subset lies in . That earliest subset is obtained by deleting the largest element. These earliest subsets vary monotonically in lexicographic order, so the upper shadow is another lexicographic prefix. For , the closed graph neighbourhood of is the union of levels zero and one. The empty initial segment causes no exception.
Induct on , with immediate. Fix a coordinate and write the sections of as , deleting from the latter section. Replace them by the initial segments with , . The sections of the old closed graph neighbourhood areBy induction their sizes are at least and , respectively. These are exactly the sizes of the new sections, because both sets in each new union are initial segments and hence nested. Thus simplicial section compression preserves size and never enlarges the closed graph neighbourhood.
Repeatedly compress any section that is not already an initial segment. Every change strictly reduces the sum of the global simplicial positions of the included vertices. This nonnegative integer decreases only finitely often, so the process ends at a family whose sections in every coordinate are initial segments. If itself is an initial segment, the induction is complete. Otherwise choose the earliest absent vertex and the latest present vertex , with . They cannot agree in any coordinate: agreement would put them in one compressed section, where an earlier absent vertex cannot precede a later present one. Hence . Nor can a vertex lie between them: if is present, pairing it with would force ; if absent, pairing it with would force . Thus are consecutive, and is obtained from by replacing its last vertex with the next vertex .
There are only two possibilities for these terminal families for simplicial section compression. If , consecutiveness makes the last -set and the first -set. Complementarity forces , and . For , the corresponding contains all sets of size at most except , and additionally . Every -set has at least two -subsets, so at least one belongs to . The missing has a -subset in . Consequently contains every set of size at most , which is exactly .
If , then . Since are complementary, the smaller one contains coordinate . Consecutiveness forces to be the last -set containing , and the first -set avoiding :The initial segment consists of all sets of size less than and all -sets containing . Its closed graph neighbourhood contains all sets of size at most and all -sets containing . For , each such -set has -subsets containing , so removing only leaves one in . All sets of size at most are still in , because all levels below belong to . Hence again . For , the two families are related by exchanging coordinates and both have the whole as their closed graph neighbourhood. These comparisons finish the induction and prove Harper theorem.
For the radius- version, repeatedly use the one-step result. At each step the comparison family remains an initial segment, and its closed graph neighbourhood is monotone in its size. If , applying Harper theorem to therefore gives . Induction on proves the asserted extension.
A Lévy family of graphs has vanishing concentration of measure functions after distances have been scaled by the graph diameter. More explicitly, for connected finite graphs of diameter , use normalized graph distance and uniform probability measure. For every fixed , requireFor this normalization is normalized Hamming distance , since its diameter is .
If , the corresponding initial segment contains the Hamming ball about of radius . The radius- version of Harper theorem impliesUse the precise Hoeffding inequality for . One can also derive this estimate directly: the moment-generating function of is ; the exponential Markov inequality followed by minimization at gives the bound. With , we have . Thus, whenever ,This proves that the hypercube graphs form a Lévy family of graphs. The stronger fixed-positive-mass formulation follows as well. For any , choose with . The Chebyshev inequality for , whose variance is , makes the Hamming ball of radius have fewer than vertices. An initial segment of size at least contains that ball. Enlarging by and using the same Hoeffding inequality gives a complement proportion tending to zero uniformly over all such . The normalization matters: with unscaled unit Hamming distance, cubes do not satisfy the metric version at every fixed radius; for a radius below one, a half-cube has no enlargement.
Equality in Harper theorem does not determine a down-set up to isomorphism. In , takeThis is a down-set of size nine. Its closed graph neighbourhood contains every set of size at most two, because all singletons belong to . Every triple contains an edge of the four-cycle among the listed pairs, so every triple also belongs to . The four-element set does not. Hence .
The size-nine simplicial order on the discrete cube initial segment is all sets of size at most one together with the pairs . Every triple contains one of these pairs, and the four-element set is again absent from its closed graph neighbourhood. Its neighbourhood therefore also has size , proving extremality of . Nevertheless the induced graphs are not isomorphic: in , the empty set has degree four, the four singletons have degree three, and the four pairs have degree two. The initial segment has two vertices of degree four, namely and . Since a graph automorphism preserves induced degree of a vertex, no automorphism of the cube can carry one family to the other. This gives nonunique down-set extremizers for Harper theorem even under the stronger test of induced graph isomorphism.
Past exam of the mathematics course of the University of Cambridge 2018 ib Paper 2 20H ii Solution Created 2026-09-24 Updated 2026-10-03
Let be the expected hitting time from any neighbour of the origin back to the origin. After the first step, the return-time calculation from part (i) givesso . Translation by the target vertex is a graph automorphism of the hypercube that exchanges the origin and that adjacent vertex, so the reverse expected hitting time is the same. Hence