Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Large bounded degree trees in expanding graphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Large bounded degree trees in expanding graphs. | Large bounded degree trees in expanding graphs Jozsef Balogh Bela CsabaỊ Martin Peb and Wojciech Samotij Submitted Jun 2 2009 Accepted Dec 17 2009 Published Jan 5 2010 Mathematics Subject Classification 05C80 05D40 05C05 05C35 Abstract A remarkable result of Friedman and Pippenger 4 gives a sufficient condition on the expansion properties of a graph to contain all small trees with bounded maximum degree. Haxell 5 showed that under slightly stronger assumptions on the expansion rate their technique allows one to find arbitrarily large trees with bounded maximum degree. Using a slightly weaker version of Haxell s result we prove that a certain family of expanding graphs which includes very sparse random graphs and regular graphs with large enough spectral gap contains all almost spanning bounded degree trees. This improves two recent tree-embedding results of Alon Krivelevich and Sudakov 1 . 1 Introduction A very well-known folklore result on tree-embedding states that every graph with minimum degree at least k contains all trees with at most k edges and this is best possible as illustrated by an arbitrarily large disjoint union of k 1 -vertex complete graphs . A natural question arises - what additional assumptions on a graph can force it to contain certain trees For an arbitrary graph H and a set X c V H let NH X denote the set of neighbors in H of vertices in X. Extending a path-embedding result of Posa 7 Department of Mathematics University of California San Diego 9500 Gilman Drive La Jolla CA 92093 USA and Department of Mathematics University of Illinois Urbana IL 61801 USA. E-mail address jobal@math.uiuc.edu. This material is based upon work supported by NSF CAREER Grant DMS-0745185 and DMS-0600303 UIUC Campus Research Board Grants 09072 and 08086 and OTKA Grant K76099 Department of Mathematics Western Kentucky University Bowling Green KY 42101 USA. E-mail address bela.csaba@wku.edu. This research was partially supported by a New Faculty Scholarship Grant of .