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.
We prove that a path maximizes the expected range of a uniformly chosen graph homomorphism into the integers, with one vertex pinned at zero, among all connected bipartite graphs of the same order. This establishes the expectation form of the Benjamini--H\"aggstr\"om--Mossel conjecture. The proof restricts and rescales...
We determine the orientable genus of an infinite family of bipartite Kneser graphs. The graph $H(h,2)$ has two copies of the two-element subsets of $[h]$, with opposite-class vertices adjacent when the corresponding subsets are disjoint. For every prime $h>3$ with $h\equiv3\pmod8$, we prove $$ \gamma(H(h,2))=1-\frac{h(...
All the eigenvalues of an integral graphs are integers. Integral graphs are extremely rare. They form an asymptotically vanishing fraction $2^{-\Omega(n)}$ among all graphs on $n$ vertices. It makes the construction of a new family of integral graphs a challenging task. Also, most of the known infinite family of integr...
T. Manna, Supriyo Dutta, Baby Bhattacharya· 0 citations
We study the hard-core model on recursively defined sequences $(G_n)_{n\geq0}$ of graphs with a fixed number $k\geq 1$ of labeled vertices in each graph. The next graph in the sequence is constructed by taking a fixed number $m\geq 2$ of copies of the previous graph, connecting these copies by identifying some labeled...
We prove that the realization graph of every graphical degree sequence is maximally Hamiltonian: it is Hamilton-laceable when bipartite on more than one vertex, and Hamilton-connected otherwise. This answers Problem P59 of M\"utze's survey of combinatorial Gray codes, and the Hamiltonicity question recorded as open by...
The canonical double cover $BX$ of a graph $X$ is the direct product $X\times K_2$. A graph $X$ is stable if every automorphism of $BX$ is induced by automorphisms of $X$ and $K_2$, and unstable otherwise. We prove several asymptotic results on stable and unstable graphs. In particular, we show that the automorphism gr...
Bartłomiej Bychawski, Ademir Hujdurović, Dorde Mitrovic et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
