Distance in a Johnson graph

ID: distance-in-a-johnson-graph

One edge of a Johnson graph replaces one element of a -subset, so it can increase intersection with a fixed target by at most one. Replacing each element outside the target by one missing target element gives a path reaching this lower bound. Equal-distance ordered pairs have equal sizes of intersection, the two differences and the remaining ground set; a permutation matching these four regions proves distance transitivity.

New to topics? Read the docs here!