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

%I #32 Jun 02 2024 19:52:21

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

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

%C 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:

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

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

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

%C 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:

%C Arc joining (i1, j1, k1) and (i2, j2, k2) if:

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

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

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

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

%H Boris Aronov, Vida Dujmović, Pat Morin, Aurélien Ooms, Luís Fernando Schultz Xavier da Silveira, <a href="https://arxiv.org/abs/1706.10193">More Turán-Type Theorems for Triangles in Convex Point Sets</a>, arXiv:1706.10193 [math.CO], 2017.

%H W. Hamaker and S. K. Stein, <a href="https://doi.org/10.1109/TIT.1984.1056868">Combinatorial packing of R^3 by certain error spheres</a>, IEEE Trans. Information Theory, 30 (No. 2, 1984), 364-368.

%H Patric R. J. Östergård, and Antti Pöllänen, <a href="https://doi.org/10.1007/s00454-018-0012-2">New Results on Tripod Packings</a>, Discrete & Computational Geometry 61.2 (2019): 271-284

%H S. K. Stein and S. Szabo, <a href="https://www.maa.org/press/ebooks/algebra-and-tiling">Algebra and Tiling</a>, MAA Carus Monograph 25, 1994, page 95.

%H Alexandre Tiskin, <a href="https://doi.org/10.1007/3-540-44968-X_27">Tripods do not pack densely</a>, Lecture Notes in Computer Science, 1858 (2000), 272-280.

%H Alexandre Tiskin, <a href="https://doi.org/10.1016/j.disc.2004.12.028">Packing tripods: narrowing the density gap</a>, Discrete Math., 307 (2007), 1973-1981.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MonotonicMatrix.html">Monotonic Matrix</a>

%F 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.

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

%e a(3) >= 5 from this matrix:

%e 2 - 3

%e - - 1

%e 1 3 -

%e a(5) >= 11 from this matrix:

%e - - 4 - 5

%e 4 - - 5 -

%e - - 1 2 3

%e 3 5 - - -

%e 1 2 - - -

%e Dean Hickerson found the following matrix, which improves the lower bound for a(8) to 23: (This is now known to be optimal)

%e - - 2 - - 4 7 8

%e - - 1 7 8 - - -

%e 7 8 - - - - - -

%e - 2 - 4 - - - 6

%e - 1 - - - 3 6 -

%e 4 - - - 6 - - -

%e 2 - - - 3 - - 5

%e 1 - - 3 - - 5 -

%e Paul Jungeblut improves the lower bound for a(11) to 38 with this matrix.

%e -- -- 8 -- -- -- 9 -- -- -- 11

%e -- 8 -- -- -- 9 -- -- -- -- 10

%e 8 -- -- -- 9 -- -- -- 10 11 --

%e -- -- -- -- -- -- -- -- 4 5 7

%e -- 4 -- -- -- 5 7 11 -- -- --

%e -- -- -- -- -- 1 -- -- 2 3 6

%e 4 -- -- -- 5 -- 6 10 -- -- --

%e -- -- -- -- 1 -- 2 3 -- -- --

%e 2 3 7 11 -- -- -- -- -- -- --

%e -- 1 6 10 -- -- -- -- -- -- --

%e 1 -- 5 9 -- -- -- -- -- -- --

%Y Cf. A086976.

%K nonn,more,hard,nice

%O 1,2

%A _N. J. A. Sloane_, Jul 24 2003, Jun 19 2007

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

%E 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.

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

%E a(11) corrected by _Paul Jungeblut_, Jul 09 2020