The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A072567 A variant of Zarankiewicz problem: maximal number of 1s in n X n 01-matrix with no four 1s forming a rectangle. 7
 1, 3, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45, 52, 56, 61, 67, 74, 81, 88, 96, 105, 108, 115, 122 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS Proving a(13) < 53 and finding a(7) were problems at the 1975 USSR National Olympiad and are presented in the Ross Honsberger 1985 book "Mathematical Gems III" (see links). - 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 Conjecture: the same number of 1s is achieved for symmetric n X n matrices (cf. A350189). - Max Alekseyev, Apr 03 2022 LINKS Brendan McKay's Largest graphs of girth at least 6, MathOverflow, 2012. [The number of edges given there for even n seem to be the terms of this sequence. 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. R. Honsberger, Two Problems from the 1974 USSR National Olympiad (#4 and #9). Excerpt from "Mathematical Gems III" book, 1985. [In fact, these problems are from the olympiad of 1975, not 1974, and were published as Problem M335 in Kvant 7 (1975).] E. Belaga, Solution to Problem M335, Kvant 3 (1976), 42-44. (in Russian) FORMULA For prime powers q, a(q^2+q+1) = (q+1)(q^2+q+1). It follows from equality case of Reiman inequality. For example, a(21)=105 and a(31)=186. - Senya Karpenko, Jul 23 2014 a(n) = A001197(n) - 1 for n>=2. - Rob Pratt, Aug 09 2019 EXAMPLE Examples of a(2)=3, a(3)=6, and a(4)=9: 11   110   1110 10   101   1001      011   0101            0011 a(4)=9 is also achieved at a symmetric matrix: 0111 1010 1100 1001 - Max Alekseyev, Apr 03 2022 CROSSREFS Cf. A001197. Sequence in context: A214050 A260706 A194199 * A186353 A061796 A113241 Adjacent sequences:  A072564 A072565 A072566 * A072568 A072569 A072570 KEYWORD nonn,nice,hard,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 a(22)-a(24) from Jeremy Tan, Jan 23 2022 Edited by Max Alekseyev, Apr 03 2022 STATUS approved

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

Last modified October 6 12:00 EDT 2022. Contains 357264 sequences. (Running on oeis4.)