On the extremal function for graph minors
Andrew Thomason Matthew Wales
math.CO 05C83



  For a graph H, let
  c(H)=inf{c : e(G)≥ c|G|  G≻ H }, where
  G≻ H means that H is a minor of G. We show that if H has
  average degree d, then

    c(H)≤ (0.319…+o_d(1))|H|√(log d)

where 0.319… is an explicitly defined constant.
This bound matches a corresponding lower bound shown to hold for almost all
such H by Norin, Reed, Wood and the first author.


 COHERENT constraints after the COHERENT-2020 quenching factor measurement
    D.K. Papoulias
    December 30, 2023
==========================================================================





§ INTRODUCTION


A graph H is a minor of G, written G≻ H, if there exist
non-empty disjoint subsets U_v⊂ V(G), v∈ V(H), such that each
G[U_v] is connected, and there is an edge in G between U_v and U_w
whenever vw is an edge in H. Thus H can be obtained from G by a
sequence of edge contractions and deletions and vertex deletions.
	
It is natural to ask, for a given H, what conditions on a graph G
guarantee that it contains H as a minor. Mader <cit.> proved
the existence of the extremal function c(H), defined as follows.


  For a graph H, let
  c(H) = inf{  c :  e(G)≥ c|G|  G≻ H }.


Mader <cit.> later proved the bound c(K_t)≤ 8tlog_2t for the
complete graph H=K_t. Bollobás, Catlin and Erdős <cit.>
realised that random graphs G=G(n,p) give a good lower bound for
c(K_t). Indeed, by choosing n and p suitably, one obtains
c(K_t)≥(α+o(1))t√(log t), where the constant α is
described here.
 The constant α is given by

    α = max_0<p<1p/2√(log(1/(1-p))) = 0.319… ,

with p=0.715…
giving the maximum value.


Kostochka <cit.> (see also <cit.>) proved that
c(K_t) is in fact of order t√(log t). Finally, it was
shown <cit.> that c(K_t)=(α+o(1))t√(log t).

Myers and Thomason <cit.> considered general graphs H with t
vertices and at least t^1+τ edges.  They defined a graph parameter
γ(H) and proved that 
c(H)=(αγ(H)+o(1)) t√(log
  t). We say more about γ(H) in <ref>, but here it is
enough to say that γ(H)≤√(τ), and in fact
c(H)=(α√(τ)+o(1)) t√(log t) for almost all H with
t^1+τ edges, and for all regular H of this kind.
Myers <cit.> further showed that the extremal graphs are all
essentially disjoint unions of pseudo-random graphs (in the sense
of <cit.>) having the same order and density as the random
graphs discussed above. Thus c(H) is determined very precisely when
τ is bounded away from zero, but these results give little useful
information when τ=o(1).

Reed and Wood <cit.> realised that it is better to
express c(H) in terms of the average degree d of H. For example, the
results just mentioned imply that c(H)≤(α+o(1)) |H|√(log d)
if log d  o(log |H|), with equality in many cases. Reed and Wood
showed that c(H)≤ 1.9475|H|√(log d) holds for all H, provided
d is large.

The actual behaviour of c(H) can be qualitatively different, though, when
log d = o(log |H|), because random graphs themselves cannot serve as
extremal graphs. In fact, Alon and Füredi <cit.> showed that,
if the maximum degree of H is at most log_2 |H|, then the random graph
G(|H|,p) almost surely contains H as a spanning subgraph when
p>1/2. Indeed, c(H) can be much smaller than |H|√(log d), even
if H is regular: Hendrey, Norin and Wood <cit.> have shown that
c(H)=O(|H|) when H is a hypercube.

But this kind of behaviour turns out to be rare. Norin, Reed, Thomason and
Wood <cit.> recently found a different class of graphs that can serve
as extremal graphs. These are blowups of small random graphs but are not
themselves random (though they are pseudo-random). Their method showed that
c(H)≥ (α +o_d(1))|H|√(log d) holds for almost all H of
average degree d. (More exactly, given ϵ>0 and
d>d_0(ϵ), then for each t>d, when H is chosen at random with
t vertices and average degree d, we have
[c(H)> (α -ϵ)t√(log d)] > 1-ϵ.)  The bound on
c(H) was conjectured to be tight; that is,
c(H)= (α +o_d(1))|H|√(log d) almost always.

Our main purpose here is to prove the next theorem, which strengthens the
result of Reed and Wood <cit.> and, in particular, settles the
aformentioned conjecture positively.



  Given ϵ>0, there exists D(ϵ), such that if
  d>D(ϵ) then every graph H of average degree d satisfies
  c(H) < (α+ϵ)|H|√(log d).


The proof follows very broadly the strategy of <cit.>, used also
in <cit.>. It splits into two cases. The first is where G has
density bounded away from zero, and is reasonably connected; this is
addressed in <ref>. The second case is where G is itself sparse
but still has dense vertex neighbourhoods as well as reasonable
connectivity; this is dealt with in <ref>. Nevertheless the
methods of <cit.> are not adequate to handle the situation
where |H| is much bigger than d, and new ideas are needed. These are
described in the appropriate sections.

Our notation is more or less standard. For example, given a graph H, then
(as used above) |H| denotes the number of vertices, e(H) the number of
edges, and δ(H) the minimum degree. If X is a subset of the vertex
set V(H) then Γ(X) denotes the set of vertices not in X that
have a neighbour in X. The subgraph of H induced by X is denoted
by H[X].

The proof of Theorem <ref> begins with the following
families of graphs.


  Let > 1 and 0≤ k≤/2 be real numbers. Define
  
    = { G : G≥ , 
        e(G)>G-k } .



The main usefulness of the class  to the study of c(H),
demonstrated by Mader <cit.>. is that a minor-minimal element of
 (that is, a graph G∈ which has no proper minor in
) enjoys the properties set out in the next lemma.


  
  Let G be a minor-minimal element of ℰ_,k. Then
  |G|≥+1, e(G)≤|G|-k+1,
  <δ(G)<2, κ(G)>k, and every edge of G is
  in more than -1 triangles.


  The proof is standard and elementary (see for
  example <cit.>), though usually  and k are
  taken to be integers, so we provide a brief sketch. There are no graphs
  G∈ with ≤ |G| < +1 because in this range
  |G| 2 < |G|-k. Hence the removal of a vertex
  of G, or the contraction or removal of an edge, violates the size
  condition, which yields all the claimed properties except
  κ(G)>k. To obtain this, consider a cutset S and a component W
  of G-S. The condition δ(G)> implies that both the
  minors G[W∪ S] and G∖ W have more than 
  vertices, and hence
  
    e(G) ≤ e(G[W∪ S])+e(G∖ W)≤(|W|+|S|)-k+(|G|-|W|)- k

  yielding |S|>k as claimed.


We now state the main theorems of Sections 2 and 3 respectively, and show
how they imply Theorem <ref> .


[]theoremsectwothm

Given ϵ >0, there exists D_1(ϵ), such that
if H is a graph of average degree d>D_1, and G is a graph of density at
least p+ϵ, with the properties ϵ < p <1-ϵ,
|G|≥ |H|√(log_1/(1-p)d) and κ(G)≥ϵ |G|, then
G≻ H.


[]theoremsecthreethm

Given ϵ >0, there exists D_2(ϵ), such that, if H is a
graph of average degree d>D_2,  is a number with
≥ϵ|H|√(log d), and G is a graph satisfying
|G|≥ D_2, κ(G)≥ D_2|H|, e(G)≤|G| and
every edge of G lies in more than -1 triangles, then
G≻ H.




  We may assume that 0<ϵ <1/4. Let H be a graph of average
  degree d, let = (α+ϵ)|H|√(log d) and let
  k = ϵ/2. We need to show that G≻ H provided
  e(G)≥|G| and D(ϵ) is large. Now G∈, and
  (replacing G by a minor of itself if necessary) from now on we assume
  that G is minor minimal in  (note that we thereby forego the
  inequality e(G)≥|G| but we still have 
e(G)>
  |G|-k). Thus G
  has all the properties stated in Lemma <ref>. We may assume
  that D(ϵ)
  is large enough that ϵ(α+ϵ)√(log d)/2 > D_2, where
  D_2=D_2(ϵ) is the constant of Theorem <ref>, and
  therefore κ(G)> k> D_2|H|. Thus if G≥
  D_2, then G satisfies the conditions of
  Theorem <ref> (provided D(ϵ)>D_2) and G≻
  H. 
  So suppose instead that G<
  D_2. Then e(G)>|G|-k ≥|G|(1-ϵ/2), so G has density at least
  2(1-ϵ/2)/(|G|-1)>1/D_2.  Let ϵ'=ϵ/2D_2,
  and let p+ϵ' be the density of G, so ϵ' < p <
  1-ϵ'. Observe that p>1/2D_2 so ϵ p>ϵ'. Therefore
  p(1+ϵ)> p+ϵ' >2(1-ϵ/2)/(|G|-1), so we have
  |G|> (2/p)(1-ϵ/2)/(1+ϵ) >(2α/p)|H|√(log
    d).
  Now 2α/p ≥
  1/√(log(1/(1-p))) holds by the definition of α, so |G|≥
  |H|√(log_1/(1-p)d). As for the connectivity of G, we have
  κ(G)≥ k=ϵ/2 > ϵ
  |G|/2D_2=ϵ'|G|. We
  may now apply Theorem <ref> to G with ϵ' in place
  of ϵ, to see that G≻ H, provided D(ϵ)>D_1(ϵ').





§ THE DENSE CASE

In this section, our main aim will be to prove
Theorem <ref>. In fact, it will turn out to be useful to prove
a slightly stronger version of the theorem, namely
Theorem <ref>, in which H is a rooted minor, which
is to say we specify, for each v∈ V(H), a vertex of G that must lie
in the class U_v. This will be needed when we come to the sparse case in
the next section.

The essence of the proof is to choose the parts U_v at random
from G. It is very unlikely that the parts so chosen will be connected;
to get round this, we first put aside a few vertices of G and choose the
U_v from the remainder, using the put aside vertices afterwards to
augment the sets U_v into connected subgraphs. In this way, all that we
require of the random sets U_v is that there is an edge in G between
U_v and U_w whenever vw∈ E(H). This procedure nearly works, but it
throws up a few “bad” parts U_v that cannot be used, and even among the
good parts there will be a few edges vw∈ E(H) for which there is no
U_v–U_w edge. In <cit.>, where H=K_t, this was not a big
problem: the initial aim is changed to finding instead a K_(1+β)t
minor, at no real extra cost if β is small, and the few blemishes in
this minor still leave us with a K_t minor. In <cit.>, where
H has average degree at least t^ϵ, a similar solution is found;
a H+K_β t minor is aimed for, which even with up to β t
blemishes still leaves an H minor. The method works in <cit.>
because if β(ϵ) is small then γ(H) and
γ(H+K_β t) are relatively close, as are c(H) and
c(H+K_β t).

This method fails completely for sparse H, because c(H) and
c(H+K_β t) are far from each other, so we need a new approach. We
randomly partition G (after setting aside some vertices) into somewhat
more than |H| parts but without predetermining which part is assigned to
which vertex of H. After discarding the few bad parts we still have |H|
good parts left, each of which has an edge to most of the other good
parts. The good parts are now randomly assigned to the vertices of H; it
turns out that this is enough to ensure that not too many (fewer than
|H|) edges vw∈ E(H) are left with no U_v–U_w edge. For
these few missing edges, we can find U_v–U_w paths at the final stage
when we make all the U_v connected. In this way we obtain the required
H minor.



 §.§ Almost-H-compatible equipartitions



  An equipartition of G is a partition of V(G) into parts
  V_i whose sizes differ by at most one. A
  j-almost-H-compatible equipartition of G is an
  equipartition into parts V_v, v∈ V(H), where there are at most j
  edges vw of H for which there is no edge between V_v and V_w. An
  H-compatible equipartition of G is a 0-almost-H-compatible
  equipartition.


We now give the details of the argument sketched above.  Here,
in <ref>, we find an almost-H-compatible equipartition in a
dense graph, and then in <ref> we show how to connect up the
parts of the equipartition, as well as `adding in' the missing edges.


The result of taking a random equipartition is described by the next
lemma. We remark that, in the proof, the parts are not chosen entirely
randomly, but subject to the constraint that each part gets its fair share
of high and low degree vertices — this helps to control the number of
“bad” parts. The lemma is more or less identical
to <cit.>, and we keep its technical form so that we
can copy it over with very little comment.

       


Let G be a graph of density at least p, let l≥ 2 be an integer,
and let s = ⌊ |G|/l⌋≥ 2. Let ω > 1 and
0<η < p . Then G has an equipartition into at least
s-2s/ωη parts, with at most
2s^2(6ω)^l(1-p/1-η)^(1-η)l(l-1) pairs of parts having
no edge between them.


  The argument is essentially exactly that of <cit.>,
  though the conclusion stated there is very slightly different.  The
  argument involves removing |G|-sl vertices, and then choosing randomly,
  from a certain distribution, an equipartition of the remaining vertices
  into s parts of size l. Some of these parts are of no use (they are
  called “unacceptable” in <cit.> and “bad” above). Amongst the
  other parts, some pairs will be defective in that they fail to have an
  edge between them. At the start of the final paragraph of the proof
  in <cit.>, it is stated that there is a partition with at most
  2s/ωη unacceptable parts and at most
  2s^2(6ω)^l(1-p/1-η)^(1-η)l(l-1) defective pairs
  amongst the other parts. For the conclusion of
  <cit.>, the unacceptable parts and one part from each
  defective pair are thrown away. For the conclusion of the present lemma,
  we keep all the acceptable parts. We then take the vertices from the
  unacceptable parts, together with the |G|-sl vertices initially
  removed, and redistribute them amongst the acceptable parts so as to
  obtain the desired equipartition.



  Let ϵ≤1/2 and let 0<x<1-ϵ. Then
  √(log(x+ϵ)/log x)≤ 1-ϵ.


This is <cit.>, except that there the condition is
0<ϵ≤ x≤ 1-ϵ. However, though the implied condition
ϵ≤1/2 is used in the proof, the condition ϵ≤ x is
not, and the proof works for 0<x.


Here is the main result of this subsection.



Given ϵ >0, there exists D_3(ϵ), such that if H is a
graph of average degree d>D_3, and G is a graph of density at least
p+ϵ, with the properties ϵ < p <1-ϵ and
|G|≥ |H|√(log_1/(1-p)d), then G contains an
|H|d^-ϵ/3-almost-H-compatible equipartition.

 
  We shall apply Lemma <ref> to G, replacing p in
  the lemma by p+ϵ (as we may), and using suitably chosen
  parameters l, k, η, ω so that |H|≤ s(1-2/ωη)
  and 2/ωη≤ 1/10.  Suppose we have done this, obtaining an
  equipartition into k≥ s(1-2/ωη) parts. Note that
  ϵ<1/2, and that we can make l, |H| and s as large as we
  like by making D_3(ϵ) large.  In particular
  2s^2/k2≤ 5. Thus, writing P for the probability that a
  randomly chosen pair of parts has no edge between, we have
  P≤ 5(6ω)^l(1-p-ϵ/1-η)^(1-η)l(l-1). Now
  randomly label |H| of the parts as U_v, v∈ V(H). The expected
  number of edges vw of H without a U_v–U_w edge is
  Pe(H)=P|H|d/2.  We shall choose the parameters so that
  P≤ d^-1-ϵ/3, and therefore there is some labelling with
  fewer than |H|d^-ϵ/3 such edges. Redistributing the vertices
  of the non-labelled parts amongst the |H| labelled parts then gives the
  desired almost-H-compatible equipartition, so proving the theorem.

  All that remains is to choose suitable parameters. To start with, let
  
l=(1-ϵ/4)
    √(log_1/(1-p)d) and s=|G|/l.
  We take ω=20/ϵ^2η, with η still to be
  chosen. Certainly 2/ωη≤ 1/10, as needed, and moreover
  s(1-2/ωη)≥ |H|. 

  We turn now to the bound on P, which is
  P≤ 5(6ω)^l(1-p-ϵ/1-η)^(1-η)l(l-1).
  Choose η small so that η<ϵ/4 and
  (1-2ϵ)^ϵ/2<(1-η)^1-2η. Since p>ϵ this
  implies 
  
    (1-p-ϵ/1-η)^(1-2η)<
      (1-p-ϵ)^1-ϵ(1-2ϵ)^ϵ-2η/(1-η)^(1-2η)
      < (1-p-ϵ)^1-ϵ .

  Make l large enough so that
  (1-2η)l^2<(1-η)l(l-1). Then 
P≤ 5(6ω)^l
  (1-p-ϵ)^(1-ϵ)l^2.
  By Lemma <ref> we have
  log(1-p)/log(1-p-ϵ)≤ (1-ϵ)^2, meaning that
  (1-p-ϵ)^(1-ϵ)^2≤ 1-p, so
  P≤5(6ω)^l(1-p)^l^2/(1-ϵ). Since

  l=(1-ϵ/4)
    √(log_1/(1-p)d) and (1-ϵ/4)^2/(1-ϵ) > 1+ϵ/2, we obtain

  P≤5(6ω)^l d^-1-ϵ/2. Finally, by making d large, we
  have P≤ d^-1-ϵ/3, as desired.




 §.§ The connector and the projector


As mentioned at the start of <ref>, when proving
Theorem <ref> we first put aside a small set for later
use. This set is actually made up of two special sets that we call the connector and the projector. The connector will contain many short
paths between all pairs of vertices, and the projector will allow us to
connect many sets X by connecting only about logX
vertices of the projector.

We borrow a couple of very straightforward lemmas from <cit.>.



Let G be a graph of connectivity κ>0 and let u,v∈ V(G). Then
u and v are joined in G by at least κ^2/4|G| internally
disjoint paths of length at most 2|G|/κ.




Let G be a bipartite graph on vertex classes A,B with the property
every vertex in A has at least γB neighbours in B, where
γ>0. Then there is a set M⊆ B with
|M|≤log_1/(1-γ)A+1 such that every vertex in A
has a neighbour in M, that is, A⊂Γ(M).


The next theorem provides us with a connector and a projector. The form of
the theorem allows us to put aside  not just these two sets but also a third
set R which will form the roots of our rooted H minor.

  Given η>0, there exists
  D_4(η) such that, if G is a graph with |G|≥ D_4 and
  κ(G)≥8η|G|, then for each set R⊂ V(G) with
  |R|≤η |G|, there exist subsets C (the connector) and P (the
  projector) in V(G), disjoint from each other and from R, with the
  following properties:
  
  
  * C,P≤ 2η |G|,
  
  *  each pair of vertices u,v ∉ C is joined by
    at least 2η^2+1/2η|G| internally disjoint
    paths of length at most 1/2η whose internal vertices lie in C,
  
  *  each vertex not in P has at least 2η^2|G| neighbours
    in P, and
  
  *  for every Y⊂ P with |Y|≤η^2|G| and 
    for every X⊂ V(G)-P-C, there is a set M in P-Y with
    X⊂Γ(M) and
    |M|≤log_1/(1-η/2)X+1.
  


  First, we construct C. We put vertices of G-R inside C
  independently at random with probability η. By Markov's Inequality,
  C≤ 2η |G| holds with probability at least 1/2.

  Define δ by κ(G)=δ|G|, so δ≥ 8η.  Let
  u,v∉ C. Applying Lemma <ref> to the graph
  G-(R∖{u,v}), noting that its connectivity is at least
  (δ-η)|G|, we see that u and v are joined by at least
  (δ-η)^2|G|/4≥δ^2|G|/16 vertex-disjoint paths of length
  at most 2/(δ-η)≤ 4/δ, whose internal vertices are not
  in R.  The probability that a given one of these paths has all internal
  vertices inside C is at least η^4/δ. We therefore expect at
  least δ^2η^4/δ|G|/16 vertex disjoint paths of length at
  most 4/δ with all internal vertices inside C. The paths are
  disjoint so the probabilities for different paths are independent of each
  other. Hence by a standard Chernoff bound (see for example
  <cit.>), except with probability at most
  |G|^2exp(-δ^2η^4/δ|G|/128), all pairs of vertices are
  joined by at least δ^2η^4/δ|G|/32 vertex disjoint paths
  of length at most 4/δ whose internal vertices lie inside C. By
  making D_4 large we can ensure this probability is less than 1/2.
  Combining this with the observation in the previous paragraph, we see
  that with positive probability there is a set C satisfying
  C≤ 2η |G| and such that every pair u,v ∉ C is joined
  by at least δ^2η^4/δ|G|/32≥ 2η^2+1/2η|G|
  paths inside C of length at most 4/δ≤ 1/2η. 
  Fix now such a choice of C; then C satisfies properties (1) and (2).
	
  We next construct P. Consider G-C-R. Since G has minimum degree at
  least κ(G)=δ |G|, every vertex has at least
  δ|G|-4η|G|≥δ|G|/2 neighbours inside G-C-R. Place
  vertices in P independently at random with probability η. As
  before, with probability at least 1/2, P≤ 2η|G|.
  Given a vertex not in P, the number of its neighbours in P is
  binomially distributed with mean at least ηδ|G|/2. Again, by a
  Chernoff bound, the probability that any vertex has fewer than
  ηδ|G|/4 neighbours in P is at most
  |G|exp(-ηδ|G|/16), which is less than 1/2 if D_4 is large. 
  Therefore with positive probability there is a set P with |P|≤
  2η|G| such that every vertex not in P has at least
  ηδ|G|/4≥ 2η^2|G| neighbours in P. Make such a choice of
  P: it satisfies properties (1) and (3).

  Finally, consider the bipartite graph with A=X and
  B=P-Y. By choice of P, each vertex of A has at least
  ηδ|G|/4-|Y|≥ηδ|G|/8 neighbours in B, which is at
  least δ|B|/16 by property (1). Lemma <ref>
  then implies there is a set M in P-Y with X⊂Γ(M) and
  |M|≤log_1/(1-δ/16)X+1
  ≤log_1/(1-η/2)X+1. Thus property (4) holds.


The next theorem shows that the connector and projector do the job required
of them in the discussion at the start of <ref>. The theorem
accommodates general partitions of a set; in this paper we shall apply it
only to equipartitions, but the more general result will be useful
elsewhere (see <ref>).



Given η>0 there is a constant D_5(η) with the following
property. Let G be a graph and R⊂ V(G) satisfy the conditions of
Theorem <ref>.  Let C and P be sets given by that
theorem. Suppose further that |G|≥ D_5|R|. Then for any partition
(V_r: r∈ R) of G-C-P-R into |R| parts, together with a set
F⊂{ rs : r,s∈ R} of pairs from R with |F|≤ |R|/η,
there are disjoint sets U_r, r∈ R such that


  * V_r∪{r}⊂ U_r for all r∈ R, 

  * G[U_r] is connected for all r∈ R, and

  *  there is a U_r-U_s edge for every pair rs∈ F.



  Note that the conditions of Theorem <ref> imply
  η≤1/8. Our first aim is to choose, one by one for each r∈ R,
  disjoint sets M_r⊂ P with V_r∪{r}⊂Γ(M_r):
  for later parts of the proof, we shall require that
  ∑_r∈ R|M_r|≤η^(3+1/2η)|G|. To this end, 
  let C_η be a constant, depending on η, such that
  1+log_1/(1-η/2)(x+1)≤ C_ηlog(2x) holds for all x≥ 1.
  The sets M_r will be derived via Theorem <ref> and
  satisfy |M_r|≤log_1/(1-η/2)V_r∪{r}+1; note
  that therefore |M_r|≤ C_ηlog2|V_r|. Thus ∑_r∈ R|M_r|≤
  C_η∑_r∈ Rlog2|V_r| ≤ C_η|R|log (2|G|/|R|) holds
  by the concavity of the log function. Now log(2x)/x→0 as
  x→∞ so D_5 can be chosen so that
  C_η (|R|/|G|)log (2|G|/|R|) ≤η^(3+1/2η), which
  means that
  ∑_r∈ R|M_r|≤η^(3+1/2η)|G|. We now see that our first
  aim can indeed be realised: choose the M_r one by one, each time
  applying property (4) of Theorem <ref> with
  X=V_r∪{r} and Y being the union of those M_r'
  already chosen, noting that  |Y| ≤∑_r∈ R|M_r|≤η^(3+1/2η)|G|≤η^2|G|.

  We now choose disjoint sets P_r⊂ P, r∈ R, such that
  G[P_r∪ M_r] is connected, and therefore so also is
  G[P_r∪ M_r ∪ V_r∪{r}]. To do this, we find |M_r|-1 paths
  joining the vertices of M_r, whose internal vertices are in C, making
  use of property (2) of Theorem <ref>. We choose the
  paths one by one. When we come to join a pair u, v of vertices, some
  of the 2η^2+1/2η|G| paths given by property (3) will be
  unavailable, because they contain a vertex lying in some previously
  chosen path. But at most ∑_r∈ R|M_r|≤η^(3+1/2η)|G|
  paths were previously chosen, so at most
  (1/2η) η^(3+1/2η)|G| < η^2+1/2η|G| u–v paths
  are unavailable. Hence the desired sets P_r can all be found.

  We now take U_r=P_r∪ M_r ∪ V_r∪{r}. This gives
  properties (1) and (2) of the theorem. To obtain property (3), for each
  rs∈ F we find an r–s path Q_rs whose internal vertices lie
  in C. These can be found one by one by an argument similar to that just
  given; the total number of unavailable r–s paths, accounting for the
  sets P_r as in the previous paragraph and for the paths Q_r's'
  already chosen, is at most
  η^2+1/2η|G| + (2/η)(|R|/η) < 2η^2+1/2η|G| if
  D_5 is large, so
  at least one path is available.  Having found Q_rs, add the vertices
  of Q_rs, apart from r, to U_s. In this way we arrive at sets
  satisfying properties (1)–(3).


 Let H and G be graphs, and let R⊂ V(G)  be a set of
  |H| vertices labelled by the vertices of H; say R={ r_v  :
    v∈ V(H)}. We say that G has an H minor rooted at R if there exist non-empty disjoint subsets
  U_v: v∈ V(H) of V(G) with r_v∈ U_v, such that each G[U_v] is
  connected and, whenever vw is an edge in H, there is an edge in G
  between U_v and U_w.


We are finally ready to state and prove the main theorem of this
section. This is a strengthening of Theorem <ref> that
gives a rooted minor, which, as we mentioned earlier, will be useful later
on. Note that Theorem <ref> follows from
Theorem <ref> by picking an arbitrary set R of roots.




Given ϵ >0, there exists D_1(ϵ), such that
if H is a graph of average degree d>D_1, G is a graph of density at
least p+ϵ, with the properties ϵ < p <1-ϵ,
|G|≥ |H|√(log_1/(1-p)d) and κ(G)≥ϵ |G|, and
furthermore R⊂ V(G) is a set of vertices labelled by
V(H), then G has an H minor rooted at R.


  Note that we can assume throughout that both |G| and |G|/|H|=|G|/|R|
  are arbitrarily large, since log(1/(1-p)) is bounded above by the
  constraint on p. We begin by applying
  Theorem <ref> with η = ϵ/20 to obtain
  sets C and P as in the theorem. Consider the graph G'=G-C-P-R. We
  want to apply Theorem <ref> to G', but |G'| might
  not satisfy the stated lower bound. However, we may assume that
  |G'|≥ (1-4η)|G|-|R|≥(1-ϵ/4)|G|, so
  e(G')≥ e(G)-(ϵ/4)|G|(|G|-1). Thus
  e(G')≥ (p+ϵ/2)|G|2, and G' has density at least
  p+ϵ/2. Let p'=p+ϵ/4 and let ϵ'=ϵ/4. By
  Lemma <ref>,
  √(log_1/(1-p')d)≤(1-ϵ/4)√(log_1/(1-p)d). So we
  may apply Theorem <ref> to G' with parameters p'
  and ϵ' to obtain an |H|d^-ϵ/12-almost-H-compatible
  equipartition V_v, v∈ V(H) of G'=G-C-P-R.  Apply
  Theorem <ref> to this equipartition (formally writing
  V_r_v instead of V_v), with F the set of pairs r_vr_w for which
  there is no V_v–V_w edge; note that
  |F|≤ |H|d^-ϵ/12≤|H|<|R|/η if d is large. The
  resulting sets U_r then form an H minor in G rooted at R.




§ THE SPARSE CASE

Our approach in the sparse case broadly mirrors that of <cit.>,
except that we need to construct an H minor rather than a complete minor,
and the graphs G in which we are working have many fewer edges. (Both
these difficulties were sidestepped in <cit.>, where there were
enough edges in the sparse case to find a large complete minor.)  We will
construct a large number (depending on ϵ) of disjoint dense and highly
connected subgraphs of a minor-minimal graph — in all but one of these we
find different subgraphs of H as rooted minors, using
Theorem <ref>, and then we connect these minors together
using the remaining dense subgraph.

To find the dense subgraphs, we use the fact that, in a minor minimal
graph, a typical vertex has a dense neighbourhood. Either we can find a
large number of typical vertices whose neighbourhoods are largely disjoint,
in which case we can carry out the programme just described, or most
vertices have highly overlapping neighbourhoods. The latter case will be
handled by the next lemma. This lemma is much the same as
<cit.>, but we need to reprove it because the degrees in
our graphs are much lower and the constants involved are different.


  
  Given ϵ, C>0, there exists D_6(ϵ, C) such that, if
  d>D_6, the following holds.  Let H be a graph of average degree d,
  and let n≥ϵ |H|√(log d). Let G be a bipartite graph
  with vertex classes A, B such that B≤ Cn,
  A≥ D_6n, and every vertex of A has at least n neighbours
  in B. Then G≻ H.


  Begin by choosing a number 0<q<1/5 such that
  ϵ√(-log(2q))≥ 1. This implies that
  n≥|H|√(log_1/2qd). Then take D_6 so that
  D_6q≥ C^2.

  Proceed by contracting, one by one, each vertex a∈ A to a vertex
  b∈ B of minimal degree in G^*[N(a)], where G^* is the graph we
  have at the moment we contract ab. We imagine that a disappears in
  this process but b remains, and after we have done this for all
  a∈ A we are left with a graph on vertex set B. Note that, if
  G^*[N(a)] has minimum degree p_a(|N(a)|-1), and q_a=1-p_a, then we
  add at least q_a(n-1) edges to B. Suppose that q_a≥ q for every
  a∈ A. Then we have added at least |A|q(n-1) edges. But we can add
  at most |B|2, so 2|A|q(n-1)≤ |B|(|B|-1). However, this
  inequality fails by our choice of D_6.

  It follows that, for some a∈ A, q_a≤ q holds. Let
  G'=G^*[N(a)]. Then G' has minimum degree at least p_a(|G'|-1),
  and since q_a≤ 1/5 we have p_a≥ 4/5 so κ(G')≥ |G'|/2.
  Moreover |G'|≥ n≥ |H|√(log_1/2qd).  Now G' has density
  at least (1-2q)+q, so we can apply Theorem <ref> to G'
  with parameters ϵ=q and p=1-2q (increasing D_6 if necessary
  so that D_6≥ D_1(q)), to obtain G≻ G'≻ H.


We can now prove Theorem <ref>. We restate first it, for convenience.

*


   Let ℓ=8/ϵ and L=ℓ2.
   We start by finding, one by one, disjoint sets S_0,…,S_L such that
   
    S_i≤ 6    δ(G[S_i])> 5/6-1 ,    0≤ i≤ L .

   Suppose we have already found sets S_0,...,S_k-1, where k≤ L.
   Let B = ⋃_0≤ i < kS_i. Then B≤ 6L. Let
   A be the set of vertices in V(G)-B having degree at
   most 6.  Then
   3G-B-A≤ e(G)≤G.  In particular,
   G-B-A≤G/2. Assuming, as we may, that D_2≥ 36L,
   then |B|≤ |G|/6, so |A|≥ |G|/3.  Let n=/6 and let
   C=36L, so n≥ (ϵ/6)|H|√(log d) and |B|≤ Cn.  We
   may also assume that D_2≥ D_6(ϵ/6,C)/2, where D_6 is the
   constant in Lemma <ref>, and so |A|>D_6n. Then, by
   that lemma, either G≻ H, in which case the theorem is proved and
   we are done, or some vertex a∈ A has fewer than n=/6
   neighbours in B. In this case put S_k=Γ(a)∖ B.  Then
   |S_k|≤ 6, since a∈ A. Moreover, because each edge
   incident with a lies in more than -1 triangles, we have
   δ(G[Γ(a)])≥ m-1 and so δ(G[S_i])>
   5/6-1. We thus find all our sets S_0,…,S_L.

   Next, inside each S_i we find a subset T_i with
   κ(G[T_i])≥/40 and 
δ(G[T_i])≥3/4.
   If κ(G[S_i])≥/40, just put T_i=S_i. If not, remove a
   cutset of size at most /40 from G[S_i] and let S_i' be the
   set of vertices of a smallest component. Then |S_i'|≤|S_i|/2≤
   3 and
   δ(G[S_i'])≥ 5/6-1-/40. If
   κ(G[S_i'])≥/40, put T_i=S_i'. Otherwise,
   repeat the procedure on G[S_i']. After j repetitions of the procedure
   we have a subgraph with at most 6/2^j vertices and minimum
   degree at least 5/6-1-j/40. This is impossible for
   j=4, so we reach the desired T_i in at most 3 steps.

   Now let V_1,...,V_ℓ be an arbitrary equipartition of H, and let
   H^{i,j} = H[V_i∪ V_j]. Each subgraph H^{i,j} has at most
   2|H|/ℓ+2≤ϵ|H|/4+2 vertices, and average degree at most
   ℓ d (if D_2 is large). Notice that H is the (not edge-disjoint)
   union of the L = ℓ2 subgraphs H^{i,j}.  We shall find the
   H^{i,j} as minors inside the G[T_i], and with this in mind we
   relabel T_1,…,T_L as T^{i,j}:1≤ i<j≤ℓ; we shall
   find H^{i,j} in G[T^{i,j}].

   We now describe how the H minor will be formed, leaving the details of
   the construction to later. The minor will be rooted at a set of roots
   R⊂ T_0, which we pick now and label as
   R={r_v:v∈ V(H)}. The H^{i,j} minors also need to be rooted,
   so pick now a set of roots
   R^{i,j}={r^{i,j}_v: v∈ V_i∪ V_j}⊂ T^{i,j}. For
   each pair {i,j} and for each v∈ V_i∪ V_j, we find an
   r_v–r^{i,j}_v path P^{i,j}_v, such that all the paths
   P^{i,j}_v are internally disjoint from each other and from all the
   H^{i',j'} minors. Then the paths P^{i,j}_v with the minors
   H^{i,j} together give an H minor, because every edge of H lies
   in one of the H^{i,j}, and by contracting the
   paths P^{i,j}_v we identify, for each v∈ V(H), all the root
   vertices r^{i,j}_v that are labelled by v.

   Here are the constructional details. In practice, to avoid the paths
   P^{i,j}_v intersecting the minors H^{i',j'}, we construct the
   paths first, then remove them and find the minors in the remaining
   graph. Each vertex v lies in ℓ-1 sets V_i∪ V_j, so
   R^*=⋃_{i,j} R^{i,j} satisfies
   |R^*|=(ℓ-1)|H|. Note that, if D_2 is large, then
   κ(G-R)≥ D_2|H|-|R^*|≥|R^*| and
   |T_0-R|≥ 3m/4-|H|≥|R^*|. Thus by Menger's theorem we can find |R^*|
   vertex disjoint paths in G-R joining the set T_0-R to the
   set R^*. Let the path which ends at r^{i,j}_v be
   Q^{i,j}_v, and let its first vertex be x^{i,j}_v∈ T_0. 
   These paths Q^{i,j}_v might, as they stand, use a lot of vertices
   from the sets T^{i',j'}, so we now modify them so as to avoid this.

   Recall that |T_0|≤ 6 and κ(G[T_0])≥/40.
   Applying Lemma <ref> to G[T_0], we see that each pair
   of vertices is joined by at least /38400 paths of length at
   most 480 — we call these “short” paths. Exactly the same remark
   applies to each G[T^{i,j}]. We now modify the paths
   Q^{i,j}_v, one by one, in the following way. For each set
   T^{i',j'} that the path Q^{i,j}_v enters, let x and y be
   the first and last vertices of Q^{i,j}_v in T^{i',j'}, and
   replace the section of Q^{i,j}_v between x and y by a short
   path inside G[T^{i',j'}]. At the moment we don't require these
   short paths to be disjoint for different i,j,v, but after doing this
   the paths Q^{i,j}_v have the property that they enter each
   T^{i',j'} only once, and use at most 480 vertices of
   T^{i',j'}. After this is done, note that the first and last
   vertices of the Q^{i,j}_v in the T^{i',j'} are all still
   distinct, since they can never lie on the internal vertices of our new
   short paths - they are always vertices of the original path.  Let E be
   the set of first and last vertices of all the new short paths in all the
   T^{i,j}.

   We now go through each T^{i,j} and replace the short paths used by
   ones that are disjoint from each other and from E. We do this by
   replacing the short paths one at a time, each time choosing a new short
   path disjoint from previously chosen new short paths and disjoint
   from all the endpoints E. We can do this because
   the number of vertices we need to avoid is at most
   480|R^*| +|E|≤ 482|R^*| < /40000. The modified paths
   Q^{i,j}_v are now once again vertex 
   disjoint, each using at most 480 vertices from each
   T^{i',j'}. Finally, we extend the paths Q^{i,j}_v to the
   paths P^{i,j}_v that we want, by finding |R^*| internally
   disjoint short paths inside G[T_0] that join r_v to x^{i,j}_v,
   for all v∈ V(H) and all appropriate {i,j}.

   What remains is to find the H^{i,j} minors. Fix some
   pair {i,j}. Let X be the set of vertices on the paths
   P^{i',j'}_v' that lie inside T^{i,j}, other than the roots
   R^{i,j}. By the choice of these paths, we have
   |X|≤ 480|R^*|< 480ℓ|H|. Let G'=G[T^{i,j}-X]. Then it is
   enough to find an H^{i,j} minor in G' that is rooted at
   R^{i,j}. Recall that H^{i,j} has at most ϵ|H|/4+2
   vertices, and average degree at most ℓ d. Since H itself has
   average degree d, it is possible to add edges to H^{i,j}, if
   necessary, so that the resultant graph H' has average degree d'
   where ϵ d/5≤ d'≤ℓ d (if D_2 is large). It is now
   enough to find H' as a minor of G', rooted at R^{i,j}.

   Recalling the properties of the T_i, we see that |G'|≤ 6m,
   δ(G')≥ 3/4-|X| and κ(G')≥/40-|X|.
   If D_2 is large, this means δ(G')> 2/3≥ |G'|/9 and
   κ(G')≥/50≥ |G'|/300. Let ϵ'=1/300.  Then
   we can pick p≥ 1/10 such that ϵ'<p<1-ϵ' and G' has
   density at least p+ϵ'. Moreover, δ(G')≥ 2/3
   implies we can choose p+ϵ' ≥ 2/3|G'|, and since
   ϵ'≤ m/50|G'| we have p≥ 3/5|G'|. Recalling that
   |H'|≤ϵ|H|/4+2, and that ϵ d/5≤ d'≤ℓ d, we
   obtain, if D_2 is large,
   
    |G'| ≥3/5p≥3ϵ/5p
       |H|√(log d)≥11/5p|H'|√(log d)≥2/p|H'|√(log d') .

   By the definition of α>1/4, this implies
   
    |G'| ≥ 4√(log(1/(1-p)))/p/2
       |H'|√(log_1/(1-p) d') > |H'|√(log_1/(1-p) d') .

   Because d'>ϵ d/5 we can ensure that d'>D_1(ϵ') by
   making D_2 large. We now have all the conditions we need to conclude,
   from Theorem <ref>, that H' is a minor of G' rooted
   at R^{i,j}, as required.


	


§ FURTHER EXTENSIONS


As mentioned in the introduction, Myers and Thomason <cit.>
defined a graph parameter γ(H) and proved that
c(H)=(αγ(H)+o(1)) t√(log t) for graphs H with t
vertices and at least t^1+τ edges. The parameter γ(H) is
found by considering non-negative vertex weightings w:V(H)→𝐑^+, and is given by

    γ(H) = min_w 1 t ∑_u∈ Hw(u)
    ∑_uv∈ E(H) t^-w(u)w(v) ≤ t .

The constant weighting w(v)=√(τ) satisfies the constraints, so
γ(H)≤√(τ) always, but in general the relative sizes of the vertex
weights are, essentially, the relative sizes of the sets |U_v| that are most
likely to give an H minor in a random graph (this is where the parameter
comes from). For most H, and for regular H when τ>0, the optimal
sizes of the |U_v| are the same, so γ(H)≈√(τ) and
c(H)=(α+o(1)) |H|√(log d).  But there are natural examples
where taking equal sized sets |U_v| is not optimal. For example, the
complete bipartite graph K_β t, (1-β)t satisfies
γ(K_β t, (1-β)t)≈ 2√(β(1-β)).

When H is sparse, examples such as the hypercube cited in the
introduction suggest that γ(H) is not enough on its own to determine
c(H). Nevertheless we think that Theorem <ref> can be extended to
incorporate some features of γ(H). For example, if β is fixed,
the proof of Theorem <ref> could probably be modified to show that,
if d is large and H is a bipartite graph with average degree d,
having vertex class sizes β|H| and (1-β)|H|, then
c(H)≤ (2√(β(1-β))α+o(1))|H|√(log d).  Moreover,
the argument of <cit.> indicates that equality holds for almost all
such H. Similar remarks could be made regarding multipartite graphs.
With this in mind, we have, as mentioned earlier, stated
Theorem <ref> in a form more general than what is needed
in this paper, but other than that we do not pursue any details of these
ideas here.


	
plain



