๐ฎ
๐ฎ
The Ethereal
Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
March 02, 2025 ยท The Ethereal ยท ๐ IEEE Annual Symposium on Foundations of Computer Science
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Jonathan Leake, Kasper Lindberg, Shayan Oveis Gharan
arXiv ID
2503.01005
Category
math.CO: Combinatorics
Cross-listed
cs.CC,
cs.DS
Citations
1
Venue
IEEE Annual Symposium on Foundations of Computer Science
Last Checked
2 months ago
Abstract
Let $X$ be a $d$-partite $d$-dimensional simplicial complex with parts $T_1,\dots,T_d$ and let $ฮผ$ be a distribution on the facets of $X$. Informally, we say $(X,ฮผ)$ is a path complex if for any $i<j<k$ and $F \in T_i,G \in T_j, K\in T_k$, we have $\mathbb{P}_ฮผ[F,K | G]=\mathbb{P}_ฮผ[F|G]\cdot\mathbb{P}_ฮผ[K|G].$ We develop a new machinery with $\mathcal{C}$-Lorentzian polynomials to show that if all links of $X$ of co-dimension 2 have spectral expansion at most $1/2$, then $X$ is a $1/2$-local spectral expander. We then prove that one can derive fast-mixing results and log-concavity statements for top-link spectral expanders. We use our machinery to prove fast mixing results for sampling maximal flags of flats of distributive lattices (a.k.a. linear extensions of posets) subject to external fields, and to sample maximal flags of flats of "typical" modular lattices. We also use it to re-prove the Heron-Rota-Welsh conjecture and to prove a conjecture of Chan and Pak which gives a generalization of Stanley's log-concavity theorem. Lastly, we use it to prove near optimal trickle-down theorems for "sparse complexes" such as constructions by Lubotzky-Samuels-Vishne, Kaufman-Oppenheim, and O'Donnell-Pratt.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal