Abstract
Extremal properties of the Johnson graphs \(G(n,r,s)\) are studied. The vertices of such a graph represent all \(r\) -element subsets of an \(n\) -element set, and two vertices are adjacent if and only if the corresponding subsets intersect in precisely \(s\) elements. The general problem of determining the asymptotic behavior of the minimum number of \(k\) -cliques in \(l\) -vertex subgraphs of \(G(n,r,s)\) is considered. Special attention is paid to the minimum number of triangles, i.e., to the case of \(k=3\) , and to the case of \(r=3\) and \(s=1\) . In the case where \(r=3\) , \(s=1\) , and \(k=2\) , the problem was solved in almost all regimes. In the paper the corresponding theorems are generalized to the case of any constant \(k\) . The asymptotic behavior of the maximum number of vertices in subgraphs of \(G(n,3,1)\) containing no triangles is also determined. This quantity is, in a sense, a generalization of the independence number of a graph.
