New version page

Induced Tree

Upgrade to remove ads

This preview shows page 1-2-3 out of 8 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

Large induced trees in Kr-free graphsIntroductionTriangle-free graphsMain lemmaProof of Lemma 1Kr-free graphsConcluding remarksReferencesJournal of Combinatorial Theory, Series B 99 (2009) 494–501Contents lists available at ScienceDirectJournal of Combinatorial Theory,Series Bwww.elsevier.com/locate/jctbLarge induced trees in Kr-free graphsJacob Foxa,1, Po-Shen Loha,2, Benny Sudakovb,3aDepartment of Mathematics, Princeton University, Princeton, NJ 08544, United StatesbDepartment of Mathematics, UCLA, Los Angeles 90095, United Statesarticle info abstractArticle history:Received 7 March 2008Availableonline29October2008Keywords:Induced subgraphsTreesTriangle-free graphsRamsey TheoryForagraphG,lett(G) denote the maximum number of verticesin an induced subgraph of G that is a tree. In this paper, westudy the problem of bounding t(G) for graphs which do notcontain a complete graph Kron r vertices. This problem wasposedtwentyyearsagobyErd˝os, Saks, and Sós. Substantiallyimproving earlier results of various researchers, we prove thatevery connected triangle-free graph on n vertices contains aninduced tree of order√n.Whenr  4, we also show that t(G) logn4logrfor every connected Kr-free graph G of order n.Bothofthesebounds are tight up to small multiplicative constants, and the firstone disproves a recent conjecture of Matoušek and Šámal.© 2008 Elsevier Inc. All rights reserved.1. IntroductionFor a graph G,lett(G) denote the maximum number of vertices in an induced subgraph of G thatisatree.Theproblemofboundingt(G) in a connected graph G was first introduced twenty yearsago by Erd˝os, Saks, and Sós [5]. Clearly, to get a non-trivial result one must impose some conditionson the graph G, because, for example, the complete graph contains no induced tree with more than 2vertices. In their paper, Erd˝os, Saks, and Sós studied the relationship between t(G) and several naturalparameters of the graph G. They were able to obtain asymptotically tight bounds on t(G) when eitherthe number of edges or the independence number of G were known.E-mail addresses: [email protected] (J. Fox), [email protected] (P.-S. Loh), [email protected](B. Sudakov).1Research supported in part by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship.2Research supported in part by a Fannie and John Hertz Foundation Fellowship, an NSF Graduate Research Fellowship, and aPrinceton Centennial Fellowship.3Research supported in part by NSF CAREER award DMS-0812005, and a USA-Israeli BSF grant.0095-8956/$ – see front matter© 2008 Elsevier Inc. All rights reserved.doi:10.1016/j.jctb.2008.10.001J. Fox et al. / Journal of Combinatorial Theory, Series B 99 (2009) 494–501 495Erd˝os, Saks, and Sós also considered the problem of estimating the size of the largest induced treein graphs with noKr(complete graph onrvertices). Lettr(n) be the minimum value oft(G) over allconnectedKr-free graphsGonnvertices. In particular, for triangle-free graphs, they proved thatΩlognlog logn t3(n)  O√nlogn,and left as an interesting open problem the task of closing the wide gap between these two bounds.The first significant progress on this question was made only recently by Matoušek and Šámal [15],who actually came to the problem of estimatingt3(n) from a different direction. Pultr had beenstudying forbidden configurations in Priestley spaces [2], and this led him to ask in [17] how larget(G) could be for connected bipartite graphsG.LettB(n) be the minimum value oft(G) over allconnected bipartite graphs onnvertices. It is clear thatt3(n)  tB(n),sotheresultofErd˝os, Saks, andSós immediately gives a lower bound ontB(n).Motivated by Pultr’s question, Matoušek and Šámal studiedtB(n) andt3(n). They found the fol-lowing nice construction which shows thatt3(n)  tB(n)<2√n + 1. Letm=√n, and consider thegraphwithpartsV−m+1, V−m+2,...,Vm−1, where |Vi|=m −|i|, and each consecutive pair of parts(Vi, Vi+1) induces a complete bipartite graph. This graph is clearly bipartite withm2=nvertices, andit is easy to see that every induced tree in it has at most 2m−1 vertices. On the other hand, Matoušekand Šámal were able to improve the lower bound ontB(n) andt3(n), showing thatt3(n) ec√lognforsome constantc. Furthermore, they also proved that if there was even a single value ofn0for whicht3(n0)<√n0, then in factt3(n)  O (nβ) for some constant β strictly below 1/2. The above fact ledMatoušek and Šámal to conjecture that the true asymptotic behavior oft3(n) was some positive powerof n which is strictly smaller than 1/2.Our first main result essentially solves this problem. It determines that the order of growth of botht3(n) and tB(n) is precisely Θ(√n), disproving the conjecture of Matoušek and Šámal.Theorem 1. Let G be a connected triangle-free graph on n vertices. Then t(G) √n.Furthermore, our approach can also be used to give asymptotically tight bounds on the size of thelargest induced tree in Kr-free graphs for all remaining values of r. In their original paper, Erd˝os, Saks,and Sós gave an elegant construction which shows that tr(n) for r 4 has only logarithmic growth.Indeed, let T be a balanced(r − 1)-regular tree, that is, a rooted tree in which all non-leaf verticeshave degree r−1 and the depth of any two leaves differs by at most 1. Then the line graph4L(T ) isclearly Kr-free, and one can easily check that induced trees in L(T ) correspond to induced paths in T ,which have only logarithmic length. Optimizing the choice of the parameters in this construction, onecan show that tr(n) 2log(n−1)log(r−2)+ 2. On the other hand, using Ramsey Theory, Erd˝os, Saks, and Sósalso showed that tr(n) crlognlog logn, where cris a constant factor depending only on r. Our second mainresult closes the gap between these two bounds as well, and determines the order of growth of tr(n)up to a small multiplicative constant.Theorem 2. Let r 4, and let G be a connected graph on n vertices with no clique of size r. Then t(G) logn4logr.One can also study induced forests rather than trees in Kr-free graphs. Let fr(n) be the maximumnumber such that every Kr-free graph on n vertices contains an induced forest with at least fr(n)vertices. Trivially we have fr(n) tr(n), but it appears that the size of the maximum induced forestin a graph is more closely related to another parameter. The independence numberα(G) of a graphis the size


Download Induced Tree
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Induced Tree and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Induced Tree 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?