Given a graph G, let f(G) denote the maximum number of edges in a bipartite subgraph of G. Given a fixed graph H and a positive integer m, let f(m, H) denote the minimum possible cardinality of f(G), as G ranges over all graphs on m edges that contain no copy of H. In this paper we prove that f(m,θk,s)⩾12m+Ω(m(2k+1)/(2k+2))\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$f\left( {m,{\theta _{k,s}}} \right) \geqslant {1 \over 2}m + \Omega \left( {{m^{\left( {2k + 1} \right)/\left( {2k + 2} \right)}}} \right)$$\end{document}, which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write Kk′ and Kt,s′ for the subdivisions of Kk and Kt,s. We show that f(m,Kk′)⩾12m+Ω(m(5k−8)/(6k−10))\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$f\left( {m,K_k^\prime } \right) \geqslant {1 \over 2}m + \Omega \left( {{m^{\left( {5k - 8} \right)/\left( {6k - 10} \right)}}} \right)$$\end{document} and f(m,Kt,s′)⩾12m+Ω(m(5t−1)/(6t−2))\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$f\left( {m,K_{t,s}^\prime } \right) \geqslant {1 \over 2}m + \Omega \left( {{m^{\left( {5t - 1} \right)/\left( {6t - 2} \right)}}} \right)$$\end{document}, improving a result of Q. Zeng, J. Hou. We also give lower bounds on wheel-free graphs. All of these contribute to a conjecture of N. Alon, B. Bollobás, M. Krivelevich, B. Sudakov (2003).
