login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A070214 Maximal number of occupied cells in all monotonic matrices of order n. 3
1, 2, 5, 8, 11, 14, 19, 23, 28, 32, 38, 43, 49, 55 (list; graph; refs; listen; history; text; internal format)
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.

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, Tripods do not pack densely

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 16 21:00 EST 2021. Contains 340213 sequences. (Running on oeis4.)