A counterexample to the Bollobás-Riordan conjectures on sparse graph limits

Abstract

Bollobás and Riordan, in their paper "Metrics for sparse graphs," proposed a number of provocative conjectures extending central results of quasirandom graphs and graph limits to sparse graphs. We refute these conjectures by exhibiting a sequence of graphs with convergent normalized subgraph densities (and pseudorandom $C_4$-counts), but with no limit expressible as a kernel.

References in corpus (3)

• A relative Szemerédi theorem
• An $L^p$ theory of sparse graph convergence II: LD convergence, quotients, and right convergence
• The Green-Tao theorem: an exposition