I've calcuated U(4,13) = 11/6 (using Veit's notation) using CPLEX (industrial strength MIP) with the MIP that Veit suggested. It seems to be implicit in the above discussion that the optimal values of U(m,n) are all rational. Perhaps this seems obvious, but here's a proof (courtesy of David Moulton): For each of the 2^mn settings of the y[i,j] variables (i.e. y[i,j] = 1, if and only if x[i,j] > 0) we can find the optimal value by means of a linear program: maximize u subject to x[i,j] >= u for all i,j such that y[i,j] = 1, plus the column and row sums being the right value. All the coefficients of the resulting matrix are integers, so the vertices of the resulting polytope are rational. Can one put a good bound on the possible denominators? They all appear to be small. Victor On Mon, Jan 12, 2009 at 11:25 PM, Michael Reid <reid@gauss.math.ucf.edu> wrote:
several more values, to cover your table:
T(7, 8) = 5/112 ; 4 * 5/112 + 2 * 3/56 + 4 * 1/16 + 2 * 1/14 + 4 * 9/112 T(7, 9) = 5/125 ; 6 * 5/126 + 3 * 1/21 + 3 * 4/63 + 6 * 1/14 T(8, 9) = 1/24 ; 6 * 1/24 + 6 * 1/18 + 6 * 5/72
the latter two agree with your table; but the first gives an improvement. (no contradiction, since you only gave a lower bound.)
mike
Here are my lower bounds for U(m, n):
1 2 3 4 5 6 7 8 9 1 1 2 1 2 3 1 1 3 4 1 2 1 4 5 1 1 5/4 3/2 5 6 1 2 3 2 2 6 7 1 1 5/4 5/3 5/3 2 7 8 1 2 4/3 4 2 2 9/4 8 9 1 1 3 7/4 2 3 5/2 3 9
The entry in column 4 row 7 is the bound on U(4, 7), which in fact equals the optimum value that was the subject of previous posts ( U(m, n) = m n T (m, n) ). I suspect several of my bounds are optimal values. I'm happy to supply the partitions to anyone interested.
i've also "calculated" some values. recall that my T(m, n) is the maximum c such that there exists a partition of 1 with each part
= c , and which is a simultaneous refinement of 1/m + 1/m + ... + 1/m = 1 and of 1/n + 1/n + ... = 1/n = 1 .
i believe i have a valid proof for each of the values below. i also give one such partition for each; showing that it's a refinement is easy.
T(m, n) = 1/n if m divides n ; n * 1/n
T(2, 2n+1) = 1/(2(2n+1)) ; (4n+2) * 1/(2(2n+1))
T(3, 4) = 1/12 ; 12 * 1/12 T(3, 5) = 1/12 ; 4 * 1/12 + 2 * 1/10 + 4 * 7/60 T(3, 7) = 5/84 ; 4 * 5/84 + 6 * 1/14 + 4 * 1/12 T(3, 8) = 1/18 ; 6 * 1/18 + 6 * 5/72 + 2 * 1/8 T(3, 10) = 2/45 ; 6 * 2/45 + 6 * 1/18 + 2 * 1/10 T(3, 11) = 1/24 ; 8 * 1/24 + 2 * 1/22 + 8 * 13/264 + 2 * 1/11 T(3, 13) = 11/312 ; 8 * 11/312 + 2 * 1/26 + 8 * 1/24 + 4 * 1/13
T(4, 5) = 3/40 ; 4 * 3/40 + 2 * 1/10 + 4 * 1/8 T(4, 6) = 1/12 ; 12 * 1/12 T(4, 7) = 5/84 ; 6 * 5/84 + 2 * 1/14 + 6 * 1/12 T(4, 9) = 7/144 ; 8 * 7/144 + 2 * 1/18 + 8 * 1/16 T(4, 10) = 1/20 ; 20 * 1/20 T(4, 11) = 9/220 ; 10 * 9/220 + 2 * 1/22 + 10 * 1/20 T(4, 4n+2) = 1/(2(4n+2)) ; (8n+4) * 1/(2(4n+2))
T(5, 6) = 1/15 ; 6 * 1/15 + 6 * 1/10 T(5, 7) = 1/21 ; 3 * 1/21 + 6 * 1/15 + 6 * 8/105 T(5, 8) = 1/20 ; 4 * 1/20 + 4 * 3/40 + 4 * 1/8 T(5, 9) = 2/45 ; 6 * 2/45 + 6 * 1/15 + 3 * 1/9
T(6, 7) = 1/21 ; 12 * 1/21 + 6 * 1/14 T(6, 8) = 1/24 ; 24 * 1/24 T(6, 9) = 1/18 ; 18 * 1/18
these appear to agree with your lower bounds on the overlap.
mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun