Steiner trees for fixed orientation metrics

We consider the problem of constructing Steiner minimum trees for a metric defined by a polygonal unit circle (corresponding to σ ≥ 2 weighted legal orientations in the plane). A linear-time algorithm to enumerate all angle configurations for degree three Steiner points is given. We provide a simple proof that the angle configuration for a Steiner point extends to all Steiner points in a full Steiner minimum tree, such that at most six orientations suffice for edges in a full Steiner minimum tree. We show that the concept of canonical forms originally introduced for the uniform orientation metric generalises to the fixed orientation metric. Finally, we give an O(σ n) time algorithm to compute a Steiner minimum tree for a given full Steiner topology with n terminal leaves.     

Compactness and the axiom of choice

In the absence of the axiom of choice four versions of compactness (A-, B-, C-, and D-compactness) are investigated. Typical results:

1. C-compact spaces form the epireflective hull in Haus of A-compact completely regular spaces.
2. Equivalent are:
3. the axiom of choice,
4. A-compactness = D-compactness,
5. B-compactness = D-compactness,
6. C-compactness = D-compactness and complete regularity,
7. products of spaces with finite topologies are A-compact,
8. products of A-compact spaces are A-compact,
9. products of D-compact spaces are D-compact,
10. powers X ^k of 2-point discrete spaces are D-compact,
11. finite products of D-compact spaces are D-compact,
12. finite coproducts of D-compact spaces are D-compact,
13. D-compact Hausdorff spaces form an epireflective subcategory of Haus,
14. spaces with finite topologies are D-compact.

1. Equivalent are:
2. the Boolean prime ideal theorem,
3. A-compactness = B-compactness,
4. A-compactness and complete regularity = C-compactness,
5. products of spaces with finite underlying sets are A-compact,
6. products of A-compact Hausdorff spaces are A-compact,
7. powers X ^k of 2-point discrete spaces are A-compact,
8. A-compact Hausdorff spaces form an epireflective subcategory of Haus.

1. Equivalent are:
2. either the axiom of choice holds or every ultrafilter is fixed,
3. products of B-compact spaces are B-compact.

1. Equivalent are:
2. Dedekind-finite sets are finite,
3. every set carries some D-compact Hausdorff topology,
4. every T ₁-space has a T ₁-D-compactification,
5. Alexandroff-compactifications of discrete spaces and D-compact.

     

Steiner minimal trees on sets of four points

LetS = {A, B, C, D} consist of the four corner points of a convex quadrilateral where diagonals [A, C] and [B, D] intersect at the pointO. There are two possible full Steiner trees forS, theAB-CD tree hasA andB adjacent to one Steiner point, andC andD to another; theAD-BC tree hasA andD adjacent to one Steiner point, andB andC to another. Pollak proved that if both full Steiner trees exist, then theAB-CD (AD-BC) tree is the Steiner minimal tree if AOD>3 (<) 90°, and both are Steiner minimal trees if AOD=90°. While the theorem has been crucially used in obtaining results on Steiner minimal trees in general, its applicability is sometimes restricted because of the condition that both full Steiner trees must exist. In this paper we remove this obstacle by showing: (i) Necessary and sufficient conditions for the existence of either full Steiner tree forS. (ii) If AOD90°, then theAB-CD tree is the SMT even if theAD-BC tree does not exist. (iii) If AOD<90° but theAD-BC tree does not exist, then theAB-CD tree cannot be ruled out as a Steiner minimal tree, though under certain broad conditions it can.     

Einstein structures: Existence versus uniqueness

Two well-known questions in differential geometry are “Does every compact manifold of dimension greater than four admit an Einstein metric?” and “Does an Einstein metric of a negative scalar curvature exist on a sphere?” We demonstrate that these questions are related: For everyn≥5 the existence of metrics for which the deviation from being Einstein is arbitrarily small on every compact manifold of dimensionn (or even on every smooth homology sphere of dimensionn) implies the existence of metrics of negative Ricci curvature on the sphereS ⁿ for which the deviation from being Einstein is arbitrarily small. Furthermore, assuming either a version of the Palais-Smale condition or the plausible looking existence of an algorithm deciding when a given metric on a compact manifold is close to an Einstein metric, we show for anyn≥5 that: 1) If everyn-dimensional smooth homology sphere admits an Einstein metric thenS ⁿ admits infinitely many Einstein structures of volume one and of negative scalar curvature; 2) If every compactn-dimensional manifold admits an Einstein metric then every compactn-dimensional manifold admits infinitely many distinct Einstein structures of volume one and of negative scalar curvature.     

Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem

We introduce a randomized iterative fragmentation procedure for finite metric spaces, which is guaranteed to result in a polynomially large subset that is D-equivalent to an ultrametric, where D ∈ (2,∞) is a prescribed target distortion. Since this procedure works for D arbitrarily close to the nonlinear Dvoretzky phase transition at distortion 2, we thus obtain a much simpler probabilistic proof of the main result of [3], answering a question from [12], and yielding the best known bounds in the nonlinear Dvoretzky theorem. Our method utilizes a sequence of random scales at which a given metric space is fragmented. As in many previous randomized arguments in embedding theory, these scales are chosen irrespective of the geometry of the metric space in question. We show that our bounds are sharp if one utilizes such a “scale-oblivious” fragmentation procedure.     

Multiparametric demand transportation problem

In some applications a minimum cost transportation model arises where supplies are fixed while demands may simultaneously vary. In this paper we analyse the structure of such a model and propose several techniques to describe its behaviour. Our approach is founded on the concept of optimal region, i.e., the subset of demand vectors where a given basic tree is optimal. The proposed algorithm consists in different pivoting strategies designed to:

• 1.build up a minimal list of basic trees such that the associated optimal regions cover the set of feasible demand vectors;
• 2.analyse the effects of either opening a new supplier or closing an existing one;
• 3.suitably treat the dual degenerate case by building up a minimal representation of every maximal region where the optimal value is linear in the demand vector.

Computational complexity is discussed and numerical examples are given.     

Convergence theorems, best approximation and best proximity for set-valued dynamic systems of relatively quasi-asymptotic contractions in cone uniform spaces

In cone uniform spaces X, using the concept of the D-family of cone pseudodistances, the distance between two not necessarily convex or compact sets A and B in X is defined, the concepts of cyclic and noncyclic set-valued dynamic systems of D-relatively quasi-asymptotic contractions T:A∪B→2^A∪B are introduced and the best approximation and best proximity point theorems for such contractions are proved. Also conditions are given which guarantee that for each starting point each generalized sequence of iterations of these contractions (in particular, each dynamic process) converges and the limit is a best proximity point. Moreover, D-families are constructed, characterized and compared. The results are new for set-valued and single-valued dynamic systems in cone uniform, cone locally convex and cone metric spaces. Various examples illustrating ideas, methods, definitions and results are constructed.     

On Supersets of Wavelet Sets

Considering a single dyadic orthonormal wavelet ψ in L ²(?), it is still an open problem whether the support of $\widehat{\psi}$ always contains a wavelet set. As far as we know, the only result in this direction is that if the Fourier support of a wavelet function is “small” then it is either a wavelet set or a union of two wavelet sets. Without assuming that a set S is the Fourier support of a wavelet, we obtain some necessary conditions and some sufficient conditions for a “small” set S to contain a wavelet set. The main results, which are in terms of the relationship between two explicitly constructed subsets A and B of S and two subsets T ₂ and D ₂ of S intersecting itself exactly twice translationally and dilationally respectively, are (1) if $A\cup B\not\subseteq T_{2}\cap D_{2}$ then S does not contain a wavelet set; and (2) if A∪B?T ₂∩D ₂ then every wavelet subset of S must be in S?(A∪B) and if S?(A∪B) satisfies a “weak” condition then there exists a wavelet subset of S?(A∪B). In particular, if the set S?(A∪B) is of the right size then it must be a wavelet set.     

Order stars and stability theorems

This paper clears up to the following three conjectures:

1. The conjecture of Ehle [1] on theA-acceptability of Padé approximations toe ^z , which is true;
2. The conjecture of Nørsett [5] on the zeros of the “E-polynomial”, which is false;
3. The conjecture of Daniel and Moore [2] on the highest attainable order of certainA-stable multistep methods, which is true, generalizing the well-known Theorem of Dahlquist.

We further give necessary as well as sufficient conditions forA-stable (acceptable) rational approximations, bounds for the highest order of “restricted” Padé approximations and prove the non-existence ofA-acceptable restricted Padé approximations of order greater than 6. The method of proof, just looking at “order stars” and counting their “fingers”, is very natural and geometric and never uses very complicated formulas.     

Li–Yorke chaos in higher dimensions: a review

Li and Yorke not only introduced the term “chaos” along with a mathematically rigorous definition of what they meant by it, but also gave a condition for chaos in scalar difference equations, their equally famous “period three implies chaos” result. Generalizations of the Li and Yorke definition of chaos to difference equations in ? ⁿ are reviewed here as well as higher dimensional conditions ensuring its existence, specifically the “snap-back repeller” condition of Marotto and its counterpart for saddle points. In addition, further generalizations to mappings in Banach spaces and complete metric spaces are considered. These will be illustrated with various simple examples including an application to chaotic dynamics on the metric space (?  ⁿ , D) of fuzzy sets on the base space ? ⁿ .     

The Steiner ratio of several discrete metric spaces

Steiner's Problem is the “Problem of shortest connectivity”, that means, given a finite set of points in a metric space (X,ρ), search for a network interconnecting these points with minimal length. This shortest network must be a tree and is called a Steiner Minimal Tree (SMT). It may contain vertices different from the points which are to be connected. Such points are called Steiner points. If we do not allow Steiner points, that means, we only connect certain pairs of the given points, we get a tree which is called a Minimum Spanning Tree (MST). Steiner's Problem is very hard as well in combinatorial as in computational sense, but, on the other hand, the determination of an MST is simple. Consequently, we are interested in the greatest lower bound for the ratio between the lengths of these both trees:

which is called the Steiner ratio (of (X,ρ)). We look for estimates and exact values for the Steiner ratio in several discrete metric spaces. Particularly, we determine the Steiner ratio for spaces of words, and we estimate the Steiner ratio for specific graphs.     

Approximating the Minimum-Degree Steiner Tree to within One of Optimal

The problem of constructing a spanning tree for a graph G = (V, E) with n vertices whose maximal degree is the smallest among all spanning trees of G is considered. This problem is easily shown to be NP-hard. In the Steiner version of this problem, along with the input graph, a set of distinguished vertices D V is given. A minimum-degree Steiner tree is a tree of minimum degree which spans at least the set D. Iterative polynomial time approximation algorithms for the problems are given. The algorithms compute trees whose maximal degree is at most Δ* + 1, where Δ* is the degree of some optimal tree for the respective problems. Unless P = NP, this is the best bound achievable in polynomial time.     

Chip-firing via open covers

We investigate chip-firing with respect to open covers of discrete graphs and metric graphs. For the case of metric graphs we show that given an open cover and a sink q, stabilization of a divisor D is unique and that there is a distinguished configuration equivalent to D, which we call the critical configuration. Also, we show that given a double cover of the metric graph by stars, which is the continuous analogue of the sandpile model, the critical configurations are in bijection with reduced divisors. Passing to the discrete case, we interpret open covers of a graph as simplicial complexes on the vertex and observe that chip-firing with respect to a simplicial complex is equivalent to the model introduced by Paoletti [G. Paoletti. July 11 2007: Master in Physics at University of Milan, defending thesis “Abelian sandpile models and sampling of trees and forests”; supervisor: Prof. S. Caracciolo. http://pcteserver.mi.infn.it/caraccio/index.html]. We generalize this setup for directed graphs using weighted simplicial complexes on the vertex set and show that the fundamental results extend. In the undirected case we present a generalization of the Cori-Le Borgne algorithm for chip-firing models via open covers, giving an explicit bijection between the critical configurations and the spanning trees of a graph.(http://www.elsevier.com/locate/endm)     

A Note on Old Babylonian Computational Techniques

Analysis of the errors in two Old Babylonian “algebraic” problems shows

• •that the computations were performed on a device where additive contributions were no longer identifiable once they had entered the computation;
• •that this device must have been some kind of counting board or abacus where numbers were represented as collections of calculi;
• •that units and tens were represented in distinct ways, perhaps by means of different calculi.

© 2002 Elsevier Science (USA).Eine Analyse der Rechenfehler in zwei altbabylonischen “algebraischen” Aufgaben läßt mehrere Rückschlüsse auf ein Hilfsmittel zu, das zur Durchführung von Rechnungen benutzt worden sein kann:

• •Additive Beiträge waren nach ihrer Eintragung in die Rechnung nicht länger identifizierbar.
• •Das Gerät war eine Art Rechenbrett, auf welchem Zahlen als Haufen von Rechensteinen erschienen.
• •Einer und Zehner wurden in verschiedener Weise, evtl. mittels verschiedener Rechensteine repräsentiert.

© 2002 Elsevier Science (USA).MSC subject classification: 01A17.     

Symplectic geometry,minors and graph Laplacians

In my talk, I will present some works done in the nineties on Laplacians on graphs: from eigenvalue problems to inverse problem for resistor networks. I will focus on the motivations and the main results as well as on the main ideas:

• •A differential topology point of view on the minor relation: a nice stratification associated to a finite graph Γ whose strata are associated to the minors of Γ
• •“Discrete” (graphs) versus “continuous” (Riemannian manifolds)
• •Stability of spectra with respect to singular limits: a finite dimensional theory of operators with domains (Von Neumann theory).

The link with topology will appear in some results about my graph parameter μ, in particular the planarity and the linkless embedding properties.     

A greedy approximation algorithm for the group Steiner problem

In the group Steiner problem we are given an edge-weighted graph G=(V,E,w) and m subsets of vertices . Each subset g_i is called a group and the vertices in ?_ig_i are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group.We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, Approximation algorithms for directed Steiner problems, J. Algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant ε>0, our algorithm gives an approximation in polynomial time. Approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of in the approximation ratio, where |V| is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio of O(log(max_i|g_i|)·logm) provided by the LP based approaches.     

Stable n-pointed trees of projective lines

Stable n-pointed trees arise in a natural way if one tries to find moduli for totally degenerate curves: Let C be a totally degenerate stable curve of genus g ≥ 2 over a field k. This means that C is a connected projective curve of arithmetic genus g satisfyingo

1. (a) every irreducible component of C is a rational curve over κ.
2. (b) every singular point of C is a κ-rational ordinary double point.
3. (c) every nonsingular component L of C meets C−L in at least three points. It is always possible to find g singular points P₁,..., P_g on C such that the blow up C of C at P₁,..., P_g is a connected projective curve with the following properties:o
   1. (i) every irreducible component of C is isomorphic to P_k¹
   2. (ii) the components of C intersect in ordinary κ-rational double points
   3. (iii) the intersection graph of C is a tree.

The morphism φ : C → C is an isomorphism outside 2g regular points Q₁, Q₁′, Q_g, Q_g′ and identifies Q_i with Q_j′. is uniquely determined by the g pairs of regular κ-rational points (Q_i, Q_i′). A curve C satisfying (i)-(iii) together with n κ-rational regular points on it is called a n-pointed tree of projective lines. C is stable if on every component there are at least three points which are either singular or marked. The object of this paper is the classification of stable n-pointed trees. We prove in particular the existence of a fine moduli space B_n of stable n-pointed trees. The discussion above shows that there is a surjective map πB_2g → D_g of B_2g onto the closed subscheme D_g of the coarse moduli scheme M_g of stable curves of genus g corresponding to the totally degenerate curves. By the universal property of M_g, π is a (finite) morphism. π factors through B_2g = B_2g mod the action of the group of pair preserving permutations of 2g elements (a group of order 2^gg, isomorphic to a wreath product of S_g and ℤ/2ℤThe induced morphism π: B_2g → D_g is an isomorphism on the open subscheme of irreducible curves in D_g, but in general there may be nonequivalent choices of g singular points on a totally degenerated curve for the above construction, so π has nontrivial fibres. In particular, π is not the quotient map for a group action on B_2g. This leads to the idea of constructing a Teichmüller space for totally degenerate curves whose irreducible components are isomorphic to B_2g and on which a discontinuous group acts such that the quotient is precisely D_g; π will then be the restriction of this quotient map to a single irreducible component. This theory will be developped in a subsequent paper.In this paper we only consider stable n-pointed trees and their moduli theory. In 4 1 we introduce the abstract cross ratio of four points (not necessarily on the same projective line) and show that for a field κ the κ-valued points in the projective variety B_n of cross ratios are in 1 − 1 correspondence with the isomorphy classes of stable n-pointed trees of projective lines over κ. We also describe the structure of the subvarieties B(T, ψ) of stable n-pointed trees with fixed combinatorial type.We generalize our notion in 4 2 to stable n-pointed trees of projective lines over an arbitrary noetherian base scheme S and show how the cross ratios for the fibres fit together to morphisms on S. This section is closely related to [Kn], but it is more elementary since we deal with a special case.4 3 contains the main result of the paper: the canonical projection B_{n + 1} → B_n is the universal family of stable n-pointed trees. As a by-product of the proof we find that B_n is a smooth projective scheme of relative dimension 2n - 3 over ℤ. We also compare B_n to the fibre product B_n−1 × _Bn-2 B_{n − 1} and investigate the singularities of the latter.In 4 4 we prove that the Picard group of B_n is free of rank 2ⁿ⁻1−(n+1)−n(n−3)/2.We also give a method to compute the Betti numbers of the complex manifold B_n(ℂ).In 4 5 we compare B_n to the quotient Q_n: = ℙ_ssⁿ/PGL₂ of semi-stable points in ℙ₁ⁿ for the action of fractional linear transformations in every component. This orbit space has been studied in greater detail by several authors, see [GIT], [MS], [G]. It turns out that B_n is a blow-up of Q_n, and we describe the blow-up in several steps where at each stage the obtained space is interpreted as a solution to a certain moduli problem.