Skip to main content
SpringerLink
Log in

Families of nested graphs with compatible symmetric-group actions

  • Published:
Selecta Mathematica Aims and scope Submit manuscript

Abstract

For fixed positive integers n and k, the Kneser graph \(KG_{n,k}\) has vertices labeled by k-element subsets of \(\{1,2,\dots ,n\}\) and edges between disjoint sets. Keeping k fixed and allowing n to grow, one obtains a family of nested graphs, each of which is acted on by a symmetric group in a way which is compatible with these inclusions and the inclusions of each symmetric group into the next. In this paper, we provide a framework for studying families of this kind using the \({{\,\mathrm{FI}\,}}\)-module theory of Church et al. (Duke Math J 164(9):1833–1910, 2015), and show that this theory has a variety of asymptotic consequences for such families of graphs. These consequences span a range of topics including enumeration, concerning counting occurrences of subgraphs, topology, concerning Hom-complexes and configuration spaces of the graphs, and algebra, concerning the changing behaviors in the graph spectra.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Abrams, A.: Configuration spaces and braid groups of graphs. Ph.D thesis. https://home.wlu.edu/~abramsa/publications/thesis.ps (2001)

  2. Bahran, C.: The commuting complex of the symmetric group with bounded number of \(p\)-cycles. arXiv:1808.02581 (2018)

  3. Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1997)

    MATH  Google Scholar 

  4. Babson, E., Kozlov, D.N.: Complexes of graph homomorphisms. Isr. J. Math. 152, 285–312 (2006)

    Article  MathSciNet  Google Scholar 

  5. Babson, E., Kozlov, D.N.: Proof of the Lovász Conjecture. Ann. Math. 165, 965–1007 (2007)

    Article  MathSciNet  Google Scholar 

  6. Biermann, J., Francisco, C.A., Hà, H.T., Tuyl, A.V.: Partial coloring, vertex decomposability and sequentially Cohen–Macaulay simplicial complexes. J. Commut. Algebra 7(3), 337–352 (2015)

    Article  MathSciNet  Google Scholar 

  7. Church, T.: Homological stability for configuration spaces of manifolds. Invent. Math. 188(2), 465–504 (2012)

    Article  MathSciNet  Google Scholar 

  8. Cook, S.A.: The complexity of theorem-proving procedures. Proc. 3rd ACM Symposium on Theory of Computing, pp. 151–158 (1971)

  9. Cvetković, D.M., Doob, M., Sachs, H.: Spectra of graphs—theory and application. Academic Press, London (1980)

    MATH  Google Scholar 

  10. Church, T., Ellenberg, J.S., Farb, B.: FI-modules and stability for representations of symmetric groups. Duke Math. J. 164(9), 1833–1910 (2015)

    Article  MathSciNet  Google Scholar 

  11. Church, T., Ellenberg, J.S., Farb, B., Nagpal, R.: FI-modules over Noetherian rings. Geom. Topol. 18, 2951–2984 (2014)

    Article  MathSciNet  Google Scholar 

  12. Church, T., Farb, B.: Representation theory and homological stability. Adv. Math. 245, 250–314 (2013)

    Article  MathSciNet  Google Scholar 

  13. Chettih, S., Lütgehetmann, D.: The homology of configuration spaces of trees with loops. Algebr. Geom. Topol. 18, 2443–2469 (2018)

    Article  MathSciNet  Google Scholar 

  14. Cvetković, D.M., Rowlinson, P., Simic, S.: Eigenspaces of Graphs. Cambridge University Press, Cambridge (1997)

    Book  Google Scholar 

  15. Cvetković, D.M., Rowlinson, P., Simic, S.: An Introduction to the Theory of Graph Spectra. Cambridge University Press, Cambridge (2010)

    MATH  Google Scholar 

  16. Dochtermann, A.: Homotopy groups of Hom complexes of graphs. J. Comb. Theory Ser. A 116, 180–194 (2009)

    Article  MathSciNet  Google Scholar 

  17. Dochtermann, A.: The universality of Hom complexes of graphs. Combinatorica 29, 433–448 (2009)

    Article  MathSciNet  Google Scholar 

  18. Dobrinskaya, N., Moller, J. M., Notbohm, D.: Vertex colorings of simplicial complexes. arXiv:1007.0710 (2010)

  19. Farley, D., Sabalka, L.: Discrete Morse theory and graph braid groups. Algebr. Geom. Topol. 5, 1075–1109 (2005). (electronic)

    Article  MathSciNet  Google Scholar 

  20. Gadish, N.: Categories of FI type: a unified approach to generalizing representation stability and character polynomials. J. Algebra 480, 450–486 (2017)

    Article  MathSciNet  Google Scholar 

  21. Gadish, N.: Representation stability for families of linear subspace arrangements. Adv. Math. 322, 341–377 (2017)

    Article  MathSciNet  Google Scholar 

  22. Gal, S.R.: Euler characteristic of the configuration space of a complex. Colloq. Math. 89, 61–67 (2001)

    Article  MathSciNet  Google Scholar 

  23. Ghrist, R.: Configuration spaces and braid groups on graphs in robotics, Knots, braids, and mapping class groups - papers dedicated to Joan S. Birman (New York, 1998), AMS/IP Stud. Adv. Math., 24, Amer. Math. Soc., Providence, RI, pp. 29–40 (2001)

  24. Gan, W.L., Watterlond, J.: Stable decompositions of certain representations of the finite general linear groups. Transform. Groups 23, 425–435 (2018)

    Article  MathSciNet  Google Scholar 

  25. Hoffman, A.J.: On the line graph of a projective plane. Proc. Am. Math. Soc. 16, 297–302 (1965)

    Article  MathSciNet  Google Scholar 

  26. Konagaya, M., Otachi, Y., Uehara, R.: Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs. Discrete Appl. Math. 199, 37–45 (2016)

    Article  MathSciNet  Google Scholar 

  27. Lütgehetmann, D.: Representation stability for configuration spaces of graphs. arXiv:1701.03490 (2017)

  28. Lovász, L.: Kneser’s conjecture, chromatic number, and homotopy. J. Comb. Theory Ser. A 25(1978), 319–324 (1978)

    Article  MathSciNet  Google Scholar 

  29. Lovász, L.: Large Networks and Graph Limits, vol. 60. American Mathematical Society, Providence (2012)

    MATH  Google Scholar 

  30. Laskar, R.: Eigenvalues of the adjacency matrix of cubic lattice graphs. Pac. J. Math. 29, 623–629 (1969)

    Article  MathSciNet  Google Scholar 

  31. Li, L., Yu, N.: \(\text{ FI }^m\)-modules over Noetherian rings. J. Pure Appl. Algebra 223, 3436–3460 (2019)

    Article  MathSciNet  Google Scholar 

  32. Moon, J.W.: On the line-graph of the complete bigraph. Ann. Math. Stat. 34, 664–667 (1963)

    Article  MathSciNet  Google Scholar 

  33. McDuff, D.: Configuration spaces of positive and negative particles. Topology 14(1), 91–107 (1975)

    Article  MathSciNet  Google Scholar 

  34. Putman, A., Sam, S.: Representation stability and finite linear groups. Duke Math. J. 166, 2521–2598 (2017)

    Article  MathSciNet  Google Scholar 

  35. Ramos, E.: Stability phenomena in the homology of tree braid groups. Algebr. Geom. Topol. 18, 2305–2337 (2018)

    Article  MathSciNet  Google Scholar 

  36. Ramos, E., Speyer, D., White, G.: FI-sets with relations. arXiv:1804.04238 (2018)

  37. Światkowski, J.: Estimates for homological dimension of configuration spaces of graphs. Colloq. Math. 89(1), 69–79 (2001)

    Article  MathSciNet  Google Scholar 

  38. Syslo, M.M.: The subgraph isomorphism problem for outerplanar graphs. Theor. Comput. Sci. 17, 91–97 (1982)

    Article  MathSciNet  Google Scholar 

  39. Snowden, A.: Syzygies of Segre embeddings and \(\Delta \)-modules. Duke Math. J. 162(2), 225–277 (2013)

    Article  MathSciNet  Google Scholar 

  40. Sam, S., Snowden, A.: Gröbner methods for representations of combinatorial categories. J. Am. Math. Soc. 30, 159–203 (2017)

    Article  Google Scholar 

  41. Whitney, H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54, 150–168 (1932)

    Article  MathSciNet  Google Scholar 

  42. Witshire-Gordon, J.: Uniformly presented vector spaces. arXiv:1406.0786 (2014)

Download references

Acknowledgements

We would like to send our deepest thanks to Tom Church, Andrew Snowden, and David Speyer for their helpful suggestions. We also thank Jordan Ellenberg, and John Wiltshire-Gordon for their early inspiration. Finally, we would like to thank the anonymous referee, whose thorough reading of the work improved its quality substantially.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Oregon, Fenton Hall, Eugene, OR, 97401, USA

    Eric Ramos

  2. Department of Mathematics, Indiana University - Bloomington, Rawles Hall, Bloomington, IN, 47405, USA

    Graham White

Authors
  1. Eric Ramos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Graham White
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Eric Ramos.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

E. Ramos was supported by NSF Grant DMS-1704811.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ramos, E., White, G. Families of nested graphs with compatible symmetric-group actions. Sel. Math. New Ser. 25, 70 (2019). https://doi.org/10.1007/s00029-019-0520-9

Download citation

  • Published:

  • DOI: https://doi.org/10.1007/s00029-019-0520-9

Keywords

Mathematics Subject Classification

Search

Navigation