Page 302 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 302
PHS AND GROUPS, GEOMETRIES AND GAP - G2G2 (MS-7)
cover.
This research was supported by the Russian Science Foundation under grant no. 20-71-
00122.
Minimum supports of eigenfunctions of graphs
Alexandr Valyuzhenich, graphkiper@mail.ru
Sobolev Institute of Mathematics, Russian Federation
Let G = (V, E) be a graph with the adjacency matrix A(G). The set of neighbors of a vertex
x is denoted by N (x). Let λ be an eigenvalue of the matrix A(G). A function f : V −→ R is
called a λ-eigenfunction of G if f ≡ 0 and the equality
λ · f (x) = f (y)
y∈N (x)
holds for any vertex x ∈ V . In this talk we focus on the following extremal problem for
eigenfunctions of graphs.
Problem 1 (MS-problem). Let G be a graph and let λ be an eigenvalue of G. Find the minimum
cardinality of the support of a λ-eigenfunction of G.
MS-problem was first formulated by Krotov and Vorob’ev [11] in 2014 (they considered
MS-problem for the Hamming graph). During the last six years, MS-problem has been actively
studied for various families of distance-regular graphs [6, 4, 3, 1, 2, 7, 8, 9, 10, 11, 12] and
Cayley graphs on the symmetric group [5]. In particular, MS-problem is completely solved for
all eigenvalues of the Hamming graph [9, 10] and asymptotically solved for all eigenvalues of
the Johnson graph [12]. In this talk we will discuss several new results on MS-problem.
References
[1] E. A. Bespalov, On the minimum supports of some eigenfunctions in the Doob graphs,
Siberian Electronic Mathematical Reports 15 (2018) 258–266.
[2] S. Goryainov, V. Kabanov, L. Shalaginov, A. Valyuzhenich, On eigenfunctions and maxi-
mal cliques of Paley graphs of square order, Finite Fields and Their Applications 52 (2018)
361–369.
[3] V. Kabanov, E. V. Konstantinova, L. Shalaginov, A. Valyuzhenich, Minimum supports
of eigenfunctions with the second largest eigenvalue of the Star graph, The Electronic
Journal of Combinatorics 27(2) (2020) #P2.14.
[4] D. S. Krotov, Trades in the combinatorial configurations, XII International Seminar Dis-
crete Mathematics and its Applications, Moscow, 20–25 June 2016, 84–96 (in Russian).
[5] D. S. Krotov, I. Yu. Mogilnykh, V. N. Potapov, To the theory of q-ary Steiner and other-
type trades, Discrete Mathematics 339(3) (2016) 1150–1157.
[6] E. V. Sotnikova, Eigenfunctions supports of minimum cardinality in cubical distance-
regular graphs, Siberian Electronic Mathematical Reports 15 (2018) 223–245.
[7] E. V. Sotnikova, Minimum supports of eigenfunctions in bilinear forms graphs, Siberian
Electronic Mathematical Reports 16 (2019) 501–515.
300
cover.
This research was supported by the Russian Science Foundation under grant no. 20-71-
00122.
Minimum supports of eigenfunctions of graphs
Alexandr Valyuzhenich, graphkiper@mail.ru
Sobolev Institute of Mathematics, Russian Federation
Let G = (V, E) be a graph with the adjacency matrix A(G). The set of neighbors of a vertex
x is denoted by N (x). Let λ be an eigenvalue of the matrix A(G). A function f : V −→ R is
called a λ-eigenfunction of G if f ≡ 0 and the equality
λ · f (x) = f (y)
y∈N (x)
holds for any vertex x ∈ V . In this talk we focus on the following extremal problem for
eigenfunctions of graphs.
Problem 1 (MS-problem). Let G be a graph and let λ be an eigenvalue of G. Find the minimum
cardinality of the support of a λ-eigenfunction of G.
MS-problem was first formulated by Krotov and Vorob’ev [11] in 2014 (they considered
MS-problem for the Hamming graph). During the last six years, MS-problem has been actively
studied for various families of distance-regular graphs [6, 4, 3, 1, 2, 7, 8, 9, 10, 11, 12] and
Cayley graphs on the symmetric group [5]. In particular, MS-problem is completely solved for
all eigenvalues of the Hamming graph [9, 10] and asymptotically solved for all eigenvalues of
the Johnson graph [12]. In this talk we will discuss several new results on MS-problem.
References
[1] E. A. Bespalov, On the minimum supports of some eigenfunctions in the Doob graphs,
Siberian Electronic Mathematical Reports 15 (2018) 258–266.
[2] S. Goryainov, V. Kabanov, L. Shalaginov, A. Valyuzhenich, On eigenfunctions and maxi-
mal cliques of Paley graphs of square order, Finite Fields and Their Applications 52 (2018)
361–369.
[3] V. Kabanov, E. V. Konstantinova, L. Shalaginov, A. Valyuzhenich, Minimum supports
of eigenfunctions with the second largest eigenvalue of the Star graph, The Electronic
Journal of Combinatorics 27(2) (2020) #P2.14.
[4] D. S. Krotov, Trades in the combinatorial configurations, XII International Seminar Dis-
crete Mathematics and its Applications, Moscow, 20–25 June 2016, 84–96 (in Russian).
[5] D. S. Krotov, I. Yu. Mogilnykh, V. N. Potapov, To the theory of q-ary Steiner and other-
type trades, Discrete Mathematics 339(3) (2016) 1150–1157.
[6] E. V. Sotnikova, Eigenfunctions supports of minimum cardinality in cubical distance-
regular graphs, Siberian Electronic Mathematical Reports 15 (2018) 223–245.
[7] E. V. Sotnikova, Minimum supports of eigenfunctions in bilinear forms graphs, Siberian
Electronic Mathematical Reports 16 (2019) 501–515.
300
