On two types of cliques related to eigenspaces of strongly regular graphs

We consider graphs without loops and multiple edges. A $k$-regular graph with $n$ vertices is called a strongly regular graph with parameters $(n,k,a,c)$
if any two adjacent vertices have exactly $a$ common neighbours and any two distinct non-adjacent vertices have $c$ common neighbours. We say that $\rho$ is an eigenvalue of a graph $X$ if $\rho$ is an eigenvalue of the adjacency matrix of $X$. A strongly regular graph is called imprimitive if it is a disjoint union of cliques of the same size or a complete multipartite graph with parts of the same size. A strongly regular graph is called primitive if it is not imprimitive.
It is well known that a primitive strongly regular graph has exactly three distinct eigenvalues: the principal eigenvalue $k$ and non-principal eigenvalues $\theta$ and $\tau$, where $\tau < 0 < \theta < k$. On the other hand, a connected regular graph with exactly three distinct eigenvalues is strongly regular (see [GR01, Lemma 10.2.1]).
 
Let $X$ be a primitive strongly regular graph $X$ with degree $k$ and smallest eigenvalue $\tau$. Delsarte proved (see [D73,Section 3.3.2]) that the size of a clique in $X$ is at most $1 - \frac{k}{\tau}$. A clique in a strongly regular graph whose size meets the Delsarte bound is called a Delsarte clique. A clique in a regular graph is called regular if every vertex outside of the clique has the same number of neighbours in the clique. It is well known that a clique in a strongly regular graph is regular if and only if it is a Delsarte clique (see [BCN89, Proposition 1.3.2]). In view of their regularity, Delsarte cliques give rise to equitable 2-partitions (the parts are formed by the vertices of a Delsarte clique and the rest vertices). Equitable 2-partitions of a regular graph can be viewed as eigenfunctions (eigenvectors of the adjacency matrix) having exactly two values, which means that Delsarte cliques also give rise to special eigenfunctions of graphs.

In the first part of the talk, we discuss several results related to Delsarte cliques in special classes of strongly regular graphs. Some of the results are published in [BCGG19], [EGP19] and [AGLY22].

In [KMP16, Corollary 1], a bound (so called weight-distribution bound; WDB for short) on the number of non-zeros of an eigenfunction of a distance-regular graph is given. Applied to a primitive strongly regular graph $X$ with parameters $(n,k,a,c)$ and non-principal eigenvalues $\tau$ and $\theta$, WDB says that a $\tau$-eigenfunction has at least $-2\tau$ non-zeros and a $\theta$-eigenfunction has at least $2(\theta+1)$ non-zeros. Moreover, the tightness of WDB for the smallest eigenvalue of a distance-regular graph is equivalent [KMP16, Corollary 2] to the existence of an isometric distance-regular induced subgraph with certain parameters. In particular, it implies that the tightness of WDB for the smallest eigenvalue $\tau$ of a primitive strongly regular graph is equivalent to the existence of a complete bipartite induced subgraph with parts $T_0$ and $T_1$ of size $-\tau$.  The complement $\overline{X}$ of a primitive strongly regular graph $X$ is a strongly regular graph with non-principal eigenvalues $\overline{\tau} = -(1+\theta)$ and $\overline{\theta} = -(1+\tau)$ such that $\overline{\tau}$-eigenspace and $\overline{\theta}$-eigenspace of $\overline{X}$ coincide with $\theta$-eigenspace and $\tau$-eigenspace of $X$, respectively. This means that the tightness of WDB for the positive non-principal eigenvalue $\theta$ of a primitive strongly regular graph is equivalent to the existence of an induced disjoint union of cliques $T_0$ and $T_1$ of size $1+\theta$. Moreover, the corresponding eigenfunction lying on WDB, up to multiplication by a non-zero constant, is equal to the function with value $1$ on the vertices of $T_0$, value $-1$ on the vertices of $T_1$, and value $0$ otherwise.

In the second part of the talk, we discuss several results on tightness of WDB for some strongly regular graphs. It particular, in [GKSV18] we showed the tightness of WDB for both non-principal eigenvalues of Paley graphs of square order; this result then led us to the discovery of new maximal but not maximum cliques in Paley graphs of square order.

[AGLY22] S. Asgarli, S. Goryainov, H. Lin, C. H. Yip, The EKR-module property of pseudo-Paley graphs of square order,
January 2022. arXiv:2201.03100

[BCGG19] R. A. Bailey, P. J. Cameron, A. L. Gavrilyuk, S. V. Goryainov, Equitable partitions of Latin-square graphs,
Journal of Combinatorial Designs, Volume 17, Issue 3, March 2019, pages 142-160.

[BCN89] A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik
und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18, Springer-Verlag,
Berlin, 1989.

[D73] P. Delsarte, An algebraic approach to the association schemes of coding theory, PhD thesis, Universite Catholique de Louvain, 1973.

[EGP19] R. J. Evans, S. V. Goryainov, D. I. Panasenko, The smallest strictly Neumaier graph and its generalisations,
The Electronic Journal of Combinatorics, 26(2) (2019), #P2.29.

[GKSV18] S. V. Goryainov, V. V. Kabanov, L. V. Shalaginov, A. A. Valyuzhenich, On eigenfunctions and maximal cliques of
Paley graphs of square order, Finite Fields and Their Applications, Volume 52, July 2018, pages 361-369.

[GR01] C. Godsil and G. Royle, Algebraic graph theory, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001.

[KMP16] D. S. Krotov, I. Y. Mogilnykh, V. N. Potapov, To the theory of $q$-ary Steiner and other-type trades,
Discrete Mathematics, 339 (2016), 1150–1157.