|
%I M3300 N1330 #51 Apr 03 2022 22:28:13
%S 4,7,10,13,17,22,25,30,35,40,46,53,57,62,68,75,82,89,97,106,109,116,
%T 123
%N Zarankiewicz's problem k_2(n).
%C 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
%C a(n) <= (1 + sqrt(4*n-3))*n/2 + 1. - _Max Alekseyev_, Apr 03 2022
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 291.
%D 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.
%D Richard J. Nowakowski, Zarankiewicz's Problem, PhD Dissertation, University of Calgary, 1978, page 202.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H R. K. Guy, <a href="/A001197/a001197.pdf">A problem of Zarankiewicz</a>, Research Paper No. 12, Dept. of Math., Univ. Calgary, Jan. 1967. [Annotated and scanned copy, with permission]
%H R. K. Guy, <a href="http://dx.doi.org/10.1007/BFb0060112">A many-facetted problem of Zarankiewicz</a>, Lect. Notes Math. 110 (1969), 129-148.
%F a(n) = A072567(n) + 1. - _Rob Pratt_, Aug 09 2019
%F a(n) = n^2 - A347472(n) = n^2 - A350296(n) + 1. - _Andrew Howroyd_, Dec 26 2021
%Y Cf. A001198 (k_3), A072567, A339635, A347472, A350296.
%Y Cf. also A006613 - A006626 (other sizes, in particular A006616 = k_4).
%K nonn,hard,more
%O 2,1
%A _N. J. A. Sloane_
%E 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
%E a(1) deleted following a suggestion from _M. F. Hasler_. - _N. J. A. Sloane_, Oct 22 2021
%E a(22)-a(24) from _Jeremy Tan_, Jan 23 2022
|
