Counting tree-like graphs in locally dense graphs

Joonkyung Lee (이준경)

Mathematical Institute, University of Oxford, Oxford, UK

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.

The proof uses a general information theoretic method to prove graph homomorphism inequalities for tree-like structured graphs, which may be of independent interest.