The Minimum Number of Cliques in Induced Subgraphs of Johnson Graphs

N. A. Dubinin^a, E. A. Neustroeva^a, A. M. Raigorodskii^abcd, Ya. K. Shubin<sup>a

a</sup> Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region
^b Lomonosov Moscow State University
^c Caucasus Mathematical Center, Adyghe State University, Maikop
^d Buryat State University, Institute for Mathematics and Informatics, Ulan-Ude

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.

Keywords: distance graph, Johnson graph, extremal graph theory.

UDC: 519

MSC: 05D99

Received: 11.09.2024
Revised: 17.05.2025

DOI: 10.4213/mzm14504

 English version: Mathematical Notes, 2025, 118:1, 80–94

Bibliographic databases:

•