1 Introduction
Graph partitioning problems have a long history in discrete mathematics and theoretical computer science. One classical example is the well-known max-cut problem: given a graph G, find the maximum bipartite subgraph of G. From the algorithmic perspective, it is non-deterministic polynomial-time (NP)-hard to determine the size of a max-cut [Reference Karp, Miller, Thatcher and Bohlinger17]. In combinatorics, it is interesting to estimate the extremal values of a max-cut in terms of its number of edges.
For a graph G, let
$f(G)$
denote the max-cut of G, that is, the maximum number of edges in a bipartite subgraph of G. For a positive integer m, let
$f(m)$
denote the minimum value of
$f(G)$
, as G ranges over all graphs with m edges. It is easy to see that
$f(m)\geq m/2$
, for instance by considering a probabilistic argument or a suitable greedy algorithm of a graph with m edges. This elementary result can be improved by providing a more accurate estimate for the error term after the main term
$m/2$
.
Answering a question of Erdős [Reference Erdős9], Edwards [Reference Edwards7, Reference Edwards and Fiedler8] proved that for every m,
$$ \begin{align*} f(m)\geq\frac{m}{2}+\frac{1}{4}\bigg(\sqrt{2m+\frac{1}{4}}-\frac{1}{2}\bigg), \end{align*} $$
and noticed that this is tight for complete graphs on an odd number of vertices. For a certain range of m, Alon [Reference Alon1] gave an additive improvement of
$\Omega (m^{1/4})$
.
The situation is more complicated if we consider H-free graphs, that is, graphs containing no copy of a fixed given graph H. Let
$f(m,H)$
denote the minimum possible cardinality of
$f(G)$
, as G ranges over all H-free graphs on m edges. It was shown in [Reference Alon, Bollobás, Krivelevich and Sudakov2] that for every fixed graph H, there exist constants
$\varepsilon =\varepsilon (H)>0$
and
$c=c(H)>0$
such that
$f(m,H) \ge m/2+cm^{1/2+\varepsilon }$
for all m. The problem of estimating the error term more precisely is not easy and the following conjecture is still wide open.
Conjecture 1.1 [Reference Alon, Bollobás, Krivelevich and Sudakov2].
For any fixed graph H, there exists a positive constant
$\varepsilon =\varepsilon (H)$
such that
$$ \begin{align*}f(m,H) \ge \dfrac{m}{2}+\Omega(m^{3/4+\varepsilon}).\end{align*} $$
In fact, we do not even know whether there exists a constant
$\alpha> 1/2$
such that for all H, we have
$f(m,H) \ge m/2+ \Omega (m^\alpha )$
. An even more ambitious problem, first explicitly posed in [Reference Alon, Bollobás, Krivelevich and Sudakov2], is to determine the asymptotic growth rate of
$f(m,H)$
for every fixed graph H. The case
$H=C_3$
was initially studied by Erdős and Lovász (see [Reference Erdős, Bondy, Murty and Tutte10]). After a series of papers by various researchers, Alon [Reference Alon1] proved that
$f(m,C_3)=m/2+\Theta (m^{4/5})$
for all m.
Motivated by a conjecture of Erdős and Lovász (see [Reference Erdős, Bondy, Murty and Tutte10]), Alon et al. [Reference Alon, Bollobás, Krivelevich and Sudakov2] studied the max-cut of graphs without short cycles. They showed that every m-edge graph not containing any cycle of length at most r has max-cut at least
$m/2+\Omega (m^{{{(r+1)}}/{{(r+2)}}})$
. For even integers
$r=2k$
, this was improved in [Reference Alon, Krivelevich and Sudakov4] to
$$ \begin{align} f(m,C_{2k})\ge \frac{m}{2}+\Omega(m^{{{(2k+1)}}/{{(2k+2)}}}). \end{align} $$
This bound is tight for
$k\in \{2,3,5\}$
. The theta graph
$\Theta _{k,t}$
denotes the graph consisting of t paths of length k with the same endpoints but no inner intersection. Obviously,
$\Theta _{k,2}=C_{2k}$
. Recently, Lin [Reference Lin19] improved (1.1) by showing that
$f(m,\Theta _{k,t})\geq m/2+\Omega (m^{{{(2k+1)}}/{{(2k+2)}}})$
. For more problems and results on
$f(m,H)$
, see [Reference Glock, Janzer and Sudakov15, Reference Hou and Wu16, Reference Lin, Zeng and Chen20, Reference Zeng and Hou23].
To generalise the degenerate extremal graph result of theta graphs (and thus of even cycles), Faudree and Simonovits [Reference Faudree and Simonovits13] introduced the following definition.
Definition 1.2 [Reference Faudree and Simonovits13].
Let T be an arbitrary bipartite graph with a fixed 2-colouring C using red and blue. Take a vertex w not belonging to T and join it to each red vertex of T by pairwise vertex-independent paths of length
$k-1$
. The resulting graph will be denoted by
$L_{k}=L_{k}(T, C)$
.
Obviously, if
$T=K_{1, t}$
and C colours the t-vertex class of
$K_{1, t}$
by red, then
$L_{k}(K_{1, t}, C)=\Theta _{k,t}$
. In this paper, we study
$f(m,H)$
and extend some known results for some general bipartite graphs H. Our first result shows that the lower bound in (1.1) holds for any
$L_{k}(T, C)$
-free graph when T is a tree.
Theorem 1.3. If T is a tree, then there is a constant
$c=c(k,T)>0$
such that
$$ \begin{align*} f(m, L_{k}(T, C))\ge \frac{m}{2} + c{m^{{{(2k+1)}}/{{(2k+2)}}}}. \end{align*} $$
We claim here that in the construction of
$L_{k}(T, C)$
, if w is also connected to each blue vertex of T, then Theorem 1.3 is not true. Let H be a graph obtained by connecting a single vertex w to all vertices of a fixed nontrivial forest, Alon et al. [Reference Alon, Krivelevich and Sudakov4] proved that
$$ \begin{align*}f(m,H)=\frac{m}{2}+\Theta(m^{4/5}).\end{align*} $$
To split a vertex v is to replace v by two adjacent vertices, say
$v'$
and
$v"$
, and to replace each edge incident to v by an edge incident to either
$v'$
or
$v"$
(but not both), the other end of the edge remaining unchanged. Our next result concerns the bipartite graph obtained by splitting w of the above H. To be more specific, let L be a tree (when regarded as a bipartite graph) with partite sets X and Y, and let
$K_{t,t}\ast L$
denote the graph obtained by completely joining one partite set of
$K_{t,t}$
to X and the other to Y.
Theorem 1.4. Let L be a tree. For all m, there is a positive constant
$c(L)$
such that
$$ \begin{align*}f(m, K_{1,1}\ast L)\geq\frac{m}{2}+c(L)m^{5/6}.\end{align*} $$
Setting
$L=K_{1,s-1}$
in Theorem 1.4,
$f(m, K_{1,1}\ast L)=f(m,K_{2,s})\geq m/2+\Omega (m^{5/6})$
. This was improved by Zeng and Hou [Reference Zeng and Hou22], who proved the same bound when H is a bipartite graph with maximum degree 2 on one side. We give a further improvement.
Theorem 1.5. If H is bipartite and has a
$\mathrm {2}$
-colouring where in the first colour class all but two vertices are of degree at most
$\mathrm {2}$
, then there is a positive constant
$c(H)$
such that
$$ \begin{align*}f(m,H)\geq\frac{m}{2}+c(H)m^{5/6}.\end{align*} $$
For
$s\geq t\ge 2$
, Alon et al. [Reference Alon, Krivelevich and Sudakov4] considered
$K_{t,s}$
-free graphs and proposed the following conjecture.
Conjecture 1.6 [Reference Alon, Krivelevich and Sudakov4].
For all
$s\geq t\geq 2$
and all m, there exists a positive constant
$c(s)$
such that
$$ \begin{align*}f(m,K_{t,s})\geq\frac{m}{2}+c(s)m^{ {(3t-1)}/{(4t-2)}}.\end{align*} $$
If true, this is tight at least for all
$s\geq (t-1)!+1$
, as shown by the projective norm graphs [Reference Alon, Rónyai and Szabó5]. In [Reference Alon, Krivelevich and Sudakov4], the authors confirmed Conjecture 1.6 for the cases
$t\in \{2,3\}$
. In this paper, we consider the first unsettled case
$f(m,K_{4,s})$
.
Theorem 1.7. For each
$s\geq 4$
and all m, there is a positive constant
$c(s)$
such that
$$ \begin{align*}f(m,K_{4,s})\geq\frac{m}{2}+c(s)m^{5/7}.\end{align*} $$
All graphs considered here are finite, undirected, and have no loops and no parallel edges, unless otherwise indicated. In the course of the paper, we will make no serious attempt to optimise the absolute constants involved. For the sake of simplicity of presentation, we will occasionally drop floor and ceiling signs whenever they are not crucial.
2 Lemmas
In this section, we give several lemmas which drive the proof of our theorems. The proof of our theorems will be given in Section 3.
A graph G is d-degenerate if each subgraph of G contains a vertex of degree at most d. We need the following well-known fact.
Lemma 2.1 (See [Reference Alon1, Reference Alon, Bollobás, Krivelevich and Sudakov2, Reference Alon, Krivelevich and Sudakov4]).
Let G be a d-degenerate graph on n vertices. Then there is a labelling
$v_1,v_2,\ldots ,v_n$
of the vertices of G so that, for each i with
$1\leq i\leq n$
, the vertex
$v_i$
has at most d neighbours
$v_j$
with
$j<i$
.
In the study of the max-cut of triangle-free graphs, Shearer [Reference Shearer21] proved an important bound in terms of the degree sequence
$d_1,d_2,\ldots ,d_n$
of a graph:
$$ \begin{align} f(m,C_3)\geq\dfrac{m}{2}+\Omega\bigg(\sum_{i=1}^n\sqrt{d_i}\bigg). \end{align} $$
The bound (2.1) implies immediately that any triangle-free d-degenerate graph with m edges has max-cut
$m/2+\Omega (m/\sqrt {d})$
. Alon et al. [Reference Alon, Krivelevich and Sudakov4] further extended Shearer’s argument to graphs with few triangles and proved the following result.
Lemma 2.2 [Reference Alon, Krivelevich and Sudakov4].
There exists an absolute positive constant
$\varepsilon $
such that for every positive constant C, there is a
$ \delta =\delta (C)>0 $
with the following property. Let
$G=(V,E)$
be a graph with n vertices (with positive degrees), m edges and degree sequence
$d_1, d_2,\ldots , d_n$
. Suppose, further, that the induced subgraph on any set of
$d\geq C$
vertices, all of which have a common neighbour, contains at most
$\varepsilon d^{3/2}$
edges. Then,
$$ \begin{align*}f(G)\geq\dfrac{m}{2}+\delta\sum_{i=1}^n\sqrt{d_i}.\end{align*} $$
Recently, Carlson et al. [Reference Carlson, Kolla, Li, Mani, Sudakov and Trevisan6] showed that the local assumption can be relaxed to a global condition, namely, any d-degenerate graph with m edges and
$O(m\sqrt {d})$
triangles has max-cut
$m/2+\Omega (m/\sqrt {d})$
. They believed that a stronger statement is true and proposed the following conjecture.
Conjecture 2.3 [Reference Carlson, Kolla, Li, Mani, Sudakov and Trevisan6].
For any graph H, there exists a constant
$c = c(H)> 0$
such that, for all H-free d-degenerate graphs with
$m \ge 1$
edges,
$$ \begin{align*}f(G)\ge \bigg(\frac 12+\frac c{\sqrt{d}}\bigg)m.\end{align*} $$
It was noted in [Reference Carlson, Kolla, Li, Mani, Sudakov and Trevisan6] that Conjecture 2.3 implies Conjecture 1.1, thus making Conjecture 2.3 a plausible stepping stone to Conjecture 1.1.
Next, we employ the following lemmas, which establish the lower bounds of
$f(G)$
for graphs G in terms of different parameters.
Lemma 2.4 [Reference Erdős, Gyárfás and Kohayakawa11].
Let G be a graph with n vertices, m edges and positive minimum degree. Then,
$$ \begin{align*}f(G)\geq \frac{m}{2}+\frac{n}{6}.\end{align*} $$
Lemma 2.5 [Reference Alon1].
Let
$G=(V,E)$
be a graph with m edges. Suppose
$U\subset V$
and let
$G'$
be the induced subgraph of G on U. If
$G'$
has
$m'$
edges, then
$$ \begin{align*}f(G)\geq f(G')+\frac{m-m'}{2}.\end{align*} $$
Finally, we use the following result proved in [Reference Zeng and Hou22] (see also [Reference Alon, Krivelevich and Sudakov4]), which gives the existence of a randomised induced subgraph in a graph with relatively large minimum degree and sparse neighbourhood.
Lemma 2.6 [Reference Zeng and Hou22].
Let
$G=(V,E)$
be a graph with n vertices, m edges and minimum degree at least
$m^{\theta }$
for some fixed real
$\theta \in (0,1)$
. Suppose that m is sufficiently large and the induced subgraph on the neighbourhood of any vertex
$v\in V$
of degree
$d_v$
contains fewer than
$sd_v^{3/2}$
edges for some positive constant s. Then, for every constant
$\eta \in (0,1)$
, there exists an induced subgraph
$G'=(V',E')$
of G with the following properties:
-
(a)
$G'$
contains at least
$\eta ^2m/2$
edges; -
(b) every vertex v of degree
$d_v$
in G that lies in
$V'$
has degree at least
$\eta d_v/2$
in
$G'$
; -
(c) every neighbourhood of the vertex v in
$V'$
contains at most
$2\eta ^2sd_v^{3/2}$
edges in
$G'$
.
3 Proofs of the main results
3.1 Excluding
$L_{k}(T, C)$
In this subsection, we give a proof of Theorem 1.3. We need the upper bound, proved by Faudree and Simonovits [Reference Faudree and Simonovits13], on the maximum number of edges in an
$L_{k}(T, C)$
-free graph. Here,
$\mbox {ex}(n,H)$
denotes the Turán number.
Lemma 3.1 [Reference Faudree and Simonovits13].
If T is a tree (or a forest) with a given
$\mathrm {2}$
-colouring C by red and blue, then for
$L_{k}=L_{k}(T, C)$
,
$$ \begin{align*}\operatorname{ex}(n, L_{k})=O(n^{1+{1}/{k}}).\end{align*} $$
Proof of Theorem 1.3.
Let
$G=(V,E)$
be an
$L_{k}(T, C)$
-free graph with n vertices and m edges. Define
$D=\mu m^{1/(k+1)}$
, where
$\mu =\mu (k)>0$
will be chosen later.
Claim 3.2. G is D-degenerate.
Assume, to the contrary, G contains a subgraph
$G'$
with minimum degree more than D. Then the number of vertices of
$G'$
satisfies
$$ \begin{align*}|G'|:=N< \frac{2m}{D}\le \frac{2D^{k}}{\mu^{k+1}}.\end{align*} $$
Thus, the number of edges of
$G'$
is
$$ \begin{align} e(G') \ge \frac{1}{2}DN \ge {\bigg( {\frac{{\mu N}}{2}} \bigg)^{{{(k + 1)}}/{k}}}. \end{align} $$
Since
$G'$
is an
$L_{k}(T, C)$
-free graph, by Lemma 3.1, there exists a constant
$c'>0$
such that
$e(G')\le c'N^{{{(k + 1)}}/{k}}$
. This contradicts (3.1) by choosing
$\mu>2(c')^{{{k}}/{(k+1)}}$
, and thus completes the proof of Claim 3.2.
By Claim 3.2 and Lemma 2.1, there exists a labelling
$v_1,v_2,\ldots ,v_{n}$
of the n vertices of G such that
$d_i^+\le D$
for each i, where
$d_i^+$
denotes the number of neighbours
$v_j$
of
$v_i$
with
$j<i$
in G. Let
$d_i$
denote the degree of
$v_i$
in G for each
$1\leq i\leq n$
. Then,
$$ \begin{align*}\sum_{i=1}^{n}\sqrt{d_i}\geq\sum_{i=1}^{n}\sqrt{d_i^+}\ge \frac{\sum_{i=1}^{n}d_i^+}{\sqrt D}=\frac{m}{\sqrt D}\ge \frac{m^{{(2k+1)}/{(2k+2)}}}{\sqrt \mu}.\end{align*} $$
Since G is
$L_{k}(T, C)$
-free, the neighbourhood of any vertex of G cannot contain a tree isomorphic to
$L=L_{k}-\{w\}$
. As is well known, there is a constant
$\ell =\ell (k,T)$
such that the induced subgraph of G on the neighbourhood of any vertex with degree d can span at most
$\ell d$
edges, which is smaller than
$\varepsilon d^{3/2}$
for all
$d>(\ell /\varepsilon )^2$
. Therefore, by Lemma 2.2 with
$C=(\ell /\varepsilon )^2$
, there is a constant
$\delta =\delta (C)$
such that
$$ \begin{align*}f(m, L_{k}(T, C))\ge \frac{m}{2}+\delta\sum_{i=1}^n\sqrt{d_i}\geq \frac{m}{2}+\delta \frac {m^{{(2k+1)}/{(2k+2)}}}{\sqrt \mu}.\end{align*} $$
This completes the proof of Theorem 1.3 by choosing
$c=\delta /\sqrt {\mu }$
.
3.2 Excluding universal bipartite graphs
In this subsection, we prove Theorems 1.4 and 1.5 using the idea in Section 3.1 and some additional ideas. First, we derive Theorem 1.5 by proving a more general result (see Theorem 3.5). The following graph, introduced by Füredi [Reference Füredi14], was shown to be closely related to the lowest three levels of the Boolean lattice.
Definition 3.3 [Reference Füredi14].
Let k, r and t be given positive integers. The graph
$U(k, r, t)$
is obtained from the k vertices
$x_1, \ldots , x_k$
by joining t distinct vertices
$y^{i}_{i_1,\ldots ,i_r}$
to each of the r-element subsets of {
$x_1, \ldots , x_k$
}. Then,
$U^{+r}(k, r, t)$
is obtained from
$U(k, r, t)$
by joining a new set of r vertices
$\{w_1,w_2,\ldots ,w_r\}$
to all
$x_h, h=1, \ldots , k$
. (See Figure 1.)
Figure 1 The graph
$U^{+2}(3, 2, 1)$
.
We use the following result to bound the maximum number of edges in a
$U^{+r}(k,r,t)$
-free graph.
Lemma 3.4 [Reference Alon, Krivelevich and Sudakov3].
For any
$U^{+r}(k, r, t)$
defined in Definition 3.3,
$$ \begin{align*}\operatorname{ex}(n,U^{+r}(k, r, t))=O(n^{2-1/r}).\end{align*} $$
Note that
$U(k, r, t)$
contains every bipartite graph with maximum degree r on one side. It turns out that any H considered in Theorem 1.5 can be embedded into an appropriate
$U^{+r}(k,r,t)$
. Hence, Theorem 1.5 is an immediate corollary of the following result.
Theorem 3.5. For any given positive integers
$k,t$
and for all m, there exists a positive constant
$c(k,t)$
such that
$$ \begin{align*}f(m,U^{+2}(k, 2, t))\geq\frac{m}{2}+c(k,t)m^{5/6}.\end{align*} $$
Proof. Let G be a
$U^{+2}(k, 2, t)$
-free graph with m edges and n vertices. We may assume that m is sufficiently large. If
$n\ge m^{5/6}/{2}$
, the desired result follows immediately from Lemma 2.4. Thus, we assume that
$n<m^{5/6}/{2}$
and aim to employ Lemma 2.2 to get the desired result. We first show that there exists an induced subgraph
$G'$
of G satisfying the assumptions of that lemma.
Claim 3.6. There exists an induced subgraph
$G'$
of G with at least
$\eta ^2m/4$
edges such that the induced subgraph on all the neighbours of any vertex v of degree
$d'$
in
$G'$
contains at most
$\varepsilon (d')^{3/2}$
edges in
$G'$
, where
$\eta \in (0,1)$
is a fixed constant and
$\varepsilon $
is the constant from Lemma 2.2.
As long as there is a vertex of degree smaller than
$m^{1/6}$
in G, omit it. This process terminates after deleting fewer than
$m^{1/6}n<m/{2}$
edges, and thus we obtain an induced subgraph
$G^*$
of G with at least
$m/{2}$
edges and minimum degree at least
$m^{1/6}$
. Clearly,
$G^*$
is also
$U^{+2}(k, 2, t)$
-free. It follows that the induced subgraph on the neighbourhood of any vertex v of degree
$d^*$
in
$G^*$
contains no copy of
$U^{+2}(k, 2, t)$
. By Lemma 3.4, there exists a constant
$c_1>1$
such that this induced subgraph spans at most
$c_1d^{*3/2}$
edges.
Now, we apply Lemma 2.6 to
$G^*$
with
$\eta \le \varepsilon ^2/(32c_1^2)$
, and hence we obtain an induced subgraph
$G'$
of
$G^*$
(and hence of G) satisfying the following properties.
-
(a) The number of edges of
$G'$
is
$$ \begin{align*}e(G')\ge \dfrac{\eta^2}{2}\cdot \dfrac{m}{2}=\dfrac{\eta^2m}{4}.\end{align*} $$
-
(b) Every vertex v of degree
$d^*$
in
$G^*$
that lies in
$V'$
has degree at least
$\eta d^*/{2}$
in
$G'$
. -
(c) The induced subgraph on all the neighbours of any vertex v of degree
$d'$
(/
$d^*$
) in
$G'$
(/
$G^*$
) contains at most edges.
$$ \begin{align*}2\eta^2c_1{d^*}^{3/2}\le \varepsilon(d')^{3/2}\end{align*} $$
This completes the proof of Claim 3.6.
Claim 3.7.
$G'$
is D-degenerate, where
$D=\mu m^{1/3}$
and
$\mu $
is a fixed constant.
Assume, to the contrary,
$G'$
contains a subgraph
$G"$
with minimum degree more than D. Note that the number of vertices of
$G"$
is
$N<2m/D\leq 2D^2/\mu ^3$
. Thus, the number of edges of
$G"$
is
$$ \begin{align*}e(G")\geq\frac{ND}{2}\geq \bigg(\frac{\mu N}{2}\bigg)^{3/2}.\end{align*} $$
Since
$G"$
is
$U^{+2}(k, 2, t)$
-free, by Lemma 3.4, there exists a constant
$c"$
such that
$e(G')\le c"N^{3/2}$
, which contradicts the above inequality by choosing
$\mu>2(c")^{2/3}$
. This completes the proof of Claim 3.7.
By Claim 3.6, the assumptions of Lemma 2.2 hold for
$G'$
. By Lemma 2.1 and Claim 3.7, there is a labelling
$v_1,v_2,\ldots ,v_{n'}$
of the
$n'$
vertices of
$G'$
such that
$d_i^+\leq D$
for every i, where
$d_i^+$
denotes the number of neighbours
$v_j$
of
$v_i$
with
$j<i$
in
$G'$
. Let
$d_i$
denote the total degree of
$v_i$
in
$G'$
for each
$1\leq i\leq n'$
. Note that
$\sum _{i=1}^{n'}d_i^+=e(G')$
. By Lemma 2.2, there is a constant
$\delta $
such that
$$ \begin{align*} f(G')&\geq \frac{e(G')}{2}+\delta\sum_{i=1}^{n'}\sqrt{d_i}\geq \frac{e(G')}{2}+\delta\sum_{i=1}^{n'}\sqrt{d_i^+} \end{align*} $$
$$ \begin{align*} \kern25pt~&\geq \frac{e(G')}{2}+\frac{\delta\sum_{i=1}^{n'}d_i^+}{\sqrt D}\geq \frac{e(G')}{2}+\frac{\delta\eta^2}{4\sqrt{\mu}}m^{5/6}. \end{align*} $$
This, together with Lemma 2.5, gives
$$ \begin{align*}f(G)\geq f(G')+\frac{m-e(G')}{2}\geq\frac{m}{2}+\frac{\delta\eta^2}{4\sqrt{\mu}}m^{5/6}.\end{align*} $$
This completes the proof of Theorem 3.5.
The proof of Theorem 1.4 is similar to the previous ones and we give only a sketch here. The following result is given by Erdős and Simonovits [Reference Erdős, Simonovits, Erdős, Rényi and Sós12].
Lemma 3.8 [Reference Erdős, Simonovits, Erdős, Rényi and Sós12].
For any tree L,
$\operatorname {ex}(n, K_{t,t}\ast L)=O(n^{2- 1/{(t+1)}})$
.
Proof Sketch proof of Theorem 1.4.
Let
$H=K_{1,1}\ast L$
and let
$G=(V,E)$
be an H-free graph with m edges and n vertices. Define
$D=\mu m^{1/3}$
, where
$\mu $
is a fixed constant.
Claim 3.9. Let
$\eta \in (0,1)$
be a fixed constant and
$\varepsilon $
be a constant defined as in Lemma 2.2. Then there is an induced subgraph
$G'$
of G with the following properties:
-
(a)
$G'$
is a D-degenerate graph with at least
$\eta ^2m/4$
edges; -
(b) the number of edges in every neighbourhood of a vertex v of degree
$d_v$
in
$G'$
is at most
$\varepsilon d_{v}^{3/2}$
.
By Lemmas 2.1, 2.2 and Claim 3.9,
$f(G')$
exceeds half the number of edges of
$G'$
by at least
$\Omega (m^{5/6})$
and the desired result follows from Lemma 2.5.
3.3 Excluding complete bipartite graphs
In this subsection, we study the function
$f(m,K_{4,s})$
, where
$s\ge 4$
is a fixed integer. We need several known results. The first one is a well-known upper bound, proved by Kővári et al. [Reference Kővári, Sós and Turán18], on the maximum number of edges in a
$K_{t,s}$
-free graph.
Lemma 3.10 [Reference Kővári, Sós and Turán18].
Let
$K_{t,s}$
be the complete bipartite graph with
$t+s$
vertices and
$ts$
edges. For any integers
$s\ge t\ge 2$
, we have
$$ \begin{align*}\operatorname{ex}(n,K_{t,s})\le \tfrac{1}{2}(s-1)^{1/t}n^{2-1/t}+\tfrac{1}{2}(t-1)n.\end{align*} $$
We also need the following result of Carlson et al. [Reference Carlson, Kolla, Li, Mani, Sudakov and Trevisan6].
Lemma 3.11 [Reference Carlson, Kolla, Li, Mani, Sudakov and Trevisan6].
For all
$s>0$
, there exists
$c=c(s)$
such that any d-degenerate
$K_{4,s}$
-free graph G always satisfies
$f(G)\ge {m}/{2}+cd^{-2/3}m$
.
Proof of Theorem 1.7.
Let
$G=(V,E)$
be a
$K_{4,s}$
-free graph with m edges and n vertices, where
$s\ge 4$
.
Define
$D=bm^{3/7}$
, where
$b=b(s)>1$
will be chosen later. If G is D-degenerate, the desired result follows immediately from Lemma 3.11.
Suppose that G is not D-degenerate, that is, G contains a subgraph
$G'$
with minimum degree more than D. Note that the number of vertices of
$G'$
is
$N<2m/D\leq 2D^{4/3}/b^{7/3}$
. Thus, the number of edges of
$G'$
is
$$ \begin{align*}e(G')\geq\frac{ND}{2}\geq \bigg(\frac{b N}{2}\bigg)^{7/4}.\end{align*} $$
Since
$G'$
is
$K_{4,s}$
-free, by Lemma 3.10, there exists a constant
$c'$
such that
$e(G')\le c'N^{7/4}$
, which contradicts the above inequality by choosing
$b>2(c')^{4/7}$
. This completes the proof of Theorem 1.7.
Acknowledgement
The authors would like to thank the referees for their careful reading and helpful comments.
