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

Ashwin Sah; Mehtaab Sawhney; Jonathan Tidor; Yufei Zhao

doi:10.1017/S0963548321000031

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

Ashwin Sah
, Mehtaab Sawhney
, Jonathan Tidor
, Yufei Zhao

Research output: Contribution to journal › Article › peer-review

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 C4-counts), but with no limit expressible as a kernel.

Original language	English (US)
Pages (from-to)	796-799
Number of pages	4
Journal	Combinatorics Probability and Computing
Volume	30
Issue number	5
DOIs	https://doi.org/10.1017/S0963548321000031
State	Published - Sep 1 2021
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/S0963548321000031

Cite this

@article{291d3ec68a6644dc956745c32e078cab,

title = "A counterexample to the Bollob{\'a}s-Riordan conjectures on sparse graph limits",

abstract = "Bollob{\'a}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 C4-counts), but with no limit expressible as a kernel.",

author = "Ashwin Sah and Mehtaab Sawhney and Jonathan Tidor and Yufei Zhao",

note = "Publisher Copyright: {\textcopyright} The Author(s), 2021.",

year = "2021",

month = sep,

day = "1",

doi = "10.1017/S0963548321000031",

language = "English (US)",

volume = "30",

pages = "796--799",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "5",

}

TY - JOUR

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

AU - Sah, Ashwin

AU - Sawhney, Mehtaab

AU - Tidor, Jonathan

AU - Zhao, Yufei

N1 - Publisher Copyright: © The Author(s), 2021.

PY - 2021/9/1

Y1 - 2021/9/1

N2 - 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 C4-counts), but with no limit expressible as a kernel.

AB - 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 C4-counts), but with no limit expressible as a kernel.

UR - https://www.scopus.com/pages/publications/85100309888

UR - https://www.scopus.com/pages/publications/85100309888#tab=citedBy

U2 - 10.1017/S0963548321000031

DO - 10.1017/S0963548321000031

M3 - Article

AN - SCOPUS:85100309888

SN - 0963-5483

VL - 30

SP - 796

EP - 799

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 5

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this