Cookie Setting MathNet Korea

이전페이지 이동
Counting tree-like graphs in locally dense graphs
[2018 Discrete Math 세미나 ]
Date: 2018-01-08
Speaker : Joonkyung Lee (Mathematical Institute, University of Oxford, Oxford, UK)
Abstract : 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.
Information Center for Mathematical Sciences KAIST
34141 대전광역시 유성구 대학로 291 (구성동373-1)
한국과학기술원(KAIST) 수리과학정보센터
전화 042-350-8196
e-mail :
Copyright (C) 2018. ICMS All Rights Reserved.