Bipartite-ness under smooth conditions

Abstract

Given a family $\mathcal{F}$ of bipartite graphs, the {\it Zarankiewicz number} $z(m,n,\mathcal{F})$ is the maximum number of edges in an $m$ by $n$ bipartite graph $G$ that does not contain any member of $\mathcal{F}$ as a subgraph (such $G$ is called {\it $\mathcal{F}$-free}). For $1\le \beta <\alpha <2$, a family $\mathcal{F}$ of bipartite graphs is $(\alpha ,\beta )$-{\it smooth} if for some $\rho >0$ and every $m\le n$, $z(m,n,\mathcal{F})=\rho m{n}^{\alpha -1}+O(n^{\beta })$. Motivated by their work on a conjecture of Erdős and Simonovits on compactness and a classic result of Andrásfai, Erdős and Sós, in \cite{AKSV} Allen, Keevash, Sudakov and Verstraëte proved that for any $(\alpha ,\beta )$-smooth family $\mathcal{F}$, there exists $k_0$ such that for all odd $k\ge k_0$ and sufficiently large $n$, any $n$-vertex $\mathcal{F}\cup \{C_k\}$-free graph with minimum degree at least $\rho (\frac{2n}{5}+o(n){)}^{\alpha -1}$ is bipartite. In this paper, we strengthen their result by showing that for every real $\delta >0$, there exists $k_0$ such that for all odd $k\ge k_0$ and sufficiently large $n$, any $n$-vertex $\mathcal{F}\cup \{C_k\}$-free graph with minimum degree at least $\delta n^{\alpha -1}$ is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families $\mathcal{F}$ consisting of the single graph $K_{s,t}$ when $t\gg s$. We also prove an analogous result for $C_{2\ell }$-free graphs for every $\ell \ge 2$, which complements a result of Keevash, Sudakov and Verstraëte in \cite{KSV}.

16 pages, to appear in Combin. Probab. Comput

References in corpus (1)

• Graphs with few paths of prescribed length between any two vertices