### 기초과학VOD

BASIC SCI VOD

•   >
• 연구동향
•   >
• 기초과학VOD
Super Title Title 2018 Discrete Math 세미나 Counting tree-like graphs in locally dense graphs Joonkyung Lee  (  Mathematical Institute, University of Oxford, Oxford, UK  ) 2018-01-08 KAIST KAIST 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.

이 페이지에서 제공하는 정보에 만족하십니까?