Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$S_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> denote the symmetric group on n letters. The k-point fixing graph <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {F}(n,k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">F</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is defined to be the graph with vertex set <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$S_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> and two vertices g, h of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathcal {F}(n,k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">F</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> are joined by an edge, if and only if <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$gh^{-1}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>g</mi> <msup> <mi>h</mi> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> fixes exactly k points. Ku, Lau and Wong [Cayley graph on symmetric group generated by elements fixing k points, Linear Algebra Appl. 471 (2015) 405-426] obtained a recursive formula for the eigenvalues of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathcal {F}(n,k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">F</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we use objects called excited diagrams defined as certain generalizations of skew shapes and derive an explicit formula for the eigenvalues of Cayley graph <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\mathcal {F}(n,k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">F</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Then we apply this formula and show that the eigenvalues of <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\mathcal {F}(n,k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">F</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> are in the interval <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$[\frac{-|S(n,k)|}{n-k-1}, |S(n,k)|]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <mfrac> <mrow> <mo>-</mo> <mo stretchy="false">|</mo> <mi>S</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> </mrow> <mrow> <mi>n</mi> <mo>-</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> <mo>,</mo> <mo stretchy="false">|</mo> <mi>S</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>, where S(n, k) is the set of elements <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>σ</mi> </math></EquationSource> </InlineEquation> of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$S_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>σ</mi> </math></EquationSource> </InlineEquation> fixes exactly k points.

A hook formula for eigenvalues of k-point fixing graphs

期刊论文
发表日期：

2026年3月5日

查看全文

Mahdi Ebrahimi

摘要

Let $S_n$ $S_{n}$ denote the symmetric group on n letters. The k-point fixing graph $\mathcal {F}(n,k)$ $F (n, k)$ is defined to be the graph with vertex set $S_n$ $S_{n}$ and two vertices g, h of $\mathcal {F}(n,k)$ $F (n, k)$ are joined by an edge, if and only if $gh^{-1}$ $g h^{- 1}$ fixes exactly k points. Ku, Lau and Wong [Cayley graph on symmetric group generated by elements fixing k points, Linear Algebra Appl. 471 (2015) 405-426] obtained a recursive formula for the eigenvalues of $\mathcal {F}(n,k)$ $F (n, k)$ . In this paper, we use objects called excited diagrams defined as certain generalizations of skew shapes and derive an explicit formula for the eigenvalues of Cayley graph $\mathcal {F}(n,k)$ $F (n, k)$ . Then we apply this formula and show that the eigenvalues of $\mathcal {F}(n,k)$ $F (n, k)$ are in the interval $[\frac{-|S(n,k)|}{n-k-1}, |S(n,k)|]$ $[\frac{- | S (n, k) |}{n - k - 1}, | S (n, k) |]$ , where S(n, k) is the set of elements $\sigma $ $σ$ of $S_n$ $S_{n}$ such that $\sigma $ $σ$ fixes exactly k points.