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

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"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 shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Combinatorics

๐Ÿ”ฎ ๐Ÿ”ฎ The Ethereal

Tables of subspace codes

Daniel Heinlein, Michael Kiermaier, ... (+2 more)

math.CO ๐Ÿ› arXiv ๐Ÿ“š 94 cites 10 years ago