Combinatorics Seminar: Graph Tiling in Bipartite Graphs
Fri, 11/06/2009 - 3:05pm, Skiles 255
Albert Bush, School of Mathematics, Georgia Tech, Organizer: Xingxing Yu
Graph tiling problems can be summarized as follows: given a graph H, what conditions do we need to find a spanning subgraph of some larger graph G that consists entirely of disjoint copies of H. The most familiar example of a graph tiling problem is finding a matching in a graph. With the Regularity Lemma and the Blow-up Lemma as our main tools, we prove a degree condition that guarantees an arbitrary bipartite graph G will be tiled by an arbitrary bipartite graph H. We also prove this degree condition is best possible up to a constant. This answers a question of Zhao and proves an asymptotic version of a result of Kuhn and Osthus for bipartite graphs.
This is joint work with Dr. Yi Zhao.