The dual Cheeger-Buser inequality for graphons

Abstract

We introduce the notion of bipartiteness ratio for graphons. We prove the dual Cheeger-Buser inequality for graphons, which relates the gap between $2$ and the top of the spectrum of the Laplacian of a graphon with its bipartiteness ratio. The dual Cheeger-Buser inequality was established by Trevisan and Bauer-Jost for graphs. Our result is an analog of that for graphons.

Comments are welcome

References in corpus (2)

• Independent sets, cliques, and colorings in graphons
• Tilings in graphons