Combinatorics Seminar
When: Sunday, June 22, 10am
Where: Schreiber 309
Speaker: Benny Sudakov,University of California at Los Angeles
Title: Nearly optimal embedding of trees
Abstract:
In this talk we show how to find nearly optimal embeddings of
large trees in several natural classes of graphs. The size of
the tree T can be as large as a constant fraction of the size
of the graph G, and the maximum degree of T can be close to
the minimum degree of G. For example, we prove that any graph
of minimum degree d without 4-cycles contains every tree of
size \epsilon d^2 and maximum degree at most (1- 2\epsilon)d.
As there exist d-regular graphs without 4-cycles of
size O(d^2), this result is optimal up to constant factors.
We prove similar nearly tight results for graphs of given
girth, graphs with no complete bipartite subgraph K_{s,t},
random and certain pseudorandom graphs. These results are
obtained using a simple and very natural randomized embedding
algorithm, which can be viewed as a "self-avoiding
tree-indexed random walk". (Joint work with J. Vondrak.)