Colorings of the space ℝn with several forbidden distances

The paper is concerned with the classical problem concerning the chromatic number of a metric space, i.e., the minimal number of colors required to color all points in the space so that the distance (the value of the metric) between points of the same color does not belong to a given set of positive real numbers (the set of forbidden distances). New bounds for the chromatic number are obtained for the case in which the space is ?ⁿ with a metric generated by some norm (in particular, l _p) and the set of forbidden distances either is finite or forms a lacunary sequence.     

A note on list edge and list total coloring of planar graphs without adjacent short cycles

LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl(G)=Δand the list total chromatic numberχl(G)=Δ+1.     

Transfinite Hausdorff dimension

Making extensive use of small transfinite topological dimension trind, we ascribe to every metric space X an ordinal number (or −1 or Ω) tHD(X), and we call it the transfinite Hausdorff dimension of X. This ordinal number shares many common features with Hausdorff dimension. It is monotone with respect to subspaces, it is invariant under bi-Lipschitz maps (but in general not under homeomorphisms), in fact like Hausdorff dimension, it does not increase under Lipschitz maps, and it also satisfies the intermediate dimension property (Theorem 2.7). The primary goal of transfinite Hausdorff dimension is to classify metric spaces with infinite Hausdorff dimension. Indeed, if tHD(X)?ω₀, then HD(X)=+∞. We prove that tHD(X)?ω₁ for every separable metric space X, and, as our main theorem, we show that for every ordinal number α<ω₁ there exists a compact metric space Xα (a subspace of the Hilbert space l₂) with tHD(Xα)=α and which is a topological Cantor set, thus of topological dimension 0. In our proof we develop a metric version of Smirnov topological spaces and we establish several properties of transfinite Hausdorff dimension, including its relations with classical Hausdorff dimension.     

List coloring of graphs having cycles of length divisible by a given number

Let G be a graph and χ_l(G) denote the list chromatic number of G. In this paper we prove that for every graph G for which the length of each cycle is divisible by l (l≥3), χ_l(G)≤3.     

Topological structure of Urysohn universal spaces

The main aim of the paper is to prove that every nonempty member P of the algebra of subsets of a nontrivial Urysohn space generated by all balls (open and closed) is an l₂-manifold of finite homotopy type. An algorithm of finding a polyhedron K such that P and K×l₂ are homeomorphic is presented. An alternative proof of the Uspenskij theorem [V.V. Uspenskij, The Urysohn universal metric space is homeomorphic to a Hilbert space, Topology Appl. 139 (2004) 145-149] is given.     

Extreme boundaries of convex bodies inl 2

Every uncountable complete separable metric space is homomorphic to the set of extreme points (in the weak topology) of a bounded closed convex body inl ₂.     

Separable complete ANR's admitting a group structure are Hilbert manifolds

Let X be a complete-metrizable, separable ANR. The following two facts are shown: (a) if X admits a topological group structure, then either this is a Lie group structure or X is an l₂-manifold; (b) If X is a closed convex set in a complete metric linear space, then X is either locally compact or homeomorphic to l₂.     

A note on the sequence spacel (p v )

In this paper, the linear isometry of the sequence space l(p_v) into itself is specified as the automorphism of l(p_v) onto itself, when (p_v) satisfies the conditions, (i) 0 < p_v? 1, (ii) 1 +d ? p_v ? p < ∞,q < q_v < 1+d/d,d > o When (p_v) satisfies condition (ii),l (p_v) andl (q_v) are proved to be perfect spaces in the sense of Kothe and Toeplitz. A similar result connecting linear isometry and automorphism has been noted in the case of a non-normable complete linear metric space whose conjugate space is also determined.     

List coloring of Cartesian products of graphs

A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χ_l(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χ_l(G) and χ_l(H). On the other hand, we prove that χ_l(G×H)?min{χ_l(G)+col(H),col(G)+χ_l(H)}-1 and construct examples of graphs G and H for which our bound is tight.     

Solution of the linear regression problem using matrix correction methods in the <Emphasis Type="Italic">l</Emphasis> <Subscript>1</Subscript> metric

The linear regression problem is considered as an improper interpolation problem. The metric l₁ is used to correct (approximate) all the initial data. A probabilistic justification of this metric in the case of the exponential noise distribution is given. The original improper interpolation problem is reduced to a set of a finite number of linear programming problems. The corresponding computational algorithms are implemented in MATLAB.     

Strongly non-embeddable metric spaces

Enflo (1969) [4] constructed a countable metric space that may not be uniformly embedded into any metric space of positive generalized roundness. Dranishnikov, Gong, Lafforgue and Yu (2002) [3] modified Enflo?s example to construct a locally finite metric space that may not be coarsely embedded into any Hilbert space. In this paper we meld these two examples into one simpler construction. The outcome is a locally finite metric space (Z,ζ) which is strongly non-embeddable in the sense that it may not be embedded uniformly or coarsely into any metric space of non-zero generalized roundness. Moreover, we show that both types of embedding may be obstructed by a common recursive principle. It follows from our construction that any metric space which is Lipschitz universal for all locally finite metric spaces may not be embedded uniformly or coarsely into any metric space of non-zero generalized roundness. Our construction is then adapted to show that the group Zω=ℵ_0⊕Z admits a Cayley graph which may not be coarsely embedded into any metric space of non-zero generalized roundness. Finally, for each p?0 and each locally finite metric space (Z,d), we prove the existence of a Lipschitz injection f:Z→?p.     

Metric tangent spaces to Euclidean spaces

We prove that the metric spaces pretangent to a finite-dimensional Euclidean or unitary space E are isometric to E. As a consequence of this result, we describe the metric pretangent spaces at the nonsingular points of smooth surfaces. It is also proved that there exist the spaces pretangent to the Hilbert space l ₂ , which are not isometric to it.     

Embedding into l ∞2 Is Easy, Embedding into l ∞3 Is?NP-Complete

We give a new algorithm for enumerating all possible embeddings of a metric space (i.e., the distances between every pair within a set of n points) into ℝ² Cartesian space preserving their l _∞ (or l ₁) metric distances. Its expected time is (i.e., within a poly-log of the size of the input) beating the previous algorithm. In contrast, we prove that detecting l _∞³ embeddings is NP-complete. The problem is also NP-complete within l ₁² or l _∞² with the added constraint that the locations of two of the points are given or alternatively that the two dimensions are curved into a three-dimensional sphere. We also refute a compaction theorem by giving a metric space that cannot be embedded in l _∞³; however, it can be embedded if any single point is removed. This research is partially supported by NSERC grants. I would like to thank Steven Watson for his extensive help on this paper.     

On the metrizability of cone metric spaces

We have shown in this paper that a (complete) cone metric space (X,E,P,d) is indeed (completely) metrizable for a suitable metric D. Moreover, given any finite number of contractions f₁,…,fn on the cone metric space (X,E,P,d), D can be defined in such a way that these functions become also contractions on (X,D).     

Banach spaces whose duals are isomorphic to l1(Γ)

Banach spaces X whose duals are isomorphic or isometric to l₁(Γ) are characterized by certain classes of operators on X. It is proved that a separable, conjugate space isomorphic to a complemented subspace of an L₁(S, Σ, μ) space is isomorphic to l₁; a $\text{L}$₁ space contained in a separable, conjugate space is isomorphic to a subspace of l₁.     

The Harmonious Chromatic Number of Deep and Wide Complete n- ary Trees

The harmonious chromatic number of a graph G is the least number of colors which can be used to color V(G) such that adjacent vertices are colored differently and no two edges have the same color pair on their vertices. Unsolved Problem 17.5 of Graph Coloring Problems by Jensen and Toft asks for the harmonious chromatic number of T_m,n the complete n-ary tree on m levels. Let q be the number of edged of T_m,n and k be the smallest positive integer such that the binomial coefficient C(k, 2) ≥ q. We show that for all sufficiently large m, n, the harmonious chromatic number of T_m,n is at most k + 1, and that many such T_m,n have harmonious chromatic number k.     

Trees,tight extensions of metric spaces,and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces

The concept of tight extensions of a metric space is introduced, the existence of an essentially unique maximal tight extension T_x—the “tight span,” being an abstract analogon of the convex hull—is established for any given metric space X and its properties are studied. Applications with respect to (1) the existence of embeddings of a metric space into trees, (2) optimal graphs realizing a metric space, and (3) the cohomological dimension of groups with specific length functions are discussed.     

Incidence coloring of the squares of some graphs

The incidence chromatic number of G, denoted by χ_i(G), is the least number of colors such that G has an incidence coloring. In this paper, we determine the incidence chromatic number of the powers of paths, trees, which are min{n,2k+1}, and Δ(T²)+1, respectively. For the square of a Halin graph, we give an upper bound of its incidence chromatic number.     

Hajós' graph-coloring conjecture: Variations and counterexamples

For each integer n ≥ 7, we exhibit graphs of chromatic number n that contain no subdivided K_n as a subgraph. However, we show that a graph with chromatic number 4 contains as a subgraph a subdivided K₄ in which each triangle of the K₄ is subdivided to form an odd cycle.     

The space of maps from a locally compact space to a Banach space

The space of continuous maps from a topological spaceX to topological spaceY is denoted byC(X,Y) with the compact-open topology. In this paper we prove thatC(X,Y) is an absolute retract ifX is a locally compact separable metric space andY a convex set in a Banach space. From the above fact we know thatC(X,Y) is homomorphic to Hilbert spacel ₂ ifX is a locally compact separable metric space andY a separable Banach space; in particular,C(R ⁿ,R^m) is homomorphic to Hilbert spacel ₂. This research is supported by the Science Foundation of Shanxi Province's Scientific Committee