Georgia Institute of Technology College of Sciences

The multipermutohedral Chow ring was introduced in a series of papers by Clader, Damiolini, Eur, Huang, Li, and Ramadas to study moduli spaces with cyclic symmetry. It generalizes Chow rings of permutohedral varieties and type-B Coxeter arrangements. In this talk, we establish the combinatorial structure of the multipermutohedral Chow ring through an explicit Gröbner basis, yielding a Feichtner-Yuzvinsky-type monomial basis and a formula for the Hilbert series. Using this formula, we refine the palindromicity of the Hilbert series. From a representation-theoretic perspective, we also compute the equivariant Hilbert series under two natural group actions and construct combinatorial maps that establish equivariant unimodality and palindromicity.

Let $G$ be an $n$-vertex graph with Laplacian eigenvalues $0=\lambda_1(G)\le \lambda_2(G)\le\cdots\le \lambda_n(G)$. Motivated by the Alon--Boppana bound and the Ramanujan phenomenon for regular graphs, Spielman conjectured that, for every graph $G$ with fixed average degree $d\ge 1$, its Laplacian eigenratio satisfies $$\frac{\lambda_2(G)}{\lambda_n(G)} \le \frac{d-2\sqrt{d-1}}{d+2\sqrt{d-1}}+o_n(1),$$ where $o_n(1)\to 0$ as $n\to\infty$. The main purpose of this paper is to investigate this conjecture. We show that the situation is mixed. On the negative side, the conjecture fails for infinitely many average degrees $d>2$, via constructions based on bipartite Ramanujan graphs. On the positive side, it holds in two important settings: we verify it for all average degrees $d\le 2$, and we prove it for all regular graphs. In fact, for regular graphs we obtain stronger bounds comparing higher Laplacian eigenvalues. As a consequence, we show that for every fixed $d\ge 3$ and every $\varepsilon>0$, every sufficiently large $d$-regular Ramanujan graph has linearly many adjacency eigenvalues below $-2\sqrt{d-1}+\varepsilon$, thereby strengthening earlier results of Li and Cioabă by giving an unconditional result of this form. We also settle two related conjectures: one of You and Liu concerning the maximum Laplacian eigenratio of trees, and one of Gu concerning the Hamiltonicity of graphs with large Laplacian eigenratio.

Joint with Quanyu Tang, Yuchang Wang and Zhiheng Zheng.

Kirchhoff's celebrated matrix tree theorem expresses the number of spanning trees of a graph as a minor of the Laplacian matrix of the graph. In modern language, this determinantal counting formula reflects the fact that spanning trees in a graph form a regular matroid. In this talk, I will give a short historical overview of the tree-counting problem and a related quantity from electrical circuit theory: the effective resistance. I will describe a characterization of effective resistances in terms of a certain polytope and discuss a recent application to discrete notions of curvature on graphs. The talk is based on the article: https://arxiv.org/abs/2410.07756

The degeneracy of a graph is a measure of sparseness that appears in many contexts throughout graph theory. In extremal graph theory, it is known that graphs of bounded degeneracy have Ramsey number which is linear in their number of vertices (Lee, 2017). Also, the degeneracy gives good bounds on the Turán exponent of bipartite graphs (Alon--Krivelevich--Sudokav, 2003). Extending these results to hypergraphs presents a challenge, as it is known that the naïve generalization of these results -- using the standard notion of hypergraph degeneracy -- are not true (Kostochka--Rödl 2006). We define a new measure of sparseness for hypergraphs called skeletal degeneracy and show that it gives information on both the Ramsey- and Turán-type properties of hypergraphs.

Based on joint work with Jacob Fox, Maya Sankar, Michael Simkin, and Yunkun Zhou