TY - JOUR
T1 - FI–sets with relations
AU - Ramos, Eric
AU - Speyer, David
AU - White, Graham
N1 - Publisher Copyright:
© The journal and the authors, 2020. Some rights reserved.
PY - 2020
Y1 - 2020
N2 - Let FI denote the category whose objects are the sets [n] = {1, . . ., n}, and whose morphisms are injections. We study functors from the category FI into the category of finite sets. We write Sn for the symmetric group on [n]. Our first main result is that, if the functor [n] 7→ Xn is “finitely generated” there is a finite sequence of integers mi and a finite sequence of subgroups Hi of Smi such that, for n sufficiently large, Xn ∼= Fi Sn/(Hi ×Sn−mi) as a set with Sn action. Our second main result is that, if [n] 7→ Xn and [n] 7→ Yn are two such finitely generated functors and Rn ⊂ Xn × Yn is an FI–invariant family of relations, then the (0, 1) matrices encoding the relation Rn, when written in an appropriate basis, vary polynomially with n. In particular, if Rn is an FI–invariant family of relations from Xn 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.
AB - Let FI denote the category whose objects are the sets [n] = {1, . . ., n}, and whose morphisms are injections. We study functors from the category FI into the category of finite sets. We write Sn for the symmetric group on [n]. Our first main result is that, if the functor [n] 7→ Xn is “finitely generated” there is a finite sequence of integers mi and a finite sequence of subgroups Hi of Smi such that, for n sufficiently large, Xn ∼= Fi Sn/(Hi ×Sn−mi) as a set with Sn action. Our second main result is that, if [n] 7→ Xn and [n] 7→ Yn are two such finitely generated functors and Rn ⊂ Xn × Yn is an FI–invariant family of relations, then the (0, 1) matrices encoding the relation Rn, when written in an appropriate basis, vary polynomially with n. In particular, if Rn is an FI–invariant family of relations from Xn 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.
KW - FI-modules
KW - Kneser graphs
KW - Representation Stability
UR - http://www.scopus.com/inward/record.url?scp=85103776119&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85103776119&partnerID=8YFLogxK
U2 - 10.5802/alco.128
DO - 10.5802/alco.128
M3 - Article
AN - SCOPUS:85103776119
VL - 3
SP - 1079
EP - 1098
JO - Algebraic Combinatorics
JF - Algebraic Combinatorics
IS - 5
ER -