Families of nested graphs with compatible symmetric-group actions

Abstract

For fixed positive integers $n$ and $k$, the Kneser graph $K{G}_{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 all of the other actions. In this paper, we provide a framework for studying families of this kind using the FI-module theory of Church, Ellenberg, and Farb, 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.

v2. Fixed the statement of Theorem G, as well as various typos throughout