Abstract
The symmetry of a circle is easily destroyed: just ``individualize'' two non-opposite points -- color one of them red, the other blue -- and all the symmetry is gone. In fact, the resulting structure is completely irregular: every point is uniquely identified by a pair of numerical invariants, namely, its pair of distances to the two individualized points. We shall say that the circle has a high degree of hidden irregularity.
In contrast, Johnson graphs are objects with robust symmetry: individualizing a small number of vertices of a Johnson graph hardly makes a dent in its symmetry.
It turns out that Johnson graphs are unique in this regard: Every finite relational structure of small arity either has a measurable (say 10%) hidden irregularity (exposed by individualizing a small number of elements) or has a high degree of hidden structure, manifested in a canonically embedded Johnson graph on more than 90% of the underlying set.
This dichotomy provides the combinatorial Divide-and-Conquer tool to recent progress on the complexity of the Graph Isomorphism problem.