---

Claim. $\mathrm{ex}(n;K_{3,3})\gg n^{5/3}$ and $\mathrm{ex}(n;K_{2,2})\gg n^{3/2}$, the statement of Problem 714 for $r=3$ and $r=2$. W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), no. 3, 281--285 (received 7 February 1966; issue 3, August 1966, the month this page's name uses); library source card. Brown writes $g(n)$ for the largest $m$ such that some graph on $n$ vertices with $m-1$ edges contains no Thomsen graph $K_{3,3}$, so $g(n)=\mathrm{ex}(n;K_{3,3})+1$. His main theorem (Section 2): for every odd prime $p$ the graph on the $p^3$ points of the affine space $EG(3,p)$, two points joined when $\sum_{i=1}^3(x_i-y_i)^2$ equals a fixed element $\alpha$ of $GF(p)$ (a nonzero quadratic residue when $p\equiv3\pmod4$, a non-residue otherwise), is $(p^2-p)$-regular, has $(p^5-p^4)/2$ edges and contains no $K_{3,3}$, which is inequality (2.8), $g(p^3)>(p^5-p^4)/2$; a prime between $(1-\varepsilon)^{1/5}n^{1/3}$ and $n^{1/3}$ carries the bound to every large $n$ (p. 284), so $g(n)>cn^{5/3}$ for some $c>0$, Brown's conjecture (1.2), which he attributes to Kővári, Sós and Turán and to Erdős, and $\liminf n^{-5/3}g(n)\ge\tfrac12$. With the Kővári--Sós--Turán upper bound (1.1), $\mathrm{ex}(n;K_{3,3})=\Theta(n^{5/3})$. Section 3, "Graphs without quadrangles" (p. 284), adds the polarity graph on the $q^2+q+1$ points of $PG(2,q)$, with $(q^2+q+1)^{3/2}/2+O(q^2)$ edges and no quadrilateral, and states $\lim f(n)n^{-3/2}=\tfrac12$ for the largest edge count $f(n)$ of a quadrilateral-free graph on $n$ vertices; since $K_{2,2}=C_4$, this is $\mathrm{ex}(n;K_{2,2})=(\tfrac12+o(1))n^{3/2}$, the case $r=2$, found independently of Erdős, Rényi and Sós, as Brown records and as the footnote on p. 219 of their paper confirms.

Covers. The instances $r=3$ and $r=2$ of the statement for every $r\ge2$. Nothing for any $r\ge4$, which remain open; the problem has no full claim. For $r=2$ the same instance is settled on the pages of Kővári, Sós and Turán and Erdős, Rényi and Sós.

Depends on. Nothing in this wiki: the constructions and the passage to all $n$ are the paper's.

Acceptance. Refereed: Canadian Mathematical Bulletin, a refereed journal, doi:10.4153/CMB-1966-036-2. No reviewed evidence is listed: the site labels the problem OPEN, and its commentary crediting Brown with the case $r=3$ is not an acceptance of the problem. This corpus supplies no independent proof review: the statements of (2.8) and of Section 3 are checked against the print, and the proofs are not.