Search: id:A070214
Results 1-1 of 1 results found.

%I A070214
%S A070214 1,2,5,8,11,14,19,23,28,32,37,43,49,55
%N A070214 Maximal number of occupied cells in all monotonic matrices of order n.
%C A070214 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 A070214 the filled-in entries in each row are strictly increasing;
%C A070214 the filled-in entries in each column are strictly decreasing;
%C A070214 for two filled-in cells with same entry, the one further right is higher 
               (the positive slope condition).
%C A070214 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 A070214 Arc joining (I1, j1, k1) and (i2, j2, k2) if:
%C A070214 [rows increasing] i1 = i2 and ((j1 < j2 and k1 >= k2) or (j1 > j2 and 
               k1 <= k2))
%C A070214 [columns decreasing] j1 = j2 and ((i1 < i2 and k1 <= k2) or (i1 > i2 
               and k1 >= k2))
%C A070214 [one color per cell] i1 = i2 and j1 = j2 and k1 <> k2
%C A070214 [positive slope] k1 = k2 and i1 <> i2 and (j2 - j1) / (i2 - i1) > 0
%D A070214 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.
%D A070214 S. K. Stein and S. Szabo, Algebra and Tiling, MAA Carus Monograph 25, 
               1994, page 95.
%D A070214 Alexandre Tiskin, Tripods do not pack densely, Lecture Notes in Computer 
               Science, 1858 (2000), 272-280.
%D A070214 Alexandre Tiskin, Packing tripods: narrowing the density gap, Discrete 
               Math., 307 (2007), 1973-1981.
%H A070214 Alexandre Tiskin, <a href="http://www.dcs.warwick.ac.uk/~tiskin/pub/2000/
               tripods.ps">Tripods do not pack densely</a>
%H A070214 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               MonotonicMatrix.html">Monotonic Matrix</a>
%F A070214 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 A070214 Tiskin showed that a(n) = o(n^2).
%e A070214 a(3) >= 5 from this matrix:
%e A070214 2 - 3
%e A070214 - - 1
%e A070214 1 3 -
%e A070214 a(5) >= 11 from this matrix:
%e A070214 - - 4 - 5
%e A070214 4 - - 5 -
%e A070214 - - 1 2 3
%e A070214 3 5 - - -
%e A070214 1 2 - - -
%e A070214 Dean Hickerson found the following matrix, which improves the lower bound 
               for a(8) to 23: (This is now known to be optimal)
%e A070214 - - 2 - - 4 7 8
%e A070214 - - 1 7 8 - - -
%e A070214 7 8 - - - - - -
%e A070214 - 2 - 4 - - - 6
%e A070214 - 1 - - - 3 6 -
%e A070214 4 - - - 6 - - -
%e A070214 2 - - - 3 - - 5
%e A070214 1 - - 3 - - 5 -
%Y A070214 Cf. A086976.
%Y A070214 Sequence in context: A135677 A163516 A000093 this_sequence A031210 A102795 
               A162938
%Y A070214 Adjacent sequences: A070211 A070212 A070213 this_sequence A070215 A070216 
               A070217
%K A070214 nonn,nice
%O A070214 1,2
%A A070214 N. J. A. Sloane (njas(AT)research.att.com), Jul 24 2003, Jun 19 2007
%E A070214 a(1)-a(5) computed by K. Joy. a(6) = 14 was established by Szabo.
%E A070214 Jul 27, 2003 - Aug 23, 2003: Rob Pratt (Rob.Pratt(AT)sas.com) 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 A070214 Extended to a(14) from Tiskin (2007), who gives a(15) >= 61, a(16) >= 
               65.

Search completed in 0.001 seconds