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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

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
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 3-4 , pp 269-273.

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

          | | |    | | | |

          O-*-*    O-*-O-*

                   | | | |

                   O-O-*-*

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

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 January 22 10:52 EST 2020. Contains 331144 sequences. (Running on oeis4.)