Journal ArticleBipartite-ness under smooth conditionsJiang, Tao; Longbrake, Sean; Ma, Jie<title>Abstract</title> <p>Given a family<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline1.png' mime-subtype='png'/><tex-math>$\mathcal{F}$</tex-math></alternatives></inline-formula>of bipartite graphs, the<italic>Zarankiewicz number</italic><inline-formula><alternatives><inline-graphic href='S0963548323000019_inline2.png' mime-subtype='png'/><tex-math>$z(m,n,\mathcal{F})$</tex-math></alternatives></inline-formula>is the maximum number of edges in an<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline3.png' mime-subtype='png'/><tex-math>$m$</tex-math></alternatives></inline-formula>by<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline4.png' mime-subtype='png'/><tex-math>$n$</tex-math></alternatives></inline-formula>bipartite graph<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline5.png' mime-subtype='png'/><tex-math>$G$</tex-math></alternatives></inline-formula>that does not contain any member of<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline6.png' mime-subtype='png'/><tex-math>$\mathcal{F}$</tex-math></alternatives></inline-formula>as a subgraph (such<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline7.png' mime-subtype='png'/><tex-math>$G$</tex-math></alternatives></inline-formula>is called<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline8.png' mime-subtype='png'/><tex-math>$\mathcal{F}$</tex-math></alternatives></inline-formula><italic>-free</italic>). For<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline9.png' mime-subtype='png'/><tex-math>$1\leq \beta \lt \alpha \lt 2$</tex-math></alternatives></inline-formula>, a family<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline10.png' mime-subtype='png'/><tex-math>$\mathcal{F}$</tex-math></alternatives></inline-formula>of bipartite graphs is<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline11.png' mime-subtype='png'/><tex-math>$(\alpha,\beta )$</tex-math></alternatives></inline-formula>-<italic>smooth</italic>if for some<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline12.png' mime-subtype='png'/><tex-math>$\rho \gt 0$</tex-math></alternatives></inline-formula>and every<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline13.png' mime-subtype='png'/><tex-math>$m\leq n$</tex-math></alternatives></inline-formula>,<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline14.png' mime-subtype='png'/><tex-math>$z(m,n,\mathcal{F})=\rho m n^{\alpha -1}+O(n^\beta )$</tex-math></alternatives></inline-formula>. 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, Allen, Keevash, Sudakov and Verstraëte proved that for any<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline15.png' mime-subtype='png'/><tex-math>$(\alpha,\beta )$</tex-math></alternatives></inline-formula>-smooth family<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline16.png' mime-subtype='png'/><tex-math>$\mathcal{F}$</tex-math></alternatives></inline-formula>, there exists<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline17.png' mime-subtype='png'/><tex-math>$k_0$</tex-math></alternatives></inline-formula>such that for all odd<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline18.png' mime-subtype='png'/><tex-math>$k\geq k_0$</tex-math></alternatives></inline-formula>and sufficiently large<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline19.png' mime-subtype='png'/><tex-math>$n$</tex-math></alternatives></inline-formula>, any<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline20.png' mime-subtype='png'/><tex-math>$n$</tex-math></alternatives></inline-formula>-vertex<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline21.png' mime-subtype='png'/><tex-math>$\mathcal{F}\cup \{C_k\}$</tex-math></alternatives></inline-formula>-free graph with minimum degree at least<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline22.png' mime-subtype='png'/><tex-math>$\rho (\frac{2n}{5}+o(n))^{\alpha -1}$</tex-math></alternatives></inline-formula>is bipartite. In this paper, we strengthen their result by showing that for every real<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline23.png' mime-subtype='png'/><tex-math>$\delta \gt 0$</tex-math></alternatives></inline-formula>, there exists<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline24.png' mime-subtype='png'/><tex-math>$k_0$</tex-math></alternatives></inline-formula>such that for all odd<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline25.png' mime-subtype='png'/><tex-math>$k\geq k_0$</tex-math></alternatives></inline-formula>and sufficiently large<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline26.png' mime-subtype='png'/><tex-math>$n$</tex-math></alternatives></inline-formula>, any<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline27.png' mime-subtype='png'/><tex-math>$n$</tex-math></alternatives></inline-formula>-vertex<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline28.png' mime-subtype='png'/><tex-math>$\mathcal{F}\cup \{C_k\}$</tex-math></alternatives></inline-formula>-free graph with minimum degree at least<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline29.png' mime-subtype='png'/><tex-math>$\delta n^{\alpha -1}$</tex-math></alternatives></inline-formula>is bipartite. Furthermore, our result holds under a more relaxed notion of smoothness, which include the families<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline30.png' mime-subtype='png'/><tex-math>$\mathcal{F}$</tex-math></alternatives></inline-formula>consisting of the single graph<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline31.png' mime-subtype='png'/><tex-math>$K_{s,t}$</tex-math></alternatives></inline-formula>when<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline32.png' mime-subtype='png'/><tex-math>$t\gg s$</tex-math></alternatives></inline-formula>. We also prove an analogous result for<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline33.png' mime-subtype='png'/><tex-math>$C_{2\ell }$</tex-math></alternatives></inline-formula>-free graphs for every<inline-formula><alternatives><inline-graphic href='S0963548323000019_inline34.png' mime-subtype='png'/><tex-math>$\ell \geq 2$</tex-math></alternatives></inline-formula>, which complements a result of Keevash, Sudakov and Verstraëte.</p>Cambridge University Press2023-02-0310544185Combinatorics, Probability and Computing324546-5580963-5483https://doi.org/10.1017/S09635483230000191855542National Science Foundation