Joonkyung Lee (이준경), Counting tree-like graphs in locally dense graphs

Counting tree-like graphs in locally dense graphs
Joonkyung Lee (이준경)
Mathematical Institute, University of Oxford, Oxford, UK
2018/1/8 Mon 4PM-5PM
We prove that a class of graphs obtained by gluing complete multipartite graphs in a tree-like way satisfies a conjecture of Kohayakawa, Nagle, Rödl, and Schacht on random-like counts for small graphs in locally dense graphs. This implies an approximate version of the conjecture for graphs with bounded tree-width. We also prove an analogous result for odd cycles instead of complete multipartite graphs.
The proof uses a general information theoretic method to prove graph homomorphism inequalities for tree-like structured graphs, which may be of independent interest.


Comments are closed.