Negligible Obstructions and Turán Exponents

Tao Jiang ,Zilin Jiang and Jie Ma

1 Department of Mathematics,Miami Univeristy,Oxford,OH 45056,USA

2 School of Mathematical and Statistical Sciences,and School of Computing and Augmented Intelligence,Arizona State University,Tempe,AZ 85281,USA

3 School of Mathematical Sciences,University of Science and Technology of China,Hefei,Anhui 230026,China

Abstract.We show that for every rational number r(1,2)of the form 2-a/b,where a,bN+ satisfythere exists a graph Fr such that the Turán number ex(n,Fr)Θ(nr).Our result in particular generates infinitely many new Turán exponents.As a byproduct,we formulate a framework that is taking shape in recent work on the Bukh–Conlon conjecture.

Key words: Extremal graph theory,turán exponents,bipartite graphs.

1 Introduction

Given a familyFof graphs,the Turán number ex(n,F)is defined to be the maximum number of edges in a graph onnvertices that contains no graph from the familyFas a subgraph.The classical Erds–Stone–Simonovits theorem shows that arguably the most interesting problems about Turán numbers,known as the degenerate extremal graph problems,are to determine the order of magnitude of ex(n,F)whenFcontains a bipartite graph.The following conjecture attributed to Erds and Simonovits is central to Degenerate Extremal Graph Theory (see [16,Conjecture 1.6]).

Conjecture 1.1(Rational Exponents Conjecture).For every finite familyFof graphs,ifFcontains a bipartite graph,then there exists a rational[1,2) and a positive constantcsuch that ex(n,F)cnr+o(nr).

Recently Bukh and Conlon made a breakthrough on the inverse problem [16,Conjecture 2.37].

Theorem 1.1(Bukh and Conlon [3]).For every rational number r(1,2),there exists a finite family of graphs Fr such thatex(n,Fr)Θ(nr).

Motivated by another outstanding problem of Erds and Simonovits (see [10,Section III]and[11,Problem 8]),subsequent work has been focused on the following conjecture,which aims to narrow the familyFrin Theorem 1.1 down to a single graph.

Conjecture 1.2(Realizability of Rational Exponents).For every rational number(1,2),there exists a bipartite graphFrsuch that ex(n,Fr)Θ(nr).?Erds and Simonovits asked a much stronger question: for every rational number r(1,2),find a bipartite graph Fr such that ex(n,Fr)cnr+o(nr) for some positive constant c.

It is believed that the graphFrin Conjecture 1.2 could be taken from a specific yet rich family of graphs,for which we give the following definitions.

Definition 1.1.A rooted graph is a graph F equipped with a subset R(F)of vertices,which we refer to as roots.We define the pth power of F,denoted Fp,by taking the disjoint union of p copies of F,and then identifying each root in R(F),reducing multiple edges (if any) between the roots.

Definition 1.2.Given a rooted graph F,we define the density ρF of F to be e(F)/(v(F)-|R(F)|),where v(F)and e(F)denote the number of vertices and respectively edges of F.We say that a rooted graph F is balanced if ρF ＞1,and for every subset S of V(F)R(F),the number of edges in F with at least one endpoint in S is at least ρF|S|.

Indeed the next result on Turán numbers,which follows immediately from [3,Lemma 1.2],establishes the lower bound in Conjecture 1.2 for some power of a balanced rooted tree.?A rooted tree is a rooted graph that is also a tree,not to be confused with a tree having a designated vertex.

Figure 1: Ts,t,s′ with roots in black.

Lemma 1.1(Bukh and Conlon [3]).For every balanced rooted tree F,there exists pN+such thatex(n,Fp)Ω(n2-1/ρF).

It is conjectured in [3] that the lower bound in Lemma 1.1 can be matched up to a constant factor.

Conjecture 1.3(The Bukh–Conlon Conjecture).For every balanced rooted treeFand everyN+,ex(n,Fp)O(n2-1/ρF).

Given the fact that every rational number bigger than one indeed appears as the density of some balanced rooted tree (see [3,Lemma 1.3]),Lemma 1.1 and Conjecture 1.3 would imply Conjecture 1.2.Our main result establishes Conjecture 1.3 for certain balanced rooted treesTs,t,s′defined in Fig.1.

Theorem 1.2.N+and s′N,when s-s′≥2assume in addition that t ≥s3-1.If the rooted tree F:Ts,t,s′ is balanced,then for every pN+,ex(n,Fp)O(n2-1/ρF),where ρF(st+t+s′)/(t+1).

It is not hard to characterize the parameterss,t,s′for whichTs,t,s′is balanced.

Proposition 1.1.N+and s′N,the rooted tree FTs,t,s′ is balanced if and only if ρF ≥max(s,s′)and ρF ＞1,or equivalently s′-1≤s≤t+s′ and(t,s′)(1,0).

Prior to our work,Conjecture 1.3 has been verified for the balanced rooted trees in Fig.2: theandPtcases are classical results due to Kvári,Sós and Turán[23],and respectively Faudree and Simonovits [13];Qs,1andS2,1,0are due to Jiang,Ma and Yepremyan[18];Qs,tandT4,7are due to Kang,Kim and Liu[22];andSs,t,0are due to Conlon,Janzer and Lee [6];andK(3)sare due to Jiang and Qiu [20];is due to Janzer[17];andSs,t,t′for allt′≤tis very recently settled by Jiang and Qiu [19].

Figure 2: Balanced rooted trees,where s,t,t′ refer to vertices,except t in Qs,t.

These recent attacks on the Bukh–Conlon conjecture are full of interesting and promising techniques.In this paper,inspired by these previous attempts,we formulate an underlying framework that centers around a notion which we call negligible obstructions (Definitions 2.4 and 2.5).In this context,we develop a lemma(Lemma 2.1),which we call the negligibility lemma,to connect negligible obstructions with the Bukh–Conlon conjecture.To our best knowledge,ideas in our formulation of the framework can be traced back to the work of Conlon and Lee [7],and can be spotted throughout later work by various authors.

To establish an instance of the Bukh–Conlon conjecture,the negligibility lemma naturally leads to a two-step strategy: the identification of obstructions and the certification of their negligibility.By no means we claim that this strategy reduces the difficulty of Conjecture 1.3.Nevertheless we propose this strategy in hopes that it will bring us one step closer to pinning down a handful of essentially different techniques in this area,akin to the theory of flag algebras [24].

We illustrate the above two steps with the proof of Theorem 1.2.In contrast with all the previous work which has the inductive flavor of certifying negligibility of larger obstructions by that of the smaller,our implementation of the second step has a distinctive inductive pattern,which is elaborated at the end of Section 2.We point out that although Theorem 1.2 can be seen as an extension of [22,Section 3]which dealt withQs,t,our approach is quite different.

Turning to realizability of rational exponents,our main result Theorem 1.2 gives realizability of the following rational exponents.

Corollary 1.1.For every rational number r(1,2)of the form2N+,if

then there exists a bipartite graph Fr such that

Proof.In casea1,Eq.(1.1) forcesb1,which contradicts with the assumption thatr ＞1.Hereafter we assume thata ≥2.Now takes,ta-1 ands′b-(a-1)(+1).SetTTs,t,s′.One can easily check thatN+,ρT(st+t+s′)/(t+1)b/aand soρT ＞1,ρT ≥sands′≤b-(a-1)b/aρT.Observe that Eq.(1.1) is equivalent tot≥s3-1 ands′≥0.In view of Proposition 1.1,Tis balanced.The corollary follows from Lemma 1.1 and Theorem 1.2 immediately.

As far as we know,all the rationals in (1,2) for which Conjecture 1.2 has been verified can be derived from Lemma 1.1 and the existing instances of Conjecture 1.3.For convenience,we say a fractionb/ais a Bukh–Conlon density if there exists a balanced rooted treeFsuch thatρFb/aand ex(n,Fp)O(n2-1/ρF) for everyN+.Kang,Kim and Liu observed in [22,Lemma 4.3] that a graph densification operation due to Erds and Simonovits [12] can be used to generate more Bukh–Conlon densities: wheneverb/ais a Bukh–Conlon density,so ism+b/afor everyN.

It appears reasonable to restrict our attention to the fractionsb/aof the formm+s/awhereN+,for fixedN withs＜a.The results listed in Fig.2 yield Bukh–Conlon densitiesm+s/afor everyN+whenevers「(a-1)/(s+1)1.§Combining [22,Lemma 4.3] with the results listed in Fig.2 (essentially with the one on Ss,t,t′),we know that m+s/(st+t′+1) is a Bukh–Conlon density for m,sN+ and t,t′N with t′≤t.For m+s/a to be a fraction of such form,one needs st+1≤a≤st+t+1 for some tN,or equivalently s「(a-1)/(s+1)≤a-1.For many choices of (s,a),for example (4,7),(5,8) or (7,10),it was not known whetherm+s/ais a Bukh–Conlon density for anyN+.For comparison,the family of fractionsb/agiven by Eq.(1.1)generates the Bukh–Conlon densitiesm+s/afor allm≥a-s-1 whenevera-1-In particular,our result gives new Bukh–Conlon densities of the formm+5/8 andm+7/10 as long asm≥2.Unfortunately our result does not give any Bukh–Conlon densities of the formm+4/7.The above discussion leads us to the following conjecture on Bukh–Conlon densities.

Conjecture 1.4.For everyN withs＜a,there existsN+such thatm+s/ais a Bukh–Conlon density.

We point out that one would settle Conjecture 1.4 if one could remove the technical conditiont≥s3-1 from Theorem 1.2.

Remark 1.1.After this work is completed,Conlon and Janzer [5],partly building on our ideas,improved Theorem 1.2 by removing the technical conditiont≥s3-1,and they hence resolved Conjecture 1.4.

The rest of the paper is organized as follows.In Section 2,we flesh out the aforementioned framework,and use it to prove Theorem 1.2.In Section 3,we prove the negligibility lemma.In Sections 4 and 5,we certify the negligibility of two different obstructions needed for the proof of Theorem 1.2.

2 Negligible obstruction family

Throughout the rest of the paper,when we view a treeFas a rooted tree,by default the root setR(F) ofFconsists exactly of the leaves ofF.We useV(G) andE(G)to denote the vertex set and the edge set ofGrespectively.

To motivate the relevant concepts,it is instructive to think about finding a copy ofFpin ann-vertexd-regular graphG,whereFis a tree and

We mostly talk about embeddings rather than subgraphs.

Definition 2.1(Embedding).Given a tree F and a graph G,denoteInj(F,G)the set of embeddings from F to G,that is,the set of injections η:V(F)→V(G)such that η(e)(G)(F).For a subset U of R(F)and an injection σ:U →V(G),denote the set of embeddings from F to G relativized to σ by

When we write these operators (and the ones coming later) in lowercase,we refer to their cardinalities,for example,

Remark 2.1.We encourage the readers who are accustomed to counting subgraphs to think of the embedding counting inj(F,G)as the corresponding subgraph counting ofFinG,because they merely differ by a multiplicative factor depending only onF.We choose embeddings over subgraphs based on the pragmatic reason that it is more succinct to write in the language of embeddings when counting relativized to some injectionσ.

Note that

as one can embedFintoGone vertex at a time.Because

by the pigeonhole principle,there existsσ:R(F)→V(G) such that inj(F,G;σ)ω(1).Ideally the images ofV(F)R(F)under somepembeddings in Inj(F,G;σ)are pairwise (vertex) disjoint,and thus suchpembeddings would give us a copy ofFpinG.To that end,we define the following notion.

Figure 3: After adding U to the root set of T3,4,2,the resulting rooted graph contains K1,4 as a rooted subgraph.

Definition 2.2(Ample embedding).Given a tree F and a graph G,for ηInj(F,G),we say η is C-ample if there exist η1,···,ηCInj(F,G)such that ηi and η are identical on R(F),and the images of V(F)R(F)under η1,···,ηC are pairwise disjoint.Given CN,denoteAmpC(F,G)the set of C-ample embeddings from F to G.For a subset U of R(F)and an injection σ:U →V(G),the relativized version ofAmpC(F,G),denoted byAmpC(F,G;σ),is justAmpC(F,G)∩Inj(F,G;σ).

However it could happen that many embeddings in Inj(F,G;σ)map a nonempty subset ofV(F)R(F) in the same way,thus preventing us from finding ap-ample embedding in Inj(F,G;σ).These possible obstructions are encapsulated in the following definitions.

Definition 2.3(Rooted subgraph).Given two rooted graphs F1and F2,we say that F2contains F1as a rooted subgraph if there exists an embedding η from F1to F2such that for every vV(F1),η(v)(F2)if and only if vR(F1).

Definition 2.4(Obstruction family).Given a tree F,a family F0of trees is an obstruction family for F if every member of F0is isomorphic to a subtree of F that is not a single edge,and moreover for every nonempty proper subset U of V(F)R(F),after adding U to the root set of F,the resulting rooted graph contains a member of F0as a rooted subgraph (see Fig.3,Proposition2.1for a concrete example of an obstruction family).

The following definition quantifies the conditions on the obstruction family forFthat ensure the existence of ap-ample embedding fromFtoG.

Definition 2.5(Negligible obstruction).Given two trees F0and F,we say that F0is negligible for F if for every pN+and ε ＞0there exist c0＞0and C0Nsuch that the following holds.For every c＞c0and every n-vertex graph G with n≥n0(c),if every vertex in G has degree between d and Kd,where dcnα,K54/α and α1-1/ρF,and moreoverampp(F,G)0,then

An obstruction family for F is negligible if every member of the family is negligible for F.

Remark 2.2.As we shall see later in Sections 4 and 5,when certifying the negligibility of an obstruction family,the concrete form ofKis unimportant as long as it depends only onF.However,since we only need that specificKfor Lemma 2.1 to work,we state it explicitly to avoid introducing an additional universal quantifier in Definition 2.5.

We wrap up the above discussion in the following lemma,and we postpone its proof to Section 3.

Lemma 2.1(Negligibility lemma).Given a tree F,if there exists a negligible obstruction family F0for F,thenex(n,Fp)O(n2-1/ρF)N+.

The negligibility lemma provides us a two-step strategy to establish Conjecture 1.3 for a balanced rooted treeF: first identifying an obstruction familyF0forF,and second certifying the negligibility ofF0.Although in the first step there might be multiple obstruction families forF,heuristically speaking it makes more sense to chooseF0that is minimal under inclusion,because all the heavy lifting happens in the second step that certifies the negligibility of each member ofF0.

Coming back to the treeTs,t,s′defined in Fig.1,we choose the following obstruction family which is indeed minimal under inclusion.

Proposition 2.1.N+and s′N,if(t,s′)(1,0),then the family{K1,s+1}∪{Ts,t-i,s′+i: 1≤i≤s-s′} is an obstruction family for Ts,t,s′.

Proof.LetFTs,t,s′,and letUbe a nonempty proper subset ofP ∪Q,wherePandQare vertex subsets ofV(F) defined in Fig.4.LetF+be the rooted graph after addingUto the root setR(F) ofF.IfUcontains the vertex inP,thenF+containsK1,s+1as a rooted subgraph.OtherwiseU ?Q.In this case,F+containsTs,t-i,s′+ias a rooted subgraph,wherei|U|.Finally notice that whens′+i≥s+1,Ts,t-i,s′+icontainsK1,s+1as a rooted subgraph,and so doesF+(see Fig.3 for an example).

Theorem 1.2 follows immediately from the next theorem which certifies the negligibility of the obstruction family defined in Proposition 2.1.

Theorem 2.1.N+and s′N,when s-s′≥2,assume in addition that

Figure 4: Vertex partition of Ts,t,s′.

If T:Ts,t,s′ is balanced,then for every pN+and ε ＞0,there exists c0＞0such that the following holds.For every c＞c0and every n-vertex graph G with n≥n0(c),if every vertex in G has degree between d and Kd,where dcnα,K54/α and α1-1/ρT,and moreoverampp(T,G)0,then

Proof of Theorem1.2. Suppose thatT:Ts,t,s′is balanced.Whens≤s′,the obstruction family forTconsists of a singleK1,s+1,which by Theorem 2.1(a) is negligible forT.Whens-s′1,in view of Theorem 2.1,the obstruction familyF0defined in Proposition 2.1 is also negligible.Whens-s′≥2,F0is negligible provided Eq.(2.1).Observe thatt ≥s3-1 ensures Eq.(2.1).Indeed,the right hand side of Eq.(2.1)is at mostk2(s+2-k)+1/s,which,by the inequality of arithmetic and geometric means,is at most (2(s+2)/3)3/2+1/s,which is at mosts3-1 fors ≥3.One can check directly in cases2 that the right hand side of Eq.(2.1)is less than 7.In any case,it then follows from Lemma 2.1 that ex(n,Tp)O(n2-1/ρF) for allN+.

Our proof of Theorem 2.1 is inductive in nature.In Section 4 we first establish the negligibility ofK1,s+1in Theorem 2.1(a).In Section 5 we deduce the negligibility ofFkin Theorem 2.1(b)from that ofK1,s+1andF1,···,Fk-1.The inductive pattern here is counterintuitive in the sense that the negligibility ofFk,which is a subgraph ofFk-1,comes after that ofFk-1.

3 Proof of the negligibility lemma

In Section 2,we have analyzed the special case where the graphGis regular.In the context of degenerate extremal graph theory,it is indeed standard to assume thatGis almost regular.This idea due to Erds and Simonovits first appeared in [12].We shall use the following variant (see also [21,Proposition 2.7] for a similar result).

We now formalize the discussion in Section 2 on finding a copy ofFpinG.

Definition 3.1(Extension).Given two trees F1,F2and a graph G,for η1Inj(F1,G)and η2Inj(F2,G),we say η2extends η1if η1η2?η12for some embedding η12Inj(F1,F2)N,denote

We can estimate the cardinality ofIby

and so

if we had chosenn0(c) large enough.

By the pigeonhole principle,the cardinality ofIσ:I∩Inj(F,G;σ) is at leastce(F)/2 for someσ:R(F)→V(G).For everyU ?V(F)R(F) and every injectionτ:U →V(G),set

Claim.For everyU ?V(F)R(F) andτ:U →V(G),

Proof of Claim.We prove by backward induction on|U|.Clearly|Iσ(τ)|≤1 when the domainUofτequalsV(F)R(F).SupposeUis a proper subset ofV(F)R(F).Recall from Definition 2.4 that after addingUto the root set ofF,the resulting rooted graph containsF0as a rooted subgraph that is isomorphic to a member ofF0.Notice thatU0:V(F0)R(F0) is nonempty becauseF0is not a single edge.

Let(τ) be a maximal subset ofIσ(τ) such that the images ofU0under the embeddings in(τ) are pairwise disjoint,and letV0be the union of these images.SinceIσ(τ)?IandIdefined by Eq.(3.1) contains no extension of anyC0-ample embedding fromF0toG,we bound(τ)|＜C0,which implies that|V0|＜C0|U0|.For each0and0,by the inductive hypothesis

whereτuv:U ∪{u}→V(G) extendsτby mappingutovadditionally.The maximality of(τ)means that for every(τ)there is0such thatη(u)0,and so(τuv) for some0.Therefore

which implies the inductive step as|U0|＜v(F) and|V0|＜C0|U0|.

The same argument works for the last inductive step whereU?because there is nop-ample embedding fromFtoG,andC0≥p.

In particular,IσIσ(τ) when the domain ofτis an empty set,and so

which would yield a contradiction if we had chosen

This completes the proof.

4 Ample embeddings of stars

The negligibility ofK1,s+1forTs,t,s′is established directly through the following technical lemma.

Lemma 4.1.N+and s′N,set s0max(s′,1),F0,F1K1,s+1and TTs,t,s′.For every pN+and ε ＞0,there exists c0＞0such that for every n-vertex graph G,ifampp(T,G)0andinj(F0,G)≥c0ns0,then(F1,G)≤εinj(F1,G),where C1

Our proof of Lemma 4.1 follows the outline of [6,Lemma 5.3].Over there the conclusion,in our language,is that for everyε＞0 there existsC1N such that

One can work out the quantitative dependencyC1Ω(ε-1/(s-1)) from their argument.Although this dependency alone is enough for the negligibility ofK1,s+1,it becomes inadequate when we iteratively apply this bound later in Section 5.To decoupleC1fromεin Lemma 4.1,we need the following classical result in degenerate extremal hypergraph theory.

Theorem 4.1(Erds [9]).For every r-partite r-uniform hypergraph H there exists ε＞0so thatex(n,H)O(nr-ε).?Given an r-uniform hypergraph H,the Turán number ex(n,H) is the maximum number of hyperedges in an r-uniform hypergraph on n vertices that contains no H as a subhypergraph.

Proof of Lemma4.1. Suppose thatGis ann-vertex graph such that ampp(T,G)0 and inj(F0,G)≥c0ns0,wherec0is to be chosen.As we only deal with embeddings toGin the following proof,we omitGin Inj(·,G),Amp·(·,G) and their relativized versions.

Recalls0max(s′,1).ClearlyGcontains noFpas a subgraph,whereFLetU0denote an arbitrary vertex subset of sizes0inG,and denoteNG(U0) the common neighborhood ofU0inG.LetHbe the (s+1)-uniform hypergraph onV(G) given by

Claim 4.1.There existsn0n0(s,t,p,C1)N such that for everyU0with|NG(U0)|≥n0,

Observe thatH[NG(U0)]never containsH0as a subhypergraph.Suppose on the contrary that there exists an embeddingηfromH0toH[NG(U0)],‖Given two hypergraphs H1 and H2 of the same uniformity,an embedding from H1 to H2 is just an injection η: V(H1)→V(H2) such that η(e)H2 for every eH1.then we can embedFpinGby mappingS′(F)toU0,mappingP(Fp)∪S(F)according toη,and embedding the vertices inQ(Fp)greedily.The last step of the embedding is possible because for every hyperedge0,η(e)η′(R(F1)) for someη′(F1),and more importantlyC1≥v(Fp).

SinceH0is an (s+1)-partite hypergraph,the claim follows from Theorem 4.1 immediately.

We choose suchn0N in Claim 4.1 and require in addition thatn0≥s+1.For convenience,set

Claim 4.2.The number ofC1-ample embeddings fromF1toGsatisfies

Proof of Claim4.2. Letσdenote an arbitrary injection fromR(F1) toV(G),and denote for shorta(σ)(F1;σ).Note thata(σ) has the dichotomy that eithera(σ)0 ora(σ)≥C1≥s0,which implies that

in either case.Through counting in two ways the disjoint union of the edge sets ofH[NG(U0)] for all vertex subsetsU0of sizes0inG,one can show that

which implies the desired inequality in the claim.

Claim 4.3.The number of embeddings fromF1toGsatisfies

On the one hand,for a fixedU0with|NG(U0)|≥n0,every subset ofNG(U0) of sizes+1 that is not a hyperedge ofH[NG(U0)] gives rise to at leasts0(s+1)! many(U0),and it follows from Claim 4.1 that

Thus we get

which implies the desired inequality in the claim.

A simple double counting argument shows that

Recall the assumption that inj(F0)≥c0ns0.Thus the average ˉNof|NG(U0)|satisfies

We can choosec0＞0 large enough so that

By Jensen’s inequality,we have

which implies that

Applying Claim 4.2 and then Claim 4.1,we get

which implies

Comparing it with Claim 4.3,we get the desired inequality in Lemma 4.1.

Proof of Theorem2.1(a). ForN+ands′N,sets0max(s′,1),andTTs,t,s′.SinceTis balanced,by Proposition 1.1,s0≤s+1 andρT ≥s0,the latter of which implies that 1+s0α≥s0,whereα1-1/ρT.

Since 1+s0α≥s0,we have

5 Ample embeddings of subtrees

5.1 Preliminary propositions

For the proof of Theorem 2.1(b),we need the following variation of the classical sunflower lemma for sequences(see[2]for the recent breakthrough on the sunflower conjecture of Erds and Rado [8] and related background).

Proof.Consider the systemFof subsets ofVdefined by

Clearly|W|≤k!|F|.We claim thatFcontains no sunflower of sizek!C.Recall that a sunflower is a collection of sets whose pairwise intersection is constant.Assuming the claim,the classical sunflower lemma precisely states that|F|＜k!(k!C-1)k,which implies the desired inequality.Suppose on the contrary thatE ?Fis a sunflower of sizek!Cwith kernelK.Consider the subsystem of sequencesW0{(s1,···,sk):{s1,···,sk}E}.Clearly|W0|≥k!C.By the pigeonhole principle,there exist a setW1?W0of sizeCandI[k] such that for every1,{si:Kand(si)iIis a constant subsequence.AsEis a sunflower,one can check thatW1is a sequential sunflower of sizeC,which is a contradiction.

We also need the following classical theorem due to Kvári,Sós and Turán [23]on the Zarankiewicz problem.

Proposition 5.2.N+.Suppose that H is a bipartite graph with two parts U and W such that every vertex in W has degree at least s.If H contains no complete bipartite subgraph with s vertices in U and t vertices in W,then

The following result is a generalization of a result due to F¨uredi [15].Our proof of the generalization follows the proof of F¨uredi’s result by Alon,Krivelevich,and Sudakov [1] using dependent random choice (see [14] for a survey on dependent random choice).We denotedG(v) the degree of a vertexvinG.

Proposition 5.3.N+such that k＜r.Suppose that F is a bipartite graph with two parts U0and W0such that every vertex in W0has degree at most r.For every bipartite graph G with two parts U and W,if there is no embedding η from F to G such that η(U0)?U and η(W0)?W,then

where

Proof.Assume for the sake of contradiction that

Pick a subsetW1?Wof sizeruniformly at random with replacement.SetU(W1)?Uto be the common neighborhood ofW1inG,and letXdenote the cardinality ofU(W1).By linearity of expectation and H¨older’s inequality,

LetYdenote the random variable counting the number of subsetsS?U(W1)of sizerwith fewer than|W0|common neighbors inG.For a given suchS,the probability that it is a subset ofU(W1) is less than (|W0|/|W|)r.Since there are at mostsubsetsSof sizer,it follows that

By linearity of expectation,

Hence there exists a choice ofW1for whichX-Y ≥|U0|.Delete one vertex from each subsetSofU(W1)of sizerwith fewer thanmcommon neighbors.We letU′be the remaining subset ofU(W1).The setU′?Uhas at least|U0|vertices,and every subset ofU′of sizerhas at least|W0|common neighbors.One can then greedily find an embeddingηfromFtoGsuch thatη(U0)?U′andη(W0)?W.

5.2 Proof of Theorem 2.1(b)

We inductively deduce the negligibility ofFkby that ofF1,···,Fk-1,whereFkTs,t-k,s′+k.In each inductive step,we also need to set aside the embeddings fromFktoGthat extend the ample embeddings fromK1,s+1toGwhich were already dealt with in Lemma 4.1.Recall ExtC(F1,F2,G) from Definition 3.1,and that extC(F1,F2,G) denotes its cardinality.

In the rest of the section,s,t,pare fixed parameters andnis a parameter that goes offto infinity.For two quantitiesa,bwithb＞0 that possibly depend onn,we writea?bif there existCC(s,t,p)＞0 andn0N such thata≤Cbfor alln≥n0.

Figure 5: F0, F1 and F2.

For every c＞1and n-vertex graph G,if every vertex in G has degree between d and Kd,where dcnα and K54/α,and moreover(F0,G)0,then

Proof.As we mostly deal with embeddings toG,we omitGin Inj(·,G),Amp(·,G),Ext(·,·,G) and their relativized versions.

Letv0,v1,···,vkbe defined forF0,···,Fkas in Fig.5,and letSibe the set of roots which are adjacent tovifor[k].We viewFias a subtree ofFi-1induced onV(Fi-1)Si.Letσdenote an arbitrary injection fromR(Fk){v1,···,vk}toV(G),and set

whose edge set is given by

andBσhas the distinctness property in the sense that

Without loss of generality,we may assume thatI[k][k-i]for some0,···,k-1}.Clearly

Because the total number ofσ′:R(F0)→V(G) such thatσ′?σis at mostnsk,summing the last inequality over allσ′,together with Eq.(5.2),yields

which implies the desired inequality in view of Eq.(5.4) and the assumption that(F0)0.

Claim 5.3.For everyσ,the number of edges insatisfies

Now we treat thek1 case and thek≥2 case separately.

For convenience,denoteN(U0)the vertex set of thek-uniform hypergraphW(U0).AsW(U0) contains no matching of sizep,clearly we have

and so

which implies the desired inequality in Claim 5.3.

The base casei1 is evident as the maximum degree ofGis at mostKd.For the inductive step,consider an arbitraryU ?Uσof sizei-1 and denoteuan arbitrary vertex inUσU.Clearly

LetU′denote an arbitrary subset ofUσof sizei.Summing the above inequality over allU ?Uσof sizei-1,we obtain from the inductive hypothesis that

Before we assemble Claims 5.1 to 5.3 together,we observe that

Using the assumption 1-1/s≤α,we estimate that

Therefore,in view of Eq.(5.7),we have

Summing over all injectionsσ:R(Fk){v1,···,vk}→V(G) yields

Case 2:k≥2.We take

Ass′＜s,one can check that+1,and soα＜s/(s+1),which impliess-(s+1)α＞0.Hencem0ω(1).We claim that the condition Eq.(5.1) ontimplies that

Indeed,usingα1-1/ρF0(st+s′-1)/(st+t+s′),one can check that Eq.(5.1) is equivalent to

which implies the first inequality in Eq.(5.8).To see that the second inequality follows from the first inequality in Eq.(5.8),in view of the fact thatnαdk-1≥nkαasdcnαandc＞1,it suffices to check that

which is equivalent tosk(k-1)(s-k+1)+(k-1)2≥0,which clearly holds.

Using Eq.(5.8),we can simplify Claim 5.3 to

Combining this with Claim 5.2,we obtain for everyσthat

Summing over all injectionsσ:R(Fk){v1,···,vk}→V(G) yields that

This completes the proof of Lemma 5.1.

Case 1:k1.Letc0be at least the constant already obtained from Theorem 2.1(a).By the choice ofc0,we know that

which implies the desired inequality in Theorem 2.1(b).

Case 2:2≤k≤s-s′.By induction,there existsc0≥1/εsuch that(Fi,G)≤εnde(Fi) for every 1≤i ＜k.Note that the assumption Eq.(2.1) in Theorem 2.1 ensures the condition Eq.(5.1) in Lemma 5.1.By Lemma 5.1 and the assumption 1/c＜ε,we similarly obtain that(Fk,G)?εnde(Fk).

Acknowledgements

We are grateful to Boris Bukh and Ryan Alweiss for comments on the earlier versions of this paper.We are thankful to the anonymous referees for their astute and useful comments.

T.Jiang is supported in part by U.S.taxpayers through the National Science Foundation (NSF) grant DMS-1855542.The work was done when Z.Jiang was an Applied Mathematics Instructor at Massachusetts Institute of Technology,and was supported in part by an AMS Simons Travel Grant,and by U.S.taxpayers through NSF grant DMS-1953946.J.Ma is supported in part by the National Key R&D Program of China 2020YFA0713100,National Natural Science Foundation of China grants 11622110 and 12125106,and Anhui Initiative in Quantum Information Technologies grant AHY150200.