[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the Spectra of Simplicial Rook Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

The simplicial rook graph \(SR(d,n)\) is the graph whose vertices are the lattice points in the \(n\)th dilate of the standard simplex in \(\mathbb {R}^d\), with two vertices adjacent if they differ in exactly two coordinates. We prove that the adjacency and Laplacian matrices of \(SR(3,n)\) have integral spectrum for every \(n\). The proof proceeds by calculating an explicit eigenbasis. We conjecture that \(SR(d,n)\) is integral for all \(d\) and \(n\), and present evidence in support of this conjecture. For \(n<\left( {\begin{array}{c}d\\ 2\end{array}}\right) \), the evidence indicates that the smallest eigenvalue of the adjacency matrix is \(-n\), and that the corresponding eigenspace has dimension given by the Mahonian numbers, which enumerate permutations by number of inversions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Balińska, K., Cvetković, D., Radosavljević, Z., Simić, S., Stevanović, D.: A survey on integral graphs. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 13(2002), 42–65 (2003)

    Google Scholar 

  2. Blackburn, S.R., Paterson, M.B., Stinson, D.R.: Putting dots in triangles. J. Comb. Math. Comb. Comput. 78, 23–32 (2011)

    MathSciNet  MATH  Google Scholar 

  3. Brouwer, A.E., Haemers, W.H.: Spectra of graphs, Universitext. Springer, New York (2012). MR 2882891

  4. Bussemaker, F.C., Cvetković, D.M.: There are exactly 13 connected, cubic, integral graphs. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz. no. 544–576, 43–48 (1976)

  5. Butler, F., Can, M., Haglund, J., Remmel, J.B.: Rook theory notes. Available at http://www.math.ucsd.edu/~remmel/files/Book.pdf. Retrieved 22 April 2014

  6. Cvetković, D.M.: Cubic integral graphs. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz. no. 498–541, 107–113 (1975)

  7. Cvetković, D.M., Doob, M., Gutman, I., Torgašev, A.: Recent results in the theory of graph spectra, annals of discrete mathematics, vol. 36. North-Holland Publishing Co., Amsterdam (1988)

  8. Godsil, C., Royle, G.: Algebraic graph theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001)

  9. Haemers, W.H.: Interlacing eigenvalues and graphs. Linear Algebra Appl. 226(228), 593–616 (1995)

    Article  MathSciNet  Google Scholar 

  10. Krebs, M., Shaheen, A.: On the spectra of Johnson graphs. Electron. J. Linear Algebra 17, 154–167 (2008)

    MathSciNet  MATH  Google Scholar 

  11. Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1–7 (1979)

    Article  MATH  Google Scholar 

  12. Merris, R.: Degree maximal graphs are Laplacian integral. Linear Algebra Appl. 199, 381–389 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  13. Nivasch, G., Lev, E.: Nonattacking queens on a triangle. Math. Mag. 78(5), 399–403 (2005)

    Article  MATH  Google Scholar 

  14. Schwenk, A.J.: Exactly thirteen connected cubic graphs have integral spectra. In: Proceedings of International Conference on Theory and Applications of Graphs, Western Michigan University, Kalamazoo, 1976. Lecture Notes in Mathematics, vol. 642, pp. 516–533. Springer, Berlin (1978)

  15. Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences (2012). Published electronically at http://oeis.org

  16. Stanley, R.P.: Enumerative combinatorics, vol. 2. Cambridge Studies in Advanced Mathematics, vol. 62. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin

  17. Stein, W.A. et al.: Sage Mathematics Software (Version 5.0.1). The Sage Development Team (2012). http://www.sagemath.org

  18. van Dam, E.R., Haemers, W.H.: Which graphs are determined by their spectrum?. Linear Algebra Appl. vol. 373, pp. 241–272 (2003). Special Issue on the Combinatorial Matrix Theory Conference (Pohang, 2002)

  19. van Dam, E.R., Haemers, W.H.: Developments on spectral characterizations of graphs. Discret. Math. 309(3), 576–586 (2009)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

We thank Cristi Stoica for bringing our attention to references [2] and [13], and Noam Elkies and other members of MathOverflow for a stimulating discussion. We also thank an anonymous referee for providing references on Question 4.2 and for suggesting the argument that \(SR(3,3)\) is determined by its spectrum. The open-source software package Sage [17] was a valuable tool in carrying out this research.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Kansas, Lawrence, KS , 66045, USA

    Jeremy L. Martin

  2. Department of Mathematics and Statistics, Washburn University, Topeka, KS , 66621, USA

    Jennifer D. Wagner

Authors
  1. Jeremy L. Martin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jennifer D. Wagner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jeremy L. Martin.

Additional information

First author supported in part by a Simons Foundation Collaboration Grant and by National Security Agency Grant No. H98230-12-1-0274.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Martin, J.L., Wagner, J.D. On the Spectra of Simplicial Rook Graphs. Graphs and Combinatorics 31, 1589–1611 (2015). https://doi.org/10.1007/s00373-014-1452-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-014-1452-y

Keywords

Mathematics Subject Classification (2000)

Search

Navigation