This is joint work with Vladislav Kabanov, Leonid Shalaginov and Alexandr Valyuzhenich.

Many combinatorial configurations (for example, perfect codes, latin squares and hypercubes, combi-
natorial designs and their q-ary generalizations — subspace designs) can be defined as an eigenfunction on a graph with some discrete restrictions. The study of these configurations often leads to the question about the minimum possible difference between two configurations from the same class (it is often related with bounds of the number of different configurations; for example, see [1–5]). Since the symmetric difference of these two configurations is also an eigenfunction, this question is directly related to the minimum cardinality of the support (the set of nonzero) of an eigenfunction with given eigenvalue. This talk is devoted to the problem of finding the minimum cardinality of the support of eigenfunctions in the Paley graphs of order q^2 (denote it by P(q^2)), where q is prime power. Currently, a similar problem is solved for Hamming graphs H(n, q) for q = 2 (see [4]). In [6] Vorob’ev and Krotov proved the lower bound on the cardinality of the support of an eigenfunction of the Hamming graph. In [7] the minimum cardinality of the support of eigenfunctions in the Hamming graphs with the second largest eigenvalue n(q − 1) − q was found.

In this talk, we present construction of eigenfuctions on P(q^2) for both non-principal eigenvalues; the cardinality of the support of the eigenfunctions is equal to q + 1. It follows from [3], that our construction gives eigenfunctions with minimum cardinality of support. As a related topic, we will discuss maximal cliques in P(q^2) of order (q + 1)/2 and (q + 3)/2, where q ≡ 1(4) and q ≡ 3(4), correspondingly. In [8], Baker, Ebert, Hemmeter and Woldar proposed contruction of such cliques, but they noted that their construction doesn’t cover all known cliques.

References

[1] E. F. Assmus, Jr and H. F. Mattson. On the number of inequivalent Steiner triple systems. J. Comb. Theory, 1(3):301-305, 1966.

[2] O. Heden and D. S. Krotov. On the structure of non-full-rank perfect q-ary codes. Adv. Math. Commun., 5(2):149-156, 2011.

[3] D. Krotov, I. Mogilnykh, V. Potapov. To the theory of q-ary Steiner and other-type trade. Discrete Mathe-
matics. 2016. V. 339, N 3. P. 1150-1157.

[4] V. N. Potapov. On perfect 2-colorings of the q-ary n-cube, Discrete Math., 2012, V. 312, N. 8, 1269-1272. [5] V. N. Potapov and D. S. Krotov. On the number of n-ary quasigroups of finite order. Discrete Math. Appl., 21(5-6):575-585, 2011.

[6] K. V. Vorob’ev and D. S. Krotov. Bounds for the size of a minimal 1-perfect bitrade in a Hamming graph. J. Appl. Ind. Math., 9(1):141-146, 2015. translated from Diskretn. Anal. Issled. Oper. 6(21):3-10, 2014.

[7] A. Valyuzhenich. Minimum supports of eigenfunctions of Hamming graphs. Accepted to Discrete Mathemat-
ics.

[8] R. D. Baker, G. L. Ebert, J. Hemmeter, A. J. Woldar. Maximal cliques in the Paley graph of square order. J. Statist. Plann. Inference 56 (1996) 33-38.