Leírás
In 1992, Bollobás and Meir showed that for any n points in the k-dimensional unit cube [0,1]^k, k >= 2, one can always find a tour x_1,...,x_n through these n points with |x_1 - x_2|^k + |x_2 - x_3|^k + ... + |x_n - x_1|^k <= c_k * k^(k/2), where |x - y| is the Euclidean distance between x and y, and c_k is an absolute constant depending only on k. Remarkably, this bound does not depend on n, the number of points. They further conjectured that the best possible constant for every k >= 2 is c_k = 2 and showed that it cannot be taken lower than that. The conjecture is only known to be true for k = 2 due to Newman. Recently, Balogh, Clemen and Dumitrescu revised the conjecture for k = 3 by showing that c_3 >= 4 * (2/3)^(3/2) > 2.17. The best currently known bounds are c_k <= 1.28 * 5.059^k and, for large k, c_k <= 2.65^k * (1 + o_k(1)).
In this talk, I will show that c_k <= min(6(k+1), 2e(k+2)), reducing the gap between the lower and upper bounds on c_k from exponential to linear. Moreover, I will give a sketch of a proof that the conjecture holds asymptotically, i.e. c_k = 2 + o_k(1). The main tool is a new generalization of the ball packing argument used in previous works.