A070214 Maximal number of occupied cells in all monotonic matrices of order n.

1, 2, 5, 8, 11, 14, 19, 23, 28, 32, 38, 43, 49, 55

Offset

1,2

Comments

A monotonic matrix of order n is an n X n matrix in which every cell contains 0 or 1 numbers from the set {1...n} subject to 3 conditions:

(1) The filled-in entries in each row are strictly increasing;

(2) The filled-in entries in each column are strictly decreasing;

(3) For two filled-in cells with same entry, the one further right is higher (the positive slope condition).

From Rob Pratt: The problem can be formulated as a maximum independent set problem in a graph with n^3 nodes (i, j, k) in {1, 2, ..., n}^3. If node (i, j, k) appears in the solution, the interpretation is that cell (i, j) should contain k. The arcs, which indicate conflicting choices, are as follows:

Arc joining (I1, j1, k1) and (i2, j2, k2) if:

[rows increasing] i1 = i2 and ((j1 < j2 and k1 >= k2) or (j1 > j2 and k1 <= k2)).

[columns decreasing] j1 = j2 and ((i1 < i2 and k1 <= k2) or (i1 > i2 and k1 >= k2)).

[one color per cell] i1 = i2 and j1 = j2 and k1 <> k2.

[positive slope] k1 = k2 and i1 <> i2 and (j2 - j1) / (i2 - i1) > 0.

Links

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

Boris Aronov, Vida Dujmović, Pat Morin, Aurélien Ooms, Luís Fernando Schultz Xavier da Silveira, More Turán-Type Theorems for Triangles in Convex Point Sets, arXiv:1706.10193 [math.CO], 2017.

W. Hamaker and S. K. Stein, Combinatorial packing of R^3 by certain error spheres, IEEE Trans. Information Theory, 30 (No. 2, 1984), 364-368.

Patric R. J. Östergård, and Antti Pöllänen, New Results on Tripod Packings, Discrete & Computational Geometry 61.2 (2019): 271-284

S. K. Stein and S. Szabo, Algebra and Tiling, MAA Carus Monograph 25, 1994, page 95.

Alexandre Tiskin, Tripods do not pack densely, Lecture Notes in Computer Science, 1858 (2000), 272-280.

Alexandre Tiskin, Packing tripods: narrowing the density gap, Discrete Math., 307 (2007), 1973-1981.

Eric Weisstein's World of Mathematics, Monotonic Matrix

Formula

a(r*s) >= a(r)*a(s); if a(n) = n^e(n) then L := lim_{n->infinity} e(n) exists and is in the range 1.513 <= L <= 2.

Tiskin showed that a(n) = o(n^2).

Example

a(3) >= 5 from this matrix:
  2 - 3
  - - 1
  1 3 -
a(5) >= 11 from this matrix:
  - - 4 - 5
  4 - - 5 -
  - - 1 2 3
  3 5 - - -
  1 2 - - -
Dean Hickerson found the following matrix, which improves the lower bound for a(8) to 23: (This is now known to be optimal)
  - - 2 - - 4 7 8
  - - 1 7 8 - - -
  7 8 - - - - - -
  - 2 - 4 - - - 6
  - 1 - - - 3 6 -
  4 - - - 6 - - -
  2 - - - 3 - - 5
  1 - - 3 - - 5 -
Paul Jungeblut improves the lower bound for a(11) to 38 with this matrix.
  -- --  8 -- -- --  9 -- -- -- 11
  --  8 -- -- --  9 -- -- -- -- 10
   8 -- -- --  9 -- -- -- 10 11 --
  -- -- -- -- -- -- -- --  4  5  7
  --  4 -- -- --  5  7 11 -- -- --
  -- -- -- -- --  1 -- --  2  3  6
   4 -- -- --  5 --  6 10 -- -- --
  -- -- -- --  1 --  2  3 -- -- --
   2  3  7 11 -- -- -- -- -- -- --
  --  1  6 10 -- -- -- -- -- -- --
   1 --  5  9 -- -- -- -- -- -- --

Crossrefs

Cf. A086976.

Sequence in context: A163516 A000093 A324476 * A330031 A031210 A287960

Adjacent sequences: A070211 A070212 A070213 * A070215 A070216 A070217

Keyword

nonn,more,hard,nice

Author

N. J. A. Sloane, Jul 24 2003, Jun 19 2007

Extensions

a(1)-a(5) computed by K. Joy. a(6) = 14 was established by Szabo.

Jul 27 2003 - Aug 23 2003: Rob Pratt has used integer programming to confirm the values for n <= 6 and has shown that a(7) = 19, 23 <= a(8) <= 28, 28 <= a(9) <= 42 and 32 <= a(10) <= 62.

Extended to a(14) from Tiskin (2007), who gives a(15) >= 61, a(16) >= 65.

a(11) corrected by Paul Jungeblut, Jul 09 2020

Status

approved