A counterexample to the Bollobás–Riordan conjectures on sparse graph limits. (27th September 2021)

• Record Type: Journal Article
• Authors: Sah, Ashwin; Sawhney, Mehtaab; Tidor, Jonathan; Zhao, Yufei
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 5(2021)
• Page Start: 796
• Page End: 799
• Publication Date: 2021-09-27
• Subjects: 05C35 -- 05D99; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548321000031
• Languages: English
• ISSNs: 0963-5483

Abstract

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.