tailieunhanh - Báo cáo toán học: "An algorithmic Friedman–Pippenger theorem on tree embeddings and applications"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: An algorithmic Friedman–Pippenger theorem on tree embeddings and applications. | An algorithmic Friedman-Pippenger theorem on tree embeddings and applications Domingos Dellamonica Jr. Department of Mathematics and Computer Science Emory University 400 Dowman Dr. Atlanta GA 30322 USA ddellam@ Yoshiharu Kohayakawa Instituto de Matematica e Estatistica Universidade de São Paulo Rua do Matão 1010 05508-090 São Paulo Brazil yoshi@ Submitted Apr 29 2008 Accepted Oct 2 2008 Published Oct 13 2008 Mathematics Subject Classification 05C05 05C85 Abstract An n d -expander is a graph G V E such that for every X c V with XI 2n 2 we have rG X d 1 X . A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger 1987 proved that any n d -expander contains every small tree. However their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of N D A -graphs A as long as G contains a positive fraction of the edges of A and A D is small enough. In several applications of the Friedman-Pippenger theorem including the ones in the original paper of those authors the n d -expander G is a subgraph of an N D A -graph as above. Therefore our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example we discuss a recent result of Alon Krivelevich and Sudakov 2007 concerning embedding nearly spanning bounded degree trees the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs solved by Aggarwal et al. 1996 . Research partially