Lipschitz homeomorphisms of the Hilbert cube

We study the question whether the Hilbert cube Q is Lipschitz homogeneous. The answer depends on the metric of Q. For example, setting d(x,y)=sup_j|x_j-y_j|/j we obtain a Lipschitz homogeneous metric, but if the last j is replaced by j!, the answer is negative.     

Homology representations arising from the half cube

We construct a CW decomposition Cn of the n-dimensional half cube in a manner compatible with its structure as a polytope. For each 3?k?n, the complex Cn has a subcomplex Cn,k, which coincides with the clique complex of the half cube graph if k=4. The homology of Cn,k is concentrated in degree k−1 and furthermore, the (k−1)st Betti number of Cn,k is equal to the (k−2)nd Betti number of the complement of the k-equal real hyperplane arrangement. These Betti numbers, which also appear in theoretical computer science, numerical analysis and engineering, are the coefficients of a certain Pascal-like triangle (Sloane's sequence A119258). The Coxeter groups of type Dn act naturally on the complexes Cn,k, and thus on the associated homology groups.     

On Lipschitz extension from finite subsets

We prove that for every n ∈ ? there exists a metric space (X, d _X), an n-point subset S ? X, a Banach space (Z, \({\left\| \right\|_Z}\)) and a 1-Lipschitz function f: S → Z such that the Lipschitz constant of every function F: X → Z that extends f is at least a constant multiple of \(\sqrt {\log n} \). This improves a bound of Johnson and Lindenstrauss [JL84]. We also obtain the following quantitative counterpart to a classical extension theorem of Minty [Min70]. For every α ∈ (1/2, 1] and n ∈ ? there exists a metric space (X, d _X), an n-point subset S ? X and a function f: S → ?₂ that is α-Hölder with constant 1, yet the α-Hölder constant of any F: X → ?₂ that extends f satisfies \({\left\| F \right\|_{Lip\left( \alpha \right)}} > {\left( {\log n} \right)^{\frac{{2\alpha - 1}}{{4\alpha }}}} + {\left( {\frac{{\log n}}{{\log \log n}}} \right)^{{\alpha ^2} - \frac{1}{2}}}\). We formulate a conjecture whose positive solution would strengthen Ball’s nonlinear Maurey extension theorem [Bal92], serving as a far-reaching nonlinear version of a theorem of König, Retherford and Tomczak-Jaegermann [KRTJ80]. We explain how this conjecture would imply as special cases answers to longstanding open questions of Johnson and Lindenstrauss [JL84] and Kalton [Kal04].     

Homology representations arising from the half cube, II

In a previous work, we defined a family of subcomplexes of the n-dimensional half cube by removing the interiors of all half cube shaped faces of dimension at least k, and we proved that the reduced homology of such a subcomplex is concentrated in degree k−1. This homology module supports a natural action of the Coxeter group W(Dn) of type D. In this paper, we explicitly determine the characters (over C) of these homology representations, which turn out to be multiplicity free. Regarded as representations of the symmetric group Sn by restriction, the homology representations turn out to be direct sums of certain representations induced from parabolic subgroups. The latter representations of Sn agree (over C) with the representations of Sn on the (k−2)-nd homology of the complement of the k-equal real hyperplane arrangement.     

Lipschitz factorization through subsets of Hilbert space

The Euclidean distortion of a metric space, a measure of how well the metric space can be embedded into a Hilbert space, is currently an active interdisciplinary research topic. We study the corresponding notion for mappings instead of spaces, which is that of Lipschitz factorization through subsets of Hilbert space. The main theorems are two characterizations of when a mapping admits such a factorization, both of them inspired by results dealing with linear factorizations through Hilbert space. The first is a nonlinear version of a classical theorem of Kwapień in terms of “dominated” sequences of vectors, whereas the second is a duality result by means of a tensor-product approach.     

Factoring elementary groups of prime cube order into subsets

Let be a prime and let be the -fold direct product of the cyclic group of order . Rédei conjectured if is the direct product of subsets and , each of which contains the identity element of , then either or does not generate all of . The paper verifies Rédei's conjecture for .

     

Nonlinear and non-separable multiscale representations based on Lipschitz perturbation

In this Note, we present a new formalism for nonlinear and non-separable multiscale representations. The new formalism we propose brings about similarities between existing nonlinear multiscale representations and also allows us to alleviate the classical hypotheses made to prove the convergence of the multiscale representations.     

Simplicial Lipschitz optimization without the Lipschitz constant

In this paper we propose a new simplicial partition-based deterministic algorithm for global optimization of Lipschitz-continuous functions without requiring any knowledge of the Lipschitz constant. Our algorithm is motivated by the well-known Direct algorithm which evaluates the objective function on a set of points that tries to cover the most promising subregions of the feasible region. Almost all previous modifications of Direct algorithm use hyper-rectangular partitions. However, other types of partitions may be more suitable for some optimization problems. Simplicial partitions may be preferable when the initial feasible region is either already a simplex or may be covered by one or a manageable number of simplices. Therefore in this paper we propose and investigate simplicial versions of the partition-based algorithm. In the case of simplicial partitions, definition of potentially optimal subregion cannot be the same as in the rectangular version. In this paper we propose and investigate two definitions of potentially optimal simplices: one involves function values at the vertices of the simplex and another uses function value at the centroid of the simplex. We use experimental investigation to compare performance of the algorithms with different definitions of potentially optimal partitions. The experimental investigation shows, that proposed simplicial algorithm gives very competitive results to Direct algorithm using standard test problems and performs particularly well when the search space and the numbers of local and global optimizers may be reduced by taking into account symmetries of the objective function.     

Rainbow coloring the cube

We prove that for d ≥ 4, d ≠ 5, the edges of the d-dimensional cube can be colored by d colors so that all quadrangles have four distinct colors. © 1993 John Wiley & Sons, Inc.     

The multicriteria big cube small cube method

In this paper we propose the big cube small cube (BCSC) technique for multicriteria optimization problems. The output of our algorithm results in a set which consists of epsilon efficient solutions and which contains all efficient solutions.     

Proof of the squashed cube conjecture

We prove a conjecture of R. L. Graham and H. O. Pollak to the effect that every connected graph onn vertices has a distance-preserving embedding in “squashed cube” of dimensionn?1. This means that to each vertex of the graph a string ofn?1 symbols from the alphabet {0, 1, *} can be assigned in such a way that the length of the shortest path between two vertices is equal to the Hamming distance between the corresponding strings, with * being regarded as at distance zero from either 1 or 0. Our labelling thus provides an efficient addressing scheme for the loop-switching communications system proposed by J. R. Pierce.     

Duplicating the cube and functional equations

In the present paper we consider a system of equations (1), (2) introduced in [2] in connection with the ancient Greek problem of duplicating the cube. We prove also some results in the case of a restricted domain, namely, if y = 2x:.¹     

Concentration of measures supported on the cube

We prove a log-Sobolev inequality for a certain class of log-concave measures in high dimension. These are the probability measures supported on the unit cube [0, 1] ⁿ ? ? ⁿ whose density takes the form exp(?ψ), where the function ψ is assumed to be convex (but not strictly convex) with bounded pure second derivatives. Our argument relies on a transportation-cost inequality á la Talagrand.