Higher-order Cheeger inequalities for graphons

2025/11/10 by Mugdha Mahesh Pokharanakar, Pokharanakar, Mugdha Mahesh
Computer Science · Mathematics · #05C50 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2511.07016

openalex publication_date 2025/11/10 · openalex created_date 2025/11/12 · openalex updated_date 2026/07/28

Abstract

The higher-order Cheeger inequalities were established for graphs by Lee, Oveis Gharan and Trevisan. We prove analogous inequalities for graphons in this article.

Citations

• The dual Cheeger-Buser inequality for graphons
• Cheeger inequalities for graph limits
• Criteria of Spectral Gap for Markov Operators
• Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing
• Limits of dense graph sequences

Related

• Cheeger inequalities for graph limits
• The dual Cheeger-Buser inequality for graphons
• Spectral bounds of multi-way Cheeger constants via cyclomatic number
• A linear k-fold Cheeger inequality
• A Higher-Order Cheeger's Inequality