Premium
On some graph densities in locally dense graphs
Author(s) -
Lee Joonkyung
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20974
Subject(s) - multipartite , conjecture , combinatorics , mathematics , pathwidth , discrete mathematics , graph , 1 planar graph , chordal graph , indifference graph , cograph , line graph , physics , quantum mechanics , quantum entanglement , quantum
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.