Invariant chains of graphs

Abstract

We initiate a systematic study of Inc-invariant chains of graphs, the combinatorial counterparts of Inc-invariant chains of edge ideals arising in the theory of equivariant Noetherianity. Such a chain consists of graphs on growing vertex sets whose edge sets are compatible with the action of the monoid of strictly increasing maps on the positive integers. We show that several associated combinatorial invariants exhibit rigid asymptotic behavior. The independence number eventually stabilizes, and every fixed entry of the $f$-vector and the $h$-vector of the independence complex is eventually linear. For clique complexes, every fixed entry of the $f$-vector is eventually polynomial, whereas the entries of the $h$-vector are eventually quasi-polynomial. Moreover, the clique and chromatic numbers are eventually quasi-linear, and their difference is eventually at most one. We also prove that the matching number eventually attains the maximal value $\lfloor n/2\rfloor$. Finally, admissible and minimal paths eventually have lengths at most $3$ and $5$, respectively, and their maximal lengths stabilize. These results reveal strong asymptotic regularity in graph families governed by increasing symmetry.