A graph Γ is said to be a minor of a graph G if for every vertex v of Γ we can choose a connected subgraph G u of G, such that subgraphs G u are vertex disjoint and G contains an edge between G v and G v ′ whenever v and v ′ make an edge in Γ. The notion of graph minors is one of the most fundamental concepts of modern graph theory and has found many applications in topology, geometry, theoretical computer science and optimisation; for more details, see the excellent surveys [17,20]. Many of these applications have their roots in the celebrated Robertson-Seymour theory of graph minors, developed over more than two decades and culminating in the proof of Wagner's conjecture [26]. One of several equivalent ways of stating this conjecture is that every family of graphs, closed under taking minors can be characterised by a finite family of excluded minors. A forerunner to this result is Kuratowski's theorem [14], one of the most classical results of graph theory dating back to 1930. In a reformulation due to Wagner [31] it postulates that a graph is planar if and only if neither K 5 nor K 3,3 are its minors.
Another cornerstone of graph theory is the famous 4-colour theorem dating back to 1852 which was finally settled with the aid of computers in 1976 by [2]. It states that every planar graph G has chromatic number 1 at most four. In light of Kuratowski's theorem, Wagner [30] has shown that in fact the 4-colour theorem is equivalent to showing that every graph without K 5 as a minor has χ(G) ≤ 4. In 1943 Hadwiger proposed a natural generalisation, namely that every graph with χ(G) ≥ r has K r as a minor. Hadwiger's conjecture is known for r ≤ 5 (for the case of r = 5 see [27]) but despite receiving considerable attention over the years it is still widely open for r ≥ 6, see [28] for the current state of affairs.
In this paper we study the question of how large a clique minor can one guarantee to find in a graph G which belongs to a certain restricted family of graphs. A prime example of this type of problems is Hadwiger's conjecture itself. Another natural example asks what happens if instead of restricting the chromatic number we assume a lower bound on the average degree. Note that χ(G) ≥ r implies that G has a subgraph of minimum degree at least r -1. So the restriction in this problem is weaker than in Hadwiger's conjecture and we are interested in how far can this condition take us. This question, first considered by Mader [18] in 1968, was answered in the 80's independently by Kostochka [12] and Thomason [29] who show that a graph of average degree r has a clique minor of order Θ(r/ √ log r). This is best possible up to a constant factor as can be seen by considering a random graph with appropriate edge density (whose largest clique minor was analysed by Bollobás, Catlin and Erdős in [6]).
This unfortunately means that this approach is not strong enough to prove Hadwiger's conjecture for all graphs. For almost four decades, bounding the chromatic number through average degree and using the Kostochka-Thomason theorem gave the best known lower bound on the clique minor given the chromatic number. Very recently, Norin, Postle, and Song [21] got beyond this barrier and in a series of works [24,25] Postle obtained the currently best result, by showing that every graph of chromatic number r has a clique minor of size Ω(r/(log log r) 6 ). This still falls short of proving Hadwiger's conjecture for all graphs.
However, if we impose some additional restrictions on the graph it turns out we can do much better. One of the most natural restrictions, frequently studied in combinatorics, is to require our graph G to be H-free for some other, small graph H. This problem was first considered by Kühn and Osthus [16] who showed that given s ≤ t every K s,t -free graph with average degree r has a clique minor of order Ω r 1+2/(s-1) / log 3 r . The polylog factor in this result was subsequently improved by Krivelevich and Sudakov [15] who obtained in a certain sense the best possible bound. They also obtain tight results, for the case of C 2k -free graphs. These results show Hadwiger's conjecture holds in a stronger form for any H-free graph, provided H is bipartite. On the other hand, if H is not bipartite then taking G to be a random bipartite graph shows that the bound of Kostochka [12] and Thomason [29] can not be improved.
A natural next question is whether we can do better if we assume a somewhat stronger condition than a bound on the average degree or the chromatic number. A natural candidate is an upper bound on α(G), the size of a largest independent set in G. Indeed, the chromatic number of a graph G is at least n/α(G). An old conjecture, which is implied by Hadwiger's conjecture, (see [28]) states that if α(G) ≤ r then G has a clique minor of order n/r. Duchet and Meyniel [7] showed in 1982 that this conjecture holds within a factor of 2, which was subsequently improved by [3,4,9,10,11,19,22,23,32], most notably Fox [9] gave the first improvement of the multiplicative constant 2. Building upon the ideas of [9], Balogh and Kostochka [3] obtain the best known bound to date.
In light of these results, Norin asked whether in this case assuming additionally that G is triangle-free allows for a better bound. This question was answered in the affirmative by Dvořák and Yepremyan [8] who show that for n/r large enough, a triangle-free n-vertex graph with α(G) ≤ r has a clique minor of order (n/r) 1+ 1 26 . They naturally ask if the same holds if instead of triangle-free graphs we consider K s -free graphs. We show that this is indeed the case.
Theorem 1. Let s ≥ 3 be an integer. Every K s -free n-vertex graph G with α(G) ≤ r has a clique minor of order at least (n/r) 1+ 1 10(s-2) , provided n/r is large enough.
For the case of s = 3 our result has a simpler proof and gives a better constant in the exponent compared to that in [8]. As an additional illustration we use our strategy to obtain a short proof of a result of Kühn and Osthus [16] about finding clique minors in K s,t -free graphs. The above-mentioned two examples put quite different restrictions on the structure of the underlying graph, nevertheless our approach performs well in both cases. This leads us to believe that our strategy, or minor modifications of it, could provide a useful tool for finding clique minors in graphs under other structural restrictions as well. The strategy is simple enough to be worth describing in the Introduction.
Given a graph G our strategy for finding minors of large average degree goes as follows:
1. We independently colour each vertex of G red with probability p and blue otherwise.
2. Each blue vertex chooses independently one of its red neighbours (if one exists) uniformly at random. This decomposes the graph into stars, either centred at a red vertex with leaves being the blue vertices, which have chosen the central vertex as their red neighbour or being isolated blue vertices which had no red neighbours to choose from. We obtain our random minor M(G, p) by contracting each star into a single vertex and deleting the isolated blue vertices.
We note that similar strategies were employed by both Kühn and Osthus [16], and Dvořák and Yepremyan [8]. Our strategy above streamlines their approaches for finding dense minors. This helps us to develop a new way of analysing the outcome, allowing us to answer the above question of Dvořák and Yepremyan [8] as well as to obtain simpler proofs of the results of both [16] and [8].
Notation: For a graph G, we denote by V (G) its vertex set and by E(G) its edge set and by δ(G), d(G) and ∆(G) its minimum, average and maximum degree. For v ∈ V (G) let d G (v) be the degree of v in G (we often write just d(v) when the underlying graph is clear). If V (G) is red-blue coloured, we denote by d r (v) the number of red neighbours of v. For a subset S ⊆ V (G), let N (S) be the set of vertices adjacent to at least one vertex in S. For us an ℓ-path is a path of length ℓ, which consists of ℓ edges and ℓ + 1 vertices. For a path v 1 v 2 . . . v n we say v 1 and v n are its endvertices and v 2 , . . . , v n-1 are its internal vertices.
We begin the section by stating some well-known tools which we are going to use. Lemma 2.1 (Chernoff bound, for a proof see [1]). Let X 1 , . . . , X d be independent random variables, taking value 1 with probability p and 0 otherwise and let X = d i=1 X i . Then P(X > 2pd) ≤ e -pd/3 and P(X < 1 2 pd) ≤ e -pd/8 . Lemma 2.2. Every graph G has a spanning bipartite subgraph in which every vertex has degree at least half as big as it had in G.
Theorem 2.3 (Kövári-Sós-Turán [13]). Let s ≤ t be positive integers. Every bipartite graph with parts of size n and at least (t -1)n 2-1/s + sn edges has K s,t as a subgraph.
We now introduce some notation and give an overview of how we analyse M(G, p).
If G has n vertices, then M ∼ M(G, p) will almost surely have roughly np vertices. In terms of edges, any edge xy of G which got both its endpoints coloured blue will become an edge in M between the red vertices that x and y picked (assuming x and y each have red neighbours). This means that, provided we pick p carefully, M will have roughly as many edges as G. The main issue is that M might not be a simple graph. In other words, between some vertices of M there could be many parallel edges and the main part of the analysis of the above process is to control the number of such parallel edges.
Given M ∼ M(G, p), we say that a 3-path vxyu in G is activated if both vertices v and u got coloured red, both vertices x and y got coloured blue and x chose v and y chose u as their red neighbours. Note that a path vxyu being activated means there is an edge between v and u in M . With this in mind our general strategy for the analysis of M(G, p) will be to try to find a collection P of many 3-paths in our graph, such that not too many of these paths have the same endvertices. The chance that a fixed 3-path activates will be rather small, but the chance that two such paths simultaneously activate is even smaller. This means that with the right choice of parameters we still expect to see many activated paths from P but only very few between the same pairs of vertices, which lets us conclude there are many edges in M but few parallel ones. The key part of the approach is to choose P correctly, which will depend on the assumptions we make on our graph G. The technical part of the approach is mostly contained in the following two lemmas. The first one gives a lower bound on the probability that a single 3-path activates while the second gives an upper bound on the chance that several paths with same endvertices activate simultaneously.
Lemma 2.4. Let G be a graph with ∆(G) ≤ d. The chance that a path vxyu activates in M(G, p) is at least 1 2 7 d 2 given 4 d ≤ p ≤ 1 2 . Proof. Let us first consider what happens in the colouring stage of our procedure. We say that a colouring is well-behaved (w.r.t. vxyu) if v, u got coloured red, x, y got coloured blue and both d r (x), d r (y) ≤ 2pd+2. The probability that the right colours got assigned to v, x, y, u is p 2 (1p) 2 and given this the probability that d r (x) > 2p(d -2) + 2 is by Chernoff bound (Lemma 2.1) at most e -p(d-2)/3 ≤ e -pd/4 (note that d ≥ 4 p ≥ 8), since x has at least d -2 neighbours which are not yet coloured or are coloured blue. So the probability that a colouring is well-behaved is at least
Given that we have obtained a well-behaved colouring in the first stage, the probability that vxyu activates is at least
So putting things together
Lemma 2.5. Let G be a graph, d ′ ≤ δ(G) and P be a non-empty collection of 3-paths between vertices v and u of G. If the set of internal vertices of all paths in P has size m and 2 7 m log m < pd ′ then the chance that all paths in P simultaneously activate in M(G, p) is at most 2p 2 /(d ′ p/4) m .
Proof. Let us denote the paths in P by vx i y i u. Let X denote the set of x i 's and Y the set of y i 's. The condition of the lemma tells us that |X ∪ Y | = m. Notice that all paths in vx i y i u simultaneously activate only if v, u get coloured red, each vertex in X ∪ Y gets coloured blue, all vertices in X choose v as their red neighbour and all vertices in Y choose u as their red neighbour. In particular, unless X ∩ Y = ∅ the probability of simultaneous activation is 0. So we may assume X ∩ Y = ∅.
We say that a colouring is feasible if v, u get coloured red and all vertices in X ∪ Y get coloured blue. We say it is well-behaved if in addition all vertices in X ∪ Y have at least (d ′m)p/2 red neighbours. The probability that a colouring is feasible is 16 , since v has at least d ′m neighbours for which we still don't know the colour or we know are red. So the probability that a colouring is not well-behaved given that it is feasible is by a union bound at most
Given a well-behaved colouring the probability that each vertex in X ∪ Y chooses the right red neighbour is at most 4
The chance that all paths in P activate given that the colouring is feasible is at most probability that all paths in P activate given that the colouring is well-behaved plus the probability that the colouring is not well-behaved given it is feasible. By the above bounds, this probability is at most
Finally, this implies that the chance that P activates is at most
2.1 Minors in K s,t -free graphs
In this subsection we illustrate our approach by giving a simpler proof of a result of Kühn and Osthus [16] on dense minors in K s,t -free graphs G.
A graph G is said to be almost regular if ∆(G) ≤ 2δ(G).
Theorem 2.6. For 2 ≤ s ≤ t there is a constant c = c(s, t) > 0 such that every K s,t -free, almost regular graph G with average degree d has a minor of average degree at least cd 1+ 2 s-1 .
Proof. We choose c = c(s, t) = 1 2 56 st 2 . If cd 2/(s-1) ≤ 1 then G itself provides us with the desired minor. So we may assume that d 2/(s-1) ≥ c -1 = 2 56 st 2 . While we will work with the above explicit value of c, for the sake of clarity a reader might assume throughout the argument that d is sufficiently large compared to s and t. We have
Let us first observe a few easy counts, all but the first of which follow due to the fact G ′ is K s,t -free.
1. The number of 3-paths in G ′ is at most 2nd 3 , where n = |G ′ |.
This follows since the number of edges in G ′ is at most nd/2 and for any choice of an edge as a middle edge of a 3-path we have at most 4d 2 choices for its endvertices.
2. The number of cycles of length 6 is at most 4 3 tnd 5-1/(s-1) . Note that as each path of length 3, of which there are at most 2nd 3 , completes into a 6-cycle in at most t(2d) 2-1/(s-1) many ways (and we counted each cycle 6 times). This follows since given a 3-path from v to u each such cycle corresponds to an edge between neighbourhoods of v and u both of which have size at most 2d. The subgraph induced by these neighbourhoods is bipartite and K s-1,t -free since any K s-1,t together with v or u would constitute a copy of K s,t in G. The claimed bound now follows by Kövári-Sós-Turán theorem (Theorem 2.3).
3. The number of copies of K 2,s is at most ntd s . This time we count, for every vertex v the number of stars K 1,s with centre in the second neighbourhood N 2 and all leaves in the first neighbourhood N 1 of v. Let k = |N 2 | and d 1 , . . . , d k denote the number of neighbours of vertices in N 2 within N 1 . The number of our stars is equal to
s ≤ t 2d s ≤ 2td s as otherwise we get a K s,t in G. Taking the sum over all vertices and noticing we count each K 2,s twice we get the claimed bound.
Let us consider M ∼ M(G ′ , p) with p = 2 12 √ td
. Let X denote the expected number of activated 3-paths in M . Since G ′ has at least nd/4 edges and each contributes a distinct activated 3-path, provided its endpoints are blue and have a red neighbour, we deduce
We say a 6-cycle in G ′ activates if it consists of two edge-disjoint activated 3-paths. Let Y count the activated 6-cycles. The chance for two edge-disjoint 3-paths with endvertices v, u to simultaneously activate is at most 2p 2 /(dp/16) 4 = 2 17 p 2 d 4 , by Lemma 2.5 (with m = 4 and d ′ = d/4), which applies since 2 12 ≤ pd.
Each cycle has three possible pairs of such paths so the chance that a 6-cycle activates is at most 3 • 2 17 p 2 d 4 . In particular, EY ≤ 2 19 tnd 1-1/(s-1) /p 2 .
Given a star K 1,s that appears between neighbourhoods of vertices v, u ∈ G ′ , we say it is activated for v and u if all 3-paths between v and u through an edge of the star activated. Let Z count the number of triples consisting of such a star and vertices v, u such that the star was activated for v, u. Each such triple corresponds to a K 2,s with a vertex appended to one of its left vertices. In particular, there are at most 4ntd s+1 plausible triples each of which activates with probability at most 2p 2 /(dp/16) s+1 = 2 4s+5 p 1-s d -s-1 , by Lemma 2.5 (with m = s + 1 and d ′ = d/4). Here we require 2 9 (s + 1) log(s + 1) ≤ pd in order to be able to apply the lemma, which holds since pd ≥ 2 12 √ d and d is large enough compared to s. In particular we get
For every activated 6-cycle we delete a middle edge of an activated 3-path on the cycle, in total deleting at most Y edges. For every activated star we delete one of its edges, in total at most Z edges get deleted. So we are left with at least X -Y -Z edges in M so we know that the expected number of remaining edges is at least
where the inequality is equivalent to d ≥ 2 4s+12 tp 1-s which after plugging in our choice of p is equivalent to d ≥ t 3-s 2 48-16s which holds by our choice of c.
Claim. After this process, between any two vertices v, u ∈ M there are at most s -1 parallel edges.
Proof. To see why this is true consider the bipartite subgraph with left part consisting of blue neighbours of v which choose v as their red neighbour and the right part similarly consists of blue neighbours of u which picked u as their red neighbour. We let the edge set consist of edges of G ′ which were a middle edge of an activated 3-path from v to u. There are no two independent edges in this graph as otherwise we would have an activated 6-cycle in which we did not delete an edge. This means that this graph is a star. If the star had size s or more we would get an activated star for which we have not deleted an edge. So this graph is a star with at most s -1 edges. This means that, after deleting all but one parallel edge between each pair of vertices, we are left with a simple graph with the expected number of edges at least nd 16s . Since we want to show this minor has large average degree, what remains to be done is to control the number of vertices in M . By the Chernoff bound (Lemma 2.1), M has more than 2pn vertices with probability at most e -np/3 and each such outcome can contribute at most n 2 edges to our expectation. So we can find an outcome with at most 2pn vertices and at least nd 16sn 2 e -np/3 edges. This gives us a minor of average degree at least
where in the first inequality we used npe -np/3 ≤ 1 since np ≥ dp ≥ 12.
The above theorem holds also without the almost regularity condition as shown by [15]. The approach presented above with some additional ideas can be used to obtain an alternative, slightly simpler proof of this result. However, since this is a known result and the purpose of including the above argument was mainly for illustration, we chose not to include the details.
3 K s -minor-free case
In this section, we prove our main result, Theorem 1. We state a slightly stronger version below that is more convenient to work with.
Theorem 3.1. Let s ≥ 3 be an integer, ε < 1 10(s-2) and d be large enough. Every K s -free graph G without K d as a minor has α(G) ≥ n d 1-ε .
To see why this implies Theorem 1 choose d = (n/α(G)) 2) . Theorem 3.1 implies that unless G has a K d as a minor we must have d ≥ (n/α(G))
, and completes the argument. Note in particular that one may take the power of n/α(G) in Theorem 1 to be anything smaller than 1 1-ε so smaller than In this setting we will need to take a slightly different approach when analysing M(G, p). The reason is that when working with K s -free graphs, we lack a good way of bounding the number of 3-paths between an arbitrary pair of vertices, which we previously obtained using the fact our graph was K s,t -free. In the present setting we will use the fact that α(G) is bounded to show that independent sets must expand well. Additionally, being K s -free allows us to show that we can cover at least a half of any collection of vertices using few independent sets. With these two facts, we fix a vertex, consider a carefully selected collection of 3-paths starting at this vertex, and then repeat a similar argument as in the previous section to show that we expect to see many non-parallel edges incident to this vertex in M . The following standard Ramsey lemma quantifies the second fact mentioned above. We prove it for completeness. Lemma 3.2. Let s ≥ 2. It is possible to cover half of the vertices of any n-vertex K s -free graph with at most 4n 1-1 (s-1) independent sets.
Proof. We will show that every K s -free graph with m vertices contains an independent set of size at least m 1 s-1 /2. It follows that, as long as we have at least n/2 vertices left, we can find an independent set of size at least n 1/(s-1) /4 and remove it from the graph. Once we stop we removed at most 4n
independent sets which cover at least half of the graph, as desired.
We prove the above claim by induction on s. For s = 2 the graph being K 2 -free means there are no edges so there is an independent set of size m as desired. Assume now that s ≥ 3 and that the lemma holds for s -1. If there is a vertex which has degree at least m s-2 s-1 then, since we know its neighbourhood is K s-1 -free, we are done by induction. On the other hand, if all vertices have degree less than m s-2 s-1 , then by Turán's theorem (see [1]) we know that there is an independent set of size
We will also make use of the result of Kostochka [12] and Thomason [29] mentioned in the introduction, which lets one pass from dense minors to clique minors. Theorem 3.3. Every graph with average degree at least (3 + o(1))t √ log t has K t as a minor.
We say that a graph G is d-independent set expanding if for any independent set S in G we have |N (S)| ≥ (d 1-ε -1)|S|. We now prove our main result with a restriction on the maximum degree and assuming that independent sets of our graph expand. Both these assumptions will be easy to remove later. Proof. Note first that since independent sets expand we have δ(G)
Permissible edges: At most one edge towards each S w,j is permissible
Illustration of the result of the cleaning procedure for S i , with a 3-path in P i drawn red. Every vertex in N i has only one edge remaining towards S i , so the remaining edges between S i and N i span stars. We mark at most one edge from each vertex u adjacent to S w,j as permissible for S w,j .
Fix a vertex v. Since G is K s -free we know that N (v) must be K s-1 -free. By Lemma 3.2 this means there exist disjoint independent sets of vertices S 1 , . . . , S t ⊆ N (v) such that |S 1 | + . . .
. For every vertex in N i we delete all but 1 edge towards S i , leaving us with at least |N i | edges between S i and N i which split into stars with centres in S i . In particular, this means that the remaining neighbourhoods of vertices in S i partition N i . For each vertex w ∈ S i we apply Lemma 3.2 to find a collection of at most t w ≤ 4d(w) 1-1/(s-2) disjoint independent sets S w,1 , . . . , S w,tw ⊆ N (w) ∩ N i which cover at least half of N (w) ∩ N i , where we again used the fact that N (w) is K s-1 -free. For every vertex in N w,j := N (S w,j ) \ ({v} ∪ N (v)) we mark one of its edges towards S w,j as permissible for S w,j . See Figure 1 for an illustration. Note that despite what the figure might indicate we do allow N w,j 's (so "third level" vertices) to intersect with some vertices among S w,j 's (so "second level" vertices) however we require both sets to be disjoint from v and N (v).
We now build a collection of 3-paths P i as follows. Every path in P i starts with v then proceeds to a w ∈ S i then to a vertex in S w,j for some j along one of the remaining edges between S i and N i and finally follows an S w,j -permissible edge. Let us first show some properties of P i that we will use. Claim 1. Middle edges of paths in P i span stars. Proof. This is immediate since we removed all but one edge of each vertex in N i towards S i . Claim 2. For any w ∈ S i and u ∈ V (G) \ ({v} ∪ N (v)) there are at most 4d 1-1 s-2 paths in P i passing through w and ending with u.
Proof. This claim follows since the last edge of any such path in P i must be S w,j -permissible for some j and any vertex u sends at most one permissible edge towards each S w,j . Therefore, there can be at most
Proof. This follows since any S w,j -permissible edge gives rise to a distinct 3-path in our construction. Since we mark precisely one such edge for each vertex in N w,j we get
where in the first inequality we used the fact S w,j is independent so by the expansion property
In the second inequality we used the fact that j∈[tw] |S w,j | ≥ |N (w) ∩ N i |/2 and ∪ w∈S i N (w) ⊇ N i to bound the first term and t w ≤ 4d 1-1/(s-2) to bound the second. In the third inequality we used |N i | ≥ |S i |d ′ -(|N (v)| + 1) which holds by the expansion property since S i is independent. In the last inequality we used ε < 1 2(s-2) and d (so also d ′ ) large enough. Let P := i P i . Applying the above claim for each i we obtain that for large enough d:
Let us fix another vertex u and look at the collection P vu of paths in P ending in u. Let X be the set of vertices following v (so in N (v)) on these paths and Y the sets of vertices preceding u on these paths. Since we excluded N (v) from our N i 's we have X ∩ Y = ∅. Consider the bipartite subgraph B with bipartition given by X and Y and edges coming from middle edges of paths in P vu .
Claim 4. ∆(B) ≤ 4d 1-1/(s-2) .
Proof. For any w in X, we know by Claim 2 that there are at most 4d 1-1/(s-2) paths in P uv so w can have at most this many neighbours in B. For any vertex y ∈ Y , Claim 1 implies y has at most one edge towards any S i ; in particular, it has degree at most t ≤ 4d 1-1/(s-2) in B. 2) and M ∼ M(G, p).
Claim 5. The probability that some path in P vu activates for M is at least |Pvu| 2 9 d 2 .
Proof. Let a := |P vu |, so by Claim 4 and the fact that parts of B have size at most d, we get |E(B)| = a ≤ 4d 2-1/(s-2) . We trivially have at most a 2 pairs of independent edges in B. On the other hand, the number of pairs of edges sharing a vertex is at most a∆(B) ≤ 4ad 1-1/(s-2) , since the first edge we can choose in a ways at which point we have 2∆(B) choices for the second and we count every pair twice.
Let us denote by A e the event that edge e in B activated path veu. By the inclusion-exclusion principle,
where in the second inequality to bound P(A e ) we used Lemma 2.4 while to bound P(A e ∩ A f ) we used Lemma 2.5 with m = 4 if e ∩ f = ∅ and with m = 3 if |e ∩ f | = 1; the conditions of the lemmas are easily seen to hold for our choice of p when d is large enough. In the last inequality we used a p 2 d ′4 ≤ 4d 2-1/(s-2)
for large enough d. Using Claim 5 and the lower bound on the total number of paths in P given in (1) we obtain that the expected number of distinct neighbours of v in M is at least u |Pvu|
As v was a fixed and arbitrary vertex of G in the above argument, we conclude that the expected number of non-parallel edges in M is at least n2 -15 d 1-3ε .
By the Chernoff bound (Lemma 2.1), M has more than 2pn vertices with probability at most e -np/3 , and each such outcome can contribute at most n 2 edges to our expectation. So we can find an outcome with at most 2pn vertices and at least n2 -15 d 1-3ε -n 2 e -np/3 edges, so of average degree at least n2 -14 d 1-3ε /(2pn)- Let us first remove the requirement that independent sets expand.
We proved that every K s -free graph G on n vertices has a clique minor of order polynomially larger than n/α(G), which would be implied by Hadwiger's conjecture. In particular, we can take any power smaller than 1 + 1 10(s-2)-1 . Examples based on random graphs used to bound the Ramsey number R(s, k) for s fixed and k large (see [5] and references therein) are K s -free and have no clique minor of order (n/α(G)) 1+ 1 s-1 +o(1) , showing that our result is best possible up to a constant factor in front of the 1 s-2
term. In terms of the constant factor, being more careful with our bounds one can easily improve the 1/10 factor to 1/8 and with more work even a bit further. It would be interesting to determine the best possible exponent of n/α(G) in our result.