Alternating sign property of the perfect matching derangement graph
It was conjectured in the monograph [9] by Godsil and Meagher and in the article [10] by Lindzey that the perfect matching derangement graph M2n possesses the alternating sign property, that is, for any integer partition λ=(λ1,…,λr)⊢n, the sign of the eigenvalue ηλ of M2n is given by sign(ηλ)=(−1)n−...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/164642 |
| _version_ | 1811684167690223616 |
|---|---|
| author | Koh, Samuel Zhi Kang Ku, Cheng Yeaw Wong, Kok Bin |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Koh, Samuel Zhi Kang Ku, Cheng Yeaw Wong, Kok Bin |
| author_sort | Koh, Samuel Zhi Kang |
| collection | NTU |
| description | It was conjectured in the monograph [9] by Godsil and Meagher and in the article [10] by Lindzey that the perfect matching derangement graph M2n possesses the alternating sign property, that is, for any integer partition λ=(λ1,…,λr)⊢n, the sign of the eigenvalue ηλ of M2n is given by sign(ηλ)=(−1)n−λ1. In this paper, we prove that the conjecture is true. Our approach yields a recurrence formula for the eigenvalues of the perfect matching derangement graph as well as a new recurrence formula for the eigenvalues of the permutation derangement graph. |
| first_indexed | 2024-10-01T04:24:20Z |
| format | Journal Article |
| id | ntu-10356/164642 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:24:20Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | ntu-10356/1646422023-02-07T05:12:03Z Alternating sign property of the perfect matching derangement graph Koh, Samuel Zhi Kang Ku, Cheng Yeaw Wong, Kok Bin School of Physical and Mathematical Sciences Science::Physics Association Schemes Perfect Matchings It was conjectured in the monograph [9] by Godsil and Meagher and in the article [10] by Lindzey that the perfect matching derangement graph M2n possesses the alternating sign property, that is, for any integer partition λ=(λ1,…,λr)⊢n, the sign of the eigenvalue ηλ of M2n is given by sign(ηλ)=(−1)n−λ1. In this paper, we prove that the conjecture is true. Our approach yields a recurrence formula for the eigenvalues of the perfect matching derangement graph as well as a new recurrence formula for the eigenvalues of the permutation derangement graph. 2023-02-07T05:12:03Z 2023-02-07T05:12:03Z 2023 Journal Article Koh, S. Z. K., Ku, C. Y. & Wong, K. B. (2023). Alternating sign property of the perfect matching derangement graph. Journal of Combinatorial Theory. Series A, 194, 105706-. https://dx.doi.org/10.1016/j.jcta.2022.105706 0097-3165 https://hdl.handle.net/10356/164642 10.1016/j.jcta.2022.105706 2-s2.0-85141678968 194 105706 en Journal of Combinatorial Theory. Series A © 2022 Elsevier Inc. All rights reserved. |
| spellingShingle | Science::Physics Association Schemes Perfect Matchings Koh, Samuel Zhi Kang Ku, Cheng Yeaw Wong, Kok Bin Alternating sign property of the perfect matching derangement graph |
| title | Alternating sign property of the perfect matching derangement graph |
| title_full | Alternating sign property of the perfect matching derangement graph |
| title_fullStr | Alternating sign property of the perfect matching derangement graph |
| title_full_unstemmed | Alternating sign property of the perfect matching derangement graph |
| title_short | Alternating sign property of the perfect matching derangement graph |
| title_sort | alternating sign property of the perfect matching derangement graph |
| topic | Science::Physics Association Schemes Perfect Matchings |
| url | https://hdl.handle.net/10356/164642 |
| work_keys_str_mv | AT kohsamuelzhikang alternatingsignpropertyoftheperfectmatchingderangementgraph AT kuchengyeaw alternatingsignpropertyoftheperfectmatchingderangementgraph AT wongkokbin alternatingsignpropertyoftheperfectmatchingderangementgraph |