Combinatorics Seminar 2018

Speaker: Elena Konstantinova, Sobolev Institute of Mathematics

Date: Mon, Apr 09, 2018

Time: 14:00 - 15:00

Venue: Middle Meeting Room

Title: Algebraic, combinatorial and structural properties of the Star graphs


Recent progress in investigating algebraic, combinatorial and structural properties of the Star graph $S_n=Cay(\mathrm{Sym}_n,t)$, $n\geqslant 2$, is presented in this talk. The Star graph is the Cayley graph on the symmetric group $\mathrm{Sym}_n$ of permutations with the generating set $t$ of all transpositions swapping the $1$st and $i$th elements of a permutation. It is a connected bipartite $(n-1)$--regular graph of order $n!$.

The Star graph $S_n, n\geqslant 2,$ has integral spectrum with all integers from the set $\{-(n-1),\ldots,n-1\}$ (with the sole exception when $n\leqslant 3$, zero is not an eigenvalue of $S_n$) [CF12,KM12]. Moreover, the spectrum is symmetric with multiplicities $\mathrm{mul}(n-k)=\mathrm{mul}(-n+k)$ for each integer $1\leqslant k \leqslant n$, and $\pm(n-1)$ is a simple eigenvalue. The exact values of multiplicities of eigenvalues of the Star graph $S_n$ for $n \leqslant 10$ were obtained in [KK15] using the spectrum of Jucys-Murphy elements in the algebra of the symmetric group. Recently, analytic formulas for calculating multiplicities of eigenvalues $\pm(n-t)$ for $t = 2,3,4,5$ of the Star graph were found in [AKK16]. In particular, it was shown that $mul(n-2)=(n-1)(n-2)$ for any $n\geqslant 3$. This result is used to get a basis of the eigenspace of $S_n, n\geqslant 4$, with the largest non-principal eigenvalue $n-2$. This is joint work with S. Goryainov, V. Kabanov, L. Shalaginov and A. Valyuzhenich.

We also investigate structural and combinatorial properties of the Star graph. Since the graph is bipartite, it does not contain odd cycles but it does contain $\ell$--cycles for all even $\ell$, where $6\leqslant \ell \leqslant n!$ [JLD91]. Hence, the Star graph $S_n$ is hamiltonian. There is a connection between hamiltonicity of graphs and combinatorial Gray codes, where a combinatorial Gray code has been introduced as a way of generating combinatorial objects so that successive objects differ in some pre--specified small way [S96]. We apply greedy approach to constructing greedy cycles in $S_n$. We consider a greedy sequence as the ordered set of generating elements of a Cayley graph. A greedy sequence is called a greedy subsequence if it forms a non-hamiltonian cycle, which is called a greedy cycle. It is proved that in the Star graph $S_n, n\geqslant 4$, any ordered set of mutually different $n-1$ elements from the generating set $t$ is a greedy subsequence which forms a cycle of length $\ell=2\cdot3^{n-2}$. Moreover, any greedy subsequence gives $\frac{n!}{6}$ mutually different greedy $\ell$-cycles in the graph. From this main result we immediately have that there are no greedy hamiltonian cycles in the Star graph $S_n$ for $n\geqslant 4$. We also show that there is a vertex disjoint cycle cover in the graph presented by greedy cycles of lengths $2\cdot3^{k-2}$, where $3\leqslant k \leqslant n$. This is joint work with D. Gostevsky.

The work has been supported by RFBS Grant 17-51-560008.


[AKK16] S.V. Avgustinovich, E.N. Khomyakova, E.V. Konstantinova, Multiplicities of eigenvalues of the Star graph. Sib. Electron. Math. Reports. 13 (2016) 1258--1270.

[CF12] G. Chapuy, V. Feray, A note on a Cayley graph of $Sym_{n}$, arXiv:1202.4976v2 1--3.

[JLD91] J.S. Jwo, S. Lakshmivarahan, and S.K. Dhall, Embedding of cycles and grids in star graphs, J. Circuits Syst. Comput., 1 (1991) 43-47.

[KK15] E.N. Khomyakova, E.V. Konstantinova, Note on exact values of multiplicities of eigenvalues of the Star graph. Sib. Electron. Math. Reports. 12 (2015) 92--100.

[KM12] R. Krakovski, B. Mohar, Spectrum of Cayley Graphs on the Symmetric Group generated by transposition. Linear Algebra and its Applications. 437 (2012) 1033--1039.

[S96] C. Savage, A survey of combinatorial Gray codes, SIAM Review, 39 (1996) 605-629.

Slides: View slides