Page 294 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 294
GRAPHS AND GROUPS, GEOMETRIES AND GAP - G2G2 (MS-7)
holds for any its vertex x, where N (x) is the neighborhood of x in Γ.
The Star graph Sn, n ≥ 2, is known to be integral (see [3]), and its spectrum consists of all
integers in the range from −(n − 1) to n − 1 (except 0 when n = 2, 3). Despite of the fact that
spectral properties of the Star graph were studied (see [1, 3, 3, 5]), no explicit construction for
the eigenfunctions was known.
In [4], an explicit construction of eigenfunctions of Sn, n ≥ 3, for all eigenvalues θ with
n−2 < θ < n − 1 was presented.
2
In this work, we generalize ideas from [4] and present eigenfunctions of the Star graph Sn,
n ≥ 3, for all its non-zero eigenvalues.
The work is supported by Mathematical Center in Akademgorodok under agreement No.
075-15-2019-167 with the Ministry of Science and Higher Education of the Russian Federation.
References
[1] A. Abdollahi, E. Vatandoost, Which Cayley graphs are integral? The Electronic Journal
of Combinatorics, 16 (2009) 6–7.
[2] G. Chapuy, V. Feray, A note on a Cayley graph of Symn, arXiv:1202.4976v2 (2012) 1–3.
[3] J. Friedman, On Cayley graphs on the symmetric group generated by transpositions, Com-
binatorica 20(4) (2000) 505–519.
[4] S. Goryainov, V. V. Kabanov, E. Konstantinova, L. Shalaginov, A. Valyuzhenich, P I-
eigenfunctions of the Star graphs, Linear Algebra and its Applications 586 (2020 7–27.
[5] R. Krakovski, B. Mohar, Spectrum of Cayley graphs on the symmetric group generated
by transposition, Linear Algebra and its Applications, 437 (2012) 1033–1039.
On spectral properties of the Star graphs
Ekaterina Khomiakova, ekhomnsu@gmail.com
Novosibirsk State University, Russian Federation
The Star graph Sn, n 2, is the Cayley graph over the symmetric group Symn generated by
transpositions swapping the ith element of the permutation with the first one. It is a connected
bipartite (n − 1)-regular graph of order n!, and diameter diam(Sn) = 3(n−1) [1].
2
In 2012, R. Krakovski and B. Mohar [7] proved that the spectrum of Sn contains all integers
in the range from −(n − 1) up to n − 1. Since the Star graph is bipartite, the spectrum is
symmetric and multiplicities of eigenvalues of (n − k) and −(n − k) are equal for each integer
1 k < n. Furthermore, ±(n − 1) are simple eigenvalues of Sn. At the same time, G. Chapuy
and V. Feray [3] showed that the spectrum of the Star graphs is equivalent to the spectrum of
Jucys-Murphy elements in the algebra of the symmetric group. This connection between two
kinds of spectra implies that the Star graph is integral.
In 2016, S. V. Avgustinovich, E. N. Khomyakova and E. V. Konstantinova [2] suggested a
method for getting explicit formulas for multiplicities of eigenvalues ±(n − k) and presented
such formulas for 2 k 5. Moreover, an asymptotic lower bound was obtained. It was
proved that for a fixed integer eigenvalue of Sn, its multiplicity is at least 21 n log n(1−o(1)) for
2
sufficiently large n. In 2018, E. N. Khomyakova [6] investigated the behavior of the eigenvalues
292
holds for any its vertex x, where N (x) is the neighborhood of x in Γ.
The Star graph Sn, n ≥ 2, is known to be integral (see [3]), and its spectrum consists of all
integers in the range from −(n − 1) to n − 1 (except 0 when n = 2, 3). Despite of the fact that
spectral properties of the Star graph were studied (see [1, 3, 3, 5]), no explicit construction for
the eigenfunctions was known.
In [4], an explicit construction of eigenfunctions of Sn, n ≥ 3, for all eigenvalues θ with
n−2 < θ < n − 1 was presented.
2
In this work, we generalize ideas from [4] and present eigenfunctions of the Star graph Sn,
n ≥ 3, for all its non-zero eigenvalues.
The work is supported by Mathematical Center in Akademgorodok under agreement No.
075-15-2019-167 with the Ministry of Science and Higher Education of the Russian Federation.
References
[1] A. Abdollahi, E. Vatandoost, Which Cayley graphs are integral? The Electronic Journal
of Combinatorics, 16 (2009) 6–7.
[2] G. Chapuy, V. Feray, A note on a Cayley graph of Symn, arXiv:1202.4976v2 (2012) 1–3.
[3] J. Friedman, On Cayley graphs on the symmetric group generated by transpositions, Com-
binatorica 20(4) (2000) 505–519.
[4] S. Goryainov, V. V. Kabanov, E. Konstantinova, L. Shalaginov, A. Valyuzhenich, P I-
eigenfunctions of the Star graphs, Linear Algebra and its Applications 586 (2020 7–27.
[5] R. Krakovski, B. Mohar, Spectrum of Cayley graphs on the symmetric group generated
by transposition, Linear Algebra and its Applications, 437 (2012) 1033–1039.
On spectral properties of the Star graphs
Ekaterina Khomiakova, ekhomnsu@gmail.com
Novosibirsk State University, Russian Federation
The Star graph Sn, n 2, is the Cayley graph over the symmetric group Symn generated by
transpositions swapping the ith element of the permutation with the first one. It is a connected
bipartite (n − 1)-regular graph of order n!, and diameter diam(Sn) = 3(n−1) [1].
2
In 2012, R. Krakovski and B. Mohar [7] proved that the spectrum of Sn contains all integers
in the range from −(n − 1) up to n − 1. Since the Star graph is bipartite, the spectrum is
symmetric and multiplicities of eigenvalues of (n − k) and −(n − k) are equal for each integer
1 k < n. Furthermore, ±(n − 1) are simple eigenvalues of Sn. At the same time, G. Chapuy
and V. Feray [3] showed that the spectrum of the Star graphs is equivalent to the spectrum of
Jucys-Murphy elements in the algebra of the symmetric group. This connection between two
kinds of spectra implies that the Star graph is integral.
In 2016, S. V. Avgustinovich, E. N. Khomyakova and E. V. Konstantinova [2] suggested a
method for getting explicit formulas for multiplicities of eigenvalues ±(n − k) and presented
such formulas for 2 k 5. Moreover, an asymptotic lower bound was obtained. It was
proved that for a fixed integer eigenvalue of Sn, its multiplicity is at least 21 n log n(1−o(1)) for
2
sufficiently large n. In 2018, E. N. Khomyakova [6] investigated the behavior of the eigenvalues
292
