PreprintarXiv licencearXiv
Counting cographs in locally dense graphs
Abstract
An n-vertex graph G is $(ρ, d)$-dense if for all U ⊆ V(G) of size at least ρn, the induced subgraph G[U] contains at least d/2|U|2 edges. In 2010, partly motivated by the theory of quasirandomness, Kohayakawa, Nagle, Rödl, and Schacht conjectured that, for any fixed graph F, the number of homomorphic copies of F in a given n-vertex (o(1),d)-dense graph is at least (1−o(1))de(F)nv(F). Despite considerable effort, only a few graphs are known to satisfy the conjecture. We find a new broad class of graphs that satisfy the conjecture, including cographs.
Related
BibTeX
@misc{lee2026counting,
title = {{Counting cographs in locally dense graphs}},
author = {Hyunwoo Lee},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13820},
eprint = {2610.13820},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13820},
}
RIS
TY - UNPB
TI - Counting cographs in locally dense graphs
AU - Hyunwoo Lee
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13820
UR - https://arxiv.org/abs/2610.13820
AB - An n-vertex graph G is $(ρ, d)$-dense if for all U ⊆ V(G) of size at least ρn, the induced subgraph G[U] contains at least d/2|U|^2 edges. In 2010, partly motivated by the theory of quasirandomness, Kohayakawa, Nagle, Rödl, and Schacht conjectured that, for any fixed graph F, the number of homomorphic copies of F in a given n-vertex (o(1),d)-dense graph is at least (1−o(1))d^e(F)n^v(F). Despite considerable effort, only a few graphs are known to satisfy the conjecture. We find a new broad class of graphs that satisfy the conjecture, including cographs.
ER -