%I
%S 1,3,6,9,12,16,21,24,29,34,39,45,52,56,61,67,74,81,88,96,105
%N Size of maximal set of points in an n X n (side length) grid such that no 4set of it forms a rectangle with horizontal/vertical sides.
%C Finding a(7) is presented as a puzzle in Mathematical Gems III by Ross Honsberger on page 4.  _Tanya Khovanova_, Oct 12 2007
%C The growth rate of a(n) is O(n^{3/2}). For a lower bound, take the incidence graph of a finite projective plane. For prime powers q, you get a(q^2+q+1) >= (q+1)(q^2+q+1). For an upper bound, the matrix is an adjacency matrix of a bipartite graph of girth 6. These have at most O(n^{3/2}) edges.  _Peter Shor_, Jul 01 2013
%C For prime powers q, a(q^2+q+1) is exactly (q+1)(q^2+q+1). It follows from equality case of Reiman inequality. For example, a(21)=105.  _Senya Karpenko_, Jul 23 2014
%H Brendan McKay's <a href="http://mathoverflow.net/questions/99770/largestgraphsofgirthatleast6">Math Overflow question</a> about graphs of girth 6. These numbers seem to be the terms of the sequence given there for even n. They are certainly bounded above by them.
%H Stefan Neuwirth, <a href="http://arxiv.org/abs/math/0102210">The size of bipartite graphs with girth eight</a>, arXiv:math/0102210 [math.CO], 2001.
%H I. Reiman, <a href="http://dx.doi.org/10.1007/BF02020254 ">Über ein Problem von K. Zarankiewicz</a>, Acta Mathematica Academiae Scientiarum Hungarica, Volume 9, Issue 34 , pp 269273.
%F a(n) = A001197(n)  1 for n>=2.  _Rob Pratt_, Aug 09 2019
%e Examples of a(1)=3, a(2)=6, and a(3)=9:
%e ** **O ***O
%e         
%e *O *O* *OO*
%e       
%e O** O*O*
%e    
%e OO**
%Y Cf. A001197.
%K nonn,nice,more
%O 1,2
%A Xuli Le (leshlie(AT)eyou.com), Jun 21 2002
%E a(1) = 1 from _Don Reble_, Oct 13 2007
%E More terms (using formula and A001197) from _Rob Pratt_, Aug 09 2019
