login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A072567 Size of maximal set of points in an n X n (side length) grid such that no 4-set of it forms a rectangle with horizontal/vertical sides. 1

%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 4-set 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/largest-graphs-of-girth-at-least-6">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 3-4 , pp 269-273.

%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-* *-O-O-*

%e | | | | | | |

%e O-*-* O-*-O-*

%e | | | |

%e O-O-*-*

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 20 07:54 EST 2020. Contains 332069 sequences. (Running on oeis4.)