A301370 Maximum determinant of an n X n (0,1)-matrix that has exactly 2*n ones.

0, 2, 2, 3, 4, 4, 6, 8, 9, 12, 16, 18, 24, 32, 36, 48, 64

Offset

2,2

Comments

A proved upper bound is abs(a(n)) <= 6^(n/6), provided by Bruhn and Rautenbach. A conjectured sharper bound is abs(a(n)) <= 2^(n/3), provided by the same authors. For n=3*k, the bound is achieved by diagonally concatenating blocks ((1 1 0)(0 1 1)(1 0 1)).

The sharper bound is proved by Araujo, Balogh, and Wang in their article. See link. - Hugo Pfoertner, Nov 04 2020

Links

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

Igor Araujo, József Balogh, and Yuzhou Wang, Maximum determinant and permanent of sparse 0-1 matrices, arXiv:2011.01892 [math.CO], 3 Nov 2020.

Henning Bruhn and Dieter Rautenbach, Maximal determinants of combinatorial matrices, arXiv:1711.09935 [math.CO], 2017.

Mathoverflow, Are bounds known for the maximum determinant of a (0,1)-matrix of specified size and with a specifed number of 1s?, 2014-2018.

Yaroslav Shitov, On the determinant of a sparse 0-1 matrix, Linear Algebra and its Applications, Volume 554, 1 October 2018, Pages 49-50.

Markus Sigg, Gasper's determinant theorem, revisited, arXiv:1804.02897 [math.CO], 2018.

Example

a(8) = 6 because no (0,1)-matrix with 2*8 ones with a greater determinant exists than
  ( 1 0 0 0 0 0 0 0 )
  ( 0 1 0 1 0 0 0 0 )
  ( 0 0 1 0 1 1 0 0 )
  ( 0 0 0 1 0 0 1 0 )
  ( 0 0 0 0 1 0 0 1 )
  ( 0 0 0 0 0 1 0 1 )
  ( 0 1 0 0 0 0 1 0 )
  ( 0 0 1 0 0 0 0 1 )

Crossrefs

Cf. A003432, A017979, A085000.

Sequence in context: A292420 A161654 A325854 * A342520 A225482 A004056

Adjacent sequences: A301367 A301368 A301369 * A301371 A301372 A301373

Keyword

nonn,hard,more

Author

Hugo Pfoertner, Mar 20 2018

Status

approved