A001197 Zarankiewicz's problem k_2(n). (Formerly M3300 N1330)

4, 7, 10, 13, 17, 22, 25, 30, 35, 40, 46, 53, 57, 62, 68, 75, 82, 89, 97, 106, 109, 116, 123

Offset

2,1

Comments

a(n) is the minimum number k_2(n) such that any n X n matrix having that number of nonzero entries has a 2 X 2 submatrix with only nonzero entries. - M. F. Hasler, Sep 28 2021

a(n) <= (1 + sqrt(4*n-3))*n/2 + 1. - Max Alekseyev, Apr 03 2022

References

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 291.

R. K. Guy, A problem of Zarankiewicz, in P. Erdős and G. Katona, editors, Theory of Graphs (Proceedings of the Colloquium, Tihany, Hungary), Academic Press, NY, 1968, pp. 119-150.

Richard J. Nowakowski, Zarankiewicz's Problem, PhD Dissertation, University of Calgary, 1978, page 202.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

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

R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.

Formula

a(n) = A072567(n) + 1. - Rob Pratt, Aug 09 2019

a(n) = n^2 - A347472(n) = n^2 - A350296(n) + 1. - Andrew Howroyd, Dec 26 2021

Crossrefs

Cf. A001198 (k_3), A072567, A339635, A347472, A350296.

Cf. also A006613 - A006626 (other sizes, in particular A006616 = k_4).

Main diagonal of A376167.

Keyword

nonn,hard,more

Author

N. J. A. Sloane

Extensions

Nowakowski's thesis, directed by Guy, corrected Guy's value for a(15) and supplied a(16)-a(21) entered by Don Knuth, Aug 13 2014

a(1) deleted following a suggestion from M. F. Hasler. - N. J. A. Sloane, Oct 22 2021

a(22)-a(24) from Jeremy Tan, Jan 23 2022

Status

approved

A001198 Zarankiewicz's problem k_3(n). (Formerly M4601 N1962)

9, 14, 21, 27, 34, 43, 50, 61, 70, 81, 93, 106, 121, 129

Offset

3,1

Comments

Guy denotes k_{a,b}(m,n) the least k such that any m X n matrix with k '1's and '0's elsewhere has an a X b submatrix with all '1's, and omits b (resp. n) when b = a (resp. n = m). With this notation, a(n) = k_3(n). Sierpiński (1951) found a(4..6), a(7) is due to Brzeziński and a(8) due to Čulík (1956). - M. F. Hasler, Sep 28 2021

References

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 291.

R. K. Guy, A problem of Zarankiewicz, in P. Erdős and G. Katona, editors, Theory of Graphs (Proceedings of the Colloquium, Tihany, Hungary), Academic Press, NY, 1968, pp. 119-150.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=3..16.

R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.

Jeremy Tan, An attack on Zarankiewicz's problem through SAT solving, arXiv:2203.02283 [math.CO], 2022.

Formula

a(n) = A350304(n) + 1 = n^2 - A347473(n) = n^2 - A350237(n) + 1. - Andrew Howroyd, Dec 26 2021

Example

From M. F. Hasler, Sep 28 2021: (Start)
For n = 3 it is clearly necessary and sufficient that there be 3 X 3 = 9 ones in the n X n matrix in order to have an all-ones 3 X 3 submatrix.
For n = 4 there may be at most 2 zeros in the 4 X 4 matrix in order to be guaranteed to have a 3 X 3 submatrix with all '1's, whence a(4) = 16 - 2 = 14: If 3 zeros are placed on a diagonal, it is no more possible to find a 3 X 3 all-ones submatrix, but if there are at most 2 zeros, one always has such a submatrix, as one can see from the following two diagrams:
                                       0 1 1 1        0 1 1 1      no 3 X 3
     Here one can delete, e.g.,   ->   1 0 1 1        1 0 1 1  <-  all-ones
     row 1 and column 2 to get         1 1 1 1        1 1 0 1      submatrix
     an all-ones 3 X 3 matrix.         1 1 1 1        1 1 1 1        (End)

Crossrefs

Cf. A001197 (k_2(n)), A006613 (k_{2,3}(n)), ..., A006626 (k_4(n,n+1)).

Cf. A339635, A347473, A350237, A350304.

Keyword

nonn,more,hard

Author

N. J. A. Sloane

Extensions

a(11)-a(13) from Andrew Howroyd, Dec 26 2021

a(14)-a(15) computed from A350237 by Max Alekseyev, Apr 01 2022

a(16) from Jeremy Tan, Oct 02 2022

Status

approved

A006626 Zarankiewicz's problem k_4(n,n+1). (Formerly M5071)

19, 27, 37, 46, 56, 68, 80, 94, 109

Offset

4,1

Comments

a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all ones 4 X 4 submatrix. - Sean A. Irvine, May 18 2017

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=4..12.

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.

Crossrefs

Cf. A006616 (k_4(n)), A006620 (k_2(n,n+1)), A006621 (k_3(n,n+1)).

Keyword

nonn,more

Author

N. J. A. Sloane

Extensions

a(9)-a(12) from Andrew Howroyd, Dec 26 2021

Status

approved

A072567 A variant of Zarankiewicz problem: maximal number of 1s in n X n 01-matrix with no four 1s forming a rectangle.

1, 3, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45, 52, 56, 61, 67, 74, 81, 88, 96, 105, 108, 115, 122

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.

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

A006613 Zarankiewicz's problem. (Formerly M4484)

8, 13, 17, 22, 29, 34, 40, 47, 56

Offset

3,1

Comments

a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all ones 2 X 3 submatrix. - Sean A. Irvine, May 16 2017

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=3..11.

R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.

Keyword

nonn,more

Author

N. J. A. Sloane

Status

approved

A006616 Zarankiewicz's problem k_4(n). (Formerly M4998)

16, 23, 32, 43, 52, 62, 75, 87, 101, 118

Offset

4,1

Comments

a(n) is the least k such that every n X n {0,1}-matrix with k ones contains an all ones 4 X 4 submatrix. - Sean A. Irvine, May 17 2017

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=4..13.

R. K. Guy, A problem of Zarankiewicz, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.

Dmitry I. Ignatov, When contranominal scales give a solution to the Zarankiewicz problem?, Workshop Notes, 12th Int'l Wksp. Formal Concept Analysis Artif. Intel. (FCA4AI 2024), 27-38. See p. 34.

Formula

a(n) = n^2 - A347474(n). - Andrew Howroyd, Dec 26 2021

Crossrefs

Cf. A001197, A001198, A006626, A339635, A347474.

Keyword

nonn,hard,more,changed

Author

N. J. A. Sloane

Extensions

a(9)-a(13) from Andrew Howroyd, Dec 26 2021

Status

approved

A191873 A problem of Zarankiewicz: maximal number of 1's in an n X n matrix of 0's and 1's with 0's on the main diagonal and no "rectangle" with 1's at the four corners.

0, 2, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45

Offset

1,2

Comments

In other words, the pattern

1...1

.....

1...1

is forbidden.

From Don Knuth, Aug 13 2014: (Start)

Well, it is well known from A001197 that a(8)<25. A001197 is essentially the same problem, but increased by 1, and without restricting the diagonals. The diagonal restriction is however of little interest, because it's easy to permute rows and columns and get all 0's or all 1's or probably any of the 2^n possible settings of the diagonal. At least, this is true when n=8; hence a(8) in this sequence is 24.

Transposing cols 1<->4 and 5<->8 in the example by Guy 1967 page 130 as cited in A001197 gives a(8)=24:

01110000

10010100

00010011

01000101

10100010

11001000

00101001

00001110

But as stated above, I think this is quite trivial, and I believe this sequence should be downplayed. Readers should look at the sequence A001197 --- that's what Zarankiewicz's problem asked for in 1951, namely the min number that forces a rectangle, not the max number that doesn't exclude it.

(end)

Conjecture: for n >= 3, a(n) = A072567(n) = A001197(n) - 1 (per above comment). - Max Alekseyev, Jan 29 2022

References

B. Bollobas, Extremal Graph Theory, pp. 309ff.

Links

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

D. Bienstock and E. Gyori, An extremal problem on sparse 0-1 matrices, SIAM J. Discrete Math. 4 (1991), 17-27.

Crossrefs

Cf. A072567, A191874, A191965, A191966.

Keyword

nonn,more

Author

R. H. Hardin and N. J. A. Sloane, Jun 18 2011

Extensions

a(8) confirmed, a(9)-a(12) added by Max Alekseyev, Feb 07 2022

Status

approved

A191965 A problem of Zarankiewicz: maximal number of 1's in a symmetric n X n matrix of 0's and 1's with 0's on the main diagonal and no "rectangle" with 1's at the four corners.

0, 2, 6, 8, 12, 14, 18, 22, 26, 32, 36, 42, 48, 54, 60, 66, 72, 78, 84, 92, 100, 104, 112, 118, 126, 134, 142, 152, 160, 170, 180, 184, 192, 204, 212, 220, 226, 234, 244, 254

Offset

1,2

Comments

In other words, the pattern

1...1

.....

1...1

is forbidden.

Such matrices are adjacency matrices of squarefree graphs (cf. A006786). The number of matrices with a(n) ones is given by A191966 and A335820 (up to permutations of rows/columns). - Max Alekseyev, Jan 29 2022

References

B. Bollobas, Extremal Graph Theory, pp. 309ff.

Links

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

D. Bienstock E. Gyori, An extremal problem on sparse 0-1 matrices. SIAM J. Discrete Math. 4 (1991), 17-27.

Formula

a(n) = 2 * A006855(n). - Max Alekseyev, Jan 29 2022

Crossrefs

Cf. A006786, A006855, A077269, A191873 A191874, A191966, A300756, A335820, A352472.

Keyword

nonn,more

Author

R. H. Hardin and N. J. A. Sloane, Jun 18 2011

Extensions

a(11)-a(40) computed from A006855 by Max Alekseyev, Jan 28 2022; Apr 2, 2022; Mar 14 2023

Status

approved

A006620 A variant of Zarankiewicz's problem: a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all-ones 2 X 2 submatrix. (Formerly M3775)

5, 8, 11, 15, 19, 23, 27, 32, 37, 43, 49, 54, 59, 64

Offset

2,1

Comments

a(n) <= A205805(2*n+1) + 1. - Max Alekseyev, Feb 02 2024

References

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=2..15.

Crossrefs

Cf. A006613, A006614, A006615, A006616, A006617, A006618, A006619, A006621, A006622, A006623, A006624, A006625, A006626.

Cf. A001197, A072567, A191965, A191873, A001198, A205805, A347473, A347474, A350304, A350237.

Keyword

nonn,more

Author

N. J. A. Sloane

Extensions

Name changed at the suggestion of Sean A. Irvine by Max Alekseyev, Feb 02 2024

Status

approved

A006621 Zarankiewicz's problem k_3(n,n+1). (Formerly M4776)

11, 17, 23, 30, 38, 46, 55, 65, 75, 87

Offset

3,1

Comments

a(n) is the least k such that every n X (n+1) {0,1}-matrix with k ones contains an all ones 3 X 3 submatrix. - Sean A. Irvine, May 18 2017

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=3..12.

R. K. Guy, A many-facetted problem of Zarankiewicz, Lect. Notes Math. 110 (1969), 129-148.

Crossrefs

Cf. A001198 (k_3(n)), A006620 (k_2(n,n+1)), A006626 (k_4(n,n+1)).

Keyword

nonn,more

Author

N. J. A. Sloane

Extensions

a(10)-a(12) from Andrew Howroyd, Dec 26 2021

Status

approved