The number of \(K_{m,m}\)-free graphs (Q653990): Difference between revisions

For any forbidden subgraph \(H\), the authors denote by \(f_n(H)\) the number of labelled \(H\)-free graphs on \(n\) vertices; this is the \(F_n(H)\) of \textit{P. Erdős, P. Frankl} and \textit{V. Rödl} [``The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent,'' Graphs Comb. 2, 113--121 (1986; Zbl 0593.05038)]. In Theorem 1.6 of the cited paper it was proved that, when \(\chi(H) \geq 3\), \(\log_2\left(f_n(H)\right) =\text{ex}(n,H)\cdot(1+{\text o}(1))\) as \(n\to\infty\), and conjectured that the same result should hold also when \(\chi(H)=2\). For complete bipartite graphs whose parts have the same size the present authors prove (Theorem 1.2): \[ \log_2\left(f_n\left(K_{m,m}\right)\right) \leq(1+{\text o}(1))\cdot\frac{m(m-1)^\frac1m}{2m-1}\cdot C_m\cdot n^{2-\frac1m}, \text{ as }n\to\infty, \] \[ \text{where }C_m=\sup_{x\in(0,1)}\left\{x^{-1+\frac1m}\cdot\left(-x\log_2x-(1-x)\log_2(1-x)\right)\right\}. \] They also address a conjecture of \textit{P. E. Haxell}, \textit{Y. Kohayakawa} and \textit{T. Łuczak} [``Turán's extremal problem in random graphs: Forbidding even cycles,'' J. Comb. Theory, Ser. B 64, No.\,2, 273--287 (1995; Zbl 0828.05056)]. The authors report that, subsequent to submission of the present paper, they have, in \textit{J. Balogh} and \textit{W. Samotij} [``The number of \(K_{s,t}\)-free graphs,'' J. Lond. Math. Soc., II. Ser. 83, 368--388 (2011; Zbl 1227.05170)], generalized their results to complete bipartite graphs \(K_{s,t}\) where \(2 \leq s \leq t\) .