The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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 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.

Last modified January 22 10:52 EST 2020. Contains 331144 sequences. (Running on oeis4.)