Let FI denote the category whose objects are the sets $\left[n\right]=\{1,...,n\}$, and whose morphisms are injections. We study functors from the category $\mathrm{FI}$ into the category of finite sets. We write ${\U0001d516}_{n}$ for the symmetric group on $\left[n\right]$. Our first main result is that, if the functor $\left[n\right]\mapsto {X}_{n}$ is “finitely generated” there is a finite sequence of integers ${m}_{i}$ and a finite sequence of subgroups ${H}_{i}$ of ${\U0001d516}_{{m}_{i}}$ such that, for $n$ sufficiently large, ${X}_{n}\cong {\u2a06}_{i}{\U0001d516}_{n}/({H}_{i}\times {\U0001d516}_{n-{m}_{i}})$ as a set with ${\U0001d516}_{n}$ action. Our second main result is that, if $\left[n\right]\mapsto {X}_{n}$ and $\left[n\right]\mapsto {Y}_{n}$ are two such finitely generated functors and ${R}_{n}\subset {X}_{n}\times {Y}_{n}$ is an FI–invariant family of relations, then the $(0,1)$ matrices encoding the relation ${R}_{n}$, when written in an appropriate basis, vary polynomially with $n$. In particular, if ${R}_{n}$ is an FI–invariant family of relations from ${X}_{n}$ to itself, then the eigenvalues of this matrix are algebraic functions of $n$. As an application of this theorem we provide a proof of a result about eigenvalues of adjacency matrices claimed by the first and last author. This result recovers, for instance, that the adjacency matrices of the Kneser graphs have eigenvalues which are algebraic functions of $n$, while also expanding this result to a larger family of graphs.

Revised: 2020-02-10

Accepted: 2020-05-06

Published online: 2020-10-12

Classification: 05E18, 18A25, 05C25, 05C75

Keywords: FI-modules, Representation Stability, Kneser graphs.

@article{ALCO_2020__3_5_1079_0, author = {Ramos, Eric and Speyer, David and White, Graham}, title = {FI--sets with relations}, journal = {Algebraic Combinatorics}, pages = {1079--1098}, publisher = {MathOA foundation}, volume = {3}, number = {5}, year = {2020}, doi = {10.5802/alco.128}, language = {en}, url = {alco.centre-mersenne.org/item/ALCO_2020__3_5_1079_0/} }

Ramos, Eric; Speyer, David; White, Graham. FI–sets with relations. Algebraic Combinatorics, Volume 3 (2020) no. 5, pp. 1079-1098. doi : 10.5802/alco.128. https://alco.centre-mersenne.org/item/ALCO_2020__3_5_1079_0/

[1] Distance-regular graphs, Springer-Verlag, 1989 | Zbl 0747.05073

[2] FI-modules and stability for representations of symmetric groups, Duke Math. J., Volume 164 (2015) no. 9, pp. 1833-1910 | Article | MR 3357185 | Zbl 1339.55004

[3] FI-modules over Noetherian rings, Geom. Topol., Volume 18 (2014) no. 5, pp. 2951-2984 | Article | MR 3285226 | Zbl 1344.20016

[4] Representation theory and homological stability, Adv. Math., Volume 245 (2013), pp. 250-314 | Article | MR 3084430 | Zbl 1300.20051

[5] Des propriétés de finitude des foncteurs polynomiaux, Fund. Math., Volume 233 (2016) no. 3, pp. 197-256 | Article | MR 3480119 | Zbl 1353.18001

[6] Foncteurs faiblement polynomiaux, Int. Math. Res. Not. IMRN (2019) no. 2, pp. 321-391 | Article | MR 3903561 | Zbl 1433.18003

[7] Representation stability for families of linear subspace arrangements, Adv. Math., Volume 322 (2017), pp. 341-377 | Article | MR 3720801 | Zbl 1377.14012

[8] Algebraic graph theory, Graduate Texts in Mathematics, Volume 207, Springer Science & Business Media, 2001 | MR 1829620 | Zbl 0968.05002

[9] FI-modules and the cohomology of modular representations of symmetric groups (2015) (https://arxiv.org/abs/1505.04294) | MR 3358218

[10] Stability in the homology of congruence subgroups, Invent. Math., Volume 202 (2015) no. 3, pp. 987-1027 | Article | MR 3425385 | Zbl 1334.20045

[11] Homological invariants of FI-modules and FI${}_{G}$-modules, J. Algebra, Volume 502 (2018), pp. 163-195 | Article | MR 3774889 | Zbl 1426.18004

[12] An application of the theory of FI-algebras to graph configuration spaces, Math. Z., Volume 294 (2020) no. 1-2, pp. 1-15 | Article | MR 4050061 | Zbl 1434.55009

[13] Families of Markov chains with compatible symmetric-group actions (2018) (https://arxiv.org/abs/1810.08475)

[14] Families of nested graphs with compatible symmetric-group actions, Selecta Math. (N.S.), Volume 25 (2019) no. 5, Paper No. 70, 42 pages | Article | MR 4030224 | Zbl 1428.05321

[15] GL-equivariant modules over polynomial rings in infinitely many variables, Trans. Amer. Math. Soc., Volume 368 (2016) no. 2, pp. 1097-1158 | Article | MR 3430359 | Zbl 1436.13012

[16] Syzygies of Segre embeddings and $\Delta $-modules, Duke Math. J., Volume 162 (2013) no. 2, pp. 225-277 | Article | MR 3018955 | Zbl 1279.13024