UCL Discovery Stage
UCL home » Library Services » Electronic resources » UCL Discovery Stage

On some graph densities in locally dense graphs

Lee, J; (2021) On some graph densities in locally dense graphs. Random Structures & Algorithms , 58 (2) pp. 322-344. 10.1002/rsa.20974. Green open access

[thumbnail of KNRS.pdf]
Preview
Text
KNRS.pdf - Accepted Version

Download (279kB) | Preview

Abstract

The Kohayakawa–Nagle–Rödl‐Schacht conjecture roughly states that every sufficiently large locally d‐dense graph G on n vertices must contain at least (1 − o(1))d|E(H )|n|V (H )| copies of a fixed graph H. Despite its important connections to both quasirandomness and Ramsey theory, there are very few examples known to satisfy the conjecture. We provide various new classes of graphs that satisfy the conjecture. First, we prove that adding an edge to a cycle or a tree produces graphs that satisfy the conjecture. Second, we prove that a class of graphs obtained by gluing complete multipartite graphs in a tree‐like way satisfies the conjecture. We also prove an analogous result with odd cycles replacing complete multipartite graphs.

Type: Article
Title: On some graph densities in locally dense graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1002/rsa.20974
Publisher version: http://dx.doi.org/10.1002/rsa.20974
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Software Engineering, Mathematics, Applied, Mathematics, Computer Science, graph inequalities, quasirandomness, Ramsey theory
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
URI: https://discovery-pp.ucl.ac.uk/id/eprint/10120250
Downloads since deposit
945Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item