Norm-graphs and bipartite Turán numbers (Q2563514): Difference between revisions

\textit{T. Kövári}, \textit{V. T. Sós} and \textit{P. Turán} [Colloq. Math. 3, 50-57 (1954; Zbl 0055.00704)] proved that, for the complete bipartite graph \(K_{t,s}\) whose ``parts'' contain, respectively, \(t\) and \(s\) vertices \((s\geq t)\), \(\text{ex}(n,K_{t,s})\leq c_{t,s}n^{2-{1\over t}}\), where \(c_{t,s}\) is a constant. This result has been proved best possible in magnitude for \(t=2\) [\textit{P. Erdös}, \textit{A. Rényi} and \textit{V. T. Sós}, Stud. Sci. Math. Hung. 1, 215-235 (1966; Zbl 0144.23302)]; [\textit{Z. Füredi}, Turán type problems, Surveys in combinatorics, Lond. Math. Soc. Lect. Note Ser. 166, 253-300 (1991; Zbl 0727.05032)]; [the reviewer, reference cited below]; and in the case \(s=t=3\) [the reviewer, Can. Math. Bull. 9, 281-285 (1966; Zbl 0178.27302)]. From the authors' abstract: ``For every \(t>1\) and positive \(n\) we construct explicit examples of graphs \(G\) with \(|V(G)|=n\), \(|E(G)|\geq c_t\cdot n^{2-{1\over t}}\) which do not contain a complete bipartite graph \(K_{t,t!+1}\). This establishes the exact order of magnitude of the Turán numbers \(\text{ex}(n,K_{t,s})\) for any fixed \(t\) and all \(s\geq t!+1\), improving over the previous probabilistic lower bounds for such pairs \((t,s)\). The construction relies on elementary facts from commutative algebra.'' In a note added in proof the authors report a strengthening of the inequality above to \(s\geq(t-1)!+1\); thus \(\text{ex}(n,K_{4,7})\geq c\cdot n^{2-{1\over 4}}\).