Mathematical snapshots from the computational geometry landscape.
Induced trees in triangle-free graphs.
A typical property of the symmetric differential quotient
Spanning trees with low crossing number
Note on bi-Lipschitz embeddings into normed spaces
Let , be metric spaces and an injective mapping. We put , and (the of the mapping ). We investigate the minimum dimension such that every -point metric space can be embedded into the space with a prescribed distortion . We obtain that this is possible for , where is a suitable absolute constant. This improves a result of Johnson, Lindenstrauss and Schechtman [JLS87] (with a simpler proof). Related results for embeddability into are obtained by a similar method.
Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces
Let , be metric spaces and an injective mapping. We put ; , , and (the of the mapping ). Some Ramsey-type questions for mappings of finite metric spaces with bounded distortion are studied; e.g., the following theorem is proved: Let be a finite metric space, and let , be given numbers. Then there exists a finite metric space , such that for every mapping ( arbitrary metric space) with one can find a mapping , such that both the mappings and have distortion at most ....
Approximate symmetric derivative and monotonicity
Extension of Lipschitz mappings on metric trees
Bi-Lipschitz embeddings into low-dimensional Euclidean spaces
Few colored cuts or cycles in edge colored graphs
Bounded-degree graphs have arbitrarily large geometric thickness.
Low-distortion embeddings of trees.
The -pebbling number is eventually linear in .
On stabbing triangles by lines in 3-space
We give an example of a set of points in such that, for any partition of into triples, there exists a line stabbing of the triangles determined by the triples.
Hercules versus Hidden Hydra Helper
L. Kirby and J. Paris introduced the Hercules and Hydra game on rooted trees as a natural example of an undecidable statement in Peano Arithmetic. One can show that Hercules has a “short” strategy (he wins in a primitively recursive number of moves) and also a “long” strategy (the finiteness of the game cannot be proved in Peano Arithmetic). We investigate the conflict of the “short” and “long” intentions (a problem suggested by J. Nešetřil). After each move of Hercules (trying to kill Hydra fast)...
NP-hardness results for intersection graphs
Hardness of embedding simplicial complexes in
Let be the following algorithmic problem: Given a finite simplicial complex of dimension at most , does there exist a (piecewise linear) embedding of into ? Known results easily imply polynomiality of (; the case is graph planarity) and of for all . We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that and are undecidable for each . Our main result is NP-hardness of and, more generally, of for all , with...
On polynomial time decidability of induced-minor-closed classes
Page 1