Title    name
KAIST COMBINATORICS SEMINAR
 
  Title
  Speaker 엄상일
  Date 2009-02-04
  Host
  Place KAIST
  File  의 1 번째 Real Media 동영상입니다.
 
Abstract : A clique of a graph is a set of pairwise adjacent vertices. We are interested in the maximum possible number of cliques in a graph. In general a graph with n vertices can have at most 2n cliques obviously. We will show that if we restrict to a graph with no Kr- minor, then such a graph can have at most O(n) cliques. Indeed this result is not new; several researchers already discovered the same bound. Previous best bound was 2crplog rn. We improved this to 2c log log rn. We also looked at other classes of graphs. As a corollary, we obtained a hypergraph generalization of the theorem of Thomason and Kostochka (independently) on the maximum number of edges in a graph with no Kr minor. This talk is based on a joint work with Fedor Fomin and Dimitrios Thilikos for relating tree-width and rank- width for planar graphs.