Аннотация:
Транспозиционный граф $T_n$ определяется как граф Кэли на симметрической группе $Sym_n$ относительно порождающего множества транспозиций. Известно, что все собственные значения этого графа являются
целыми числами. Кроме этого, доказано, что наибольшее собственное значение $\frac{n(n-1)}{2}$ имеет кратность $1$, второе собственное значение $\frac{n(n-3)}{2}$ имеет кратность $(n-1)^2$, и для каждого $k, \ 1\leqslant k \leqslant n$, значение $\frac{n(n-2k+1)}{2}$ является собственным значением с кратностью не менее $\frac{n!}{n(n-k)!(k-i)!}$. Поскольку транспозиционный граф является двудольным, то для любого его собственного значения $\lambda$ верно, что $-\lambda$ также является собственным значением с той же кратностью, что и $\lambda$. Таким образом, имеется некоторое представление о том, как устроен спектр $Spec(T_n)$ транспозиционного графа $T_n$, где под спектром понимается множество всех различных собственных значений графа вместе с их кратностями. Однако точное описание спектра для графа $T_n$ неизвестно. В этом докладе будут рассказаны результаты в изучении спектра графа $T_n$, которых уже удалось добиться, а так же о сложностях, которые возникают при попытке точно описать спектр данного графа.
|
