

A072567


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.


1



1, 3, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45, 52, 56, 61, 67, 74, 81, 88, 96, 105
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Finding a(7) is presented as a puzzle in Mathematical Gems III by Ross Honsberger on page 4.  Tanya Khovanova, Oct 12 2007
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
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


LINKS

Table of n, a(n) for n=1..21.
Brendan McKay's Math Overflow question 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.
Stefan Neuwirth, The size of bipartite graphs with girth eight, arXiv:math/0102210 [math.CO], 2001.
I. Reiman, Über ein Problem von K. Zarankiewicz, Acta Mathematica Academiae Scientiarum Hungarica, Volume 9, Issue 34 , pp 269273.


FORMULA

a(n) = A001197(n)  1 for n>=2.  Rob Pratt, Aug 09 2019


EXAMPLE

Examples of a(1)=3, a(2)=6, and a(3)=9:
** **O ***O
        
*O *O* *OO*
      
O** O*O*
   
OO**


CROSSREFS

Cf. A001197.
Sequence in context: A214050 A260706 A194199 * A186353 A061796 A113241
Adjacent sequences: A072564 A072565 A072566 * A072568 A072569 A072570


KEYWORD

nonn,nice,more


AUTHOR

Xuli Le (leshlie(AT)eyou.com), Jun 21 2002


EXTENSIONS

a(1) = 1 from Don Reble, Oct 13 2007
More terms (using formula and A001197) from Rob Pratt, Aug 09 2019


STATUS

approved



