Johnson graphs, their random subgraphs, and some of their extremal characteristics

One of the most important objects of study in modern graph theory is the so-called Johnson graph G (n, r, s). The vertices of this graph are all Cₙʳ subsets of cardinality r of the set \1, …, n\, and two vertices are joined by an edge if and only if the intersection of the corresponding subsets has cardinality s. Such graphs play a vital role in coding theory, extremal combinatorics and Ramsey theory, combinatorial geometry, and in other areas. In this survey we give an account of applications of these graphs and of some of their parameters including the independence number, clique number, and chromatic number. We also pay attention to a large part of this theory concerned with investigation of random subgraphs in Johnson graphs, which has actively been developed in recent years. Bibliography: 135 titles.