login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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

Table of n, a(n) for n=1..24.

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.

License Agreements, Terms of Use, Privacy Policy. .

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