Combinatorics, Probability and Computing

Research Article

An Upper Bound on Zarankiewicz' Problem

Zoltán Füredia1

a1 Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801-2975, USA and Mathematical Institute of the Hungarian Academy of Sciences, PO Box 127, Budapest 1364, Hungary


Let ex(n, K3,3) denote the maximum number of edges of a K3,3-free graph on n vertices. Improving earlier results of Kővári, T. Sós and Turán on Zarankiewicz' problem, we obtain that Brown's example for a maximal K3,3-free graph is asymptotically optimal. Hence S0963548300001814inline1.

(Received January 05 1995)

(Revised March 09 1995)