Choongbum Lee (이중범), Self-similarity of graphs

Self-similarity of graphs
Choongbum Lee (이중범)
Department of Mathematics, UCLA, Los Angeles, USA
2012/7/4 Wed 4PM-5PM (Bldg. E6-1, Room 3433)

An old problem raised independently by Jacobson and Schönheim asks to determine the maximum s for which every graph with m edges contains a pair of edge-disjoint isomorphic subgraphs with s edges. We determine this maximum up to a constant factor and show that every m-edge graph contains a pair of edge-disjoint isomorphic subgraphs with at least c (m log m)2/3 edges for some absolute constant c, and find graphs where this estimate is off only by a multiplicative constant. Our results improve bounds of Erdős, Pach, and Pyber from 1987.
Joint work with Po-Shen Loh and Benny Sudakov.

Tags:

This entry was posted on Tuesday, June 26th, 2012 at 6:42 am and is filed under 2012, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.