기초과학VOD

BASIC SCI VOD

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

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