A new look at twin reduction

I have just submitted to the arXiv a paper with this title.

The idea was born during an evening walk around the campus of IIT Madras with Arun Kumar. I remarked that I would like to have a method of finding the result of complete twin reduction of a graph without actually going through the process.

Two vertices of a graph are twins if they have the same neighbours, except possibly for one another. Random graphs have no pairs of twins (with high probability); but graphs defined on groups almost always do have them. For example, if x is an element of order greater than 2 in a group G, and y an element generating the same cyclic subgroup as x, then x and y are twins in the generating graph, the commuting graph, the power graph, and many other graphs on G.

I used to think of twin reduction as the following process: find a pair of twins; delete one of them; and repeat until no pairs of twins remain. But now I prefer to think of it as generating a partition Π on the vertex set of the graph Γ. Start with the partition into singletons. Now, at each step, look at the quotient Γ/Π (that is, collapse each part to a single vertex). If there is a pair of twins in this quotient, replace the two parts containing them with a single part. Repeat until no further twins are found. Then the problem arises: how do we characterise the final partition? This is the question I can now answer.

A cograph is a graph not containing the 4-vertex path as an induced subgraph. The class of cographs has many interpretations: one relevant here is that a graph is a cograph if and only if every induced subgraph on more than one vertex contains a pair of twins.

Now I define a sibling partition on the vertex set of a graph to be a partition Π with the following properties:

• the induced subgraph on any part is a cograph;
• between any two parts, either no edges or all possible edges occur.

The main result now asserts that any graph has a unique coarsest sibling partition, and that this partition is the result of complete twin reduction on the graph. The crucial step of the proof is that the join (in the lattice of partitions) of two sibling partitions is a sibling partition. I felt sure that this would be the case; but it was only when I got back to St Andrews and had time to think that I managed to figure out the proof of this. The proof is not entirely trivial, and took me more than a page to write out. (I hope that my conviction that it was true didn’t lead me to produce a dodgy proof!)

A consequence is that the automorphism group G of any graph has a canonical normal subgroup N such that

• N has a normal series in which every quotient is a direct product of symmetric groups;
• G/N is contained in the automorphsim group of a twin-free graph.

Again this theorem is not of much use in random graphs, which almost surely have trivial automorphism group.

I would very much like to find a good application of this result. I suppose that such application will lie in the area of graphs on groups.