Title   name
2018 Discrete Math 세미나
 
  Title
  Speaker   Joonkyung Lee  
  Date 2018-01-08
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다.
 
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.