Constructing a spanning tree with many leaves

It was shown by Griggs and Wu that a graph of minimal degree 4 on n vertices has a spanning tree with at least \frac25 \frac{2}{5} n leaves, which is asymptomatically the best possible bound for this class of graphs. In this paper, we present a polynomial time algorithm that finds in any graph with k vertices of degree greater than or equal to 4 and k′ vertices of degree 3 a spanning tree with [ \frac25 ·k + \frac215 ·k￠ ] \left[ {\frac{2}{5} \cdot k + \frac{2}{{15}} \cdot k'} \right] leaves.     

Speeding up the Dreyfus–Wagner algorithm for minimum Steiner trees

The Dreyfus–Wagner algorithm is a well-known dynamic programming method for computing minimum Steiner trees in general weighted graphs in time O ^*(3 ^k ), where k is the number of terminal nodes to be connected. We improve its running time to O ^*(2.684 ^k ) by showing that the optimum Steiner tree T can be partitioned into T = T ₁∪ T ₂ ∪ T ₃ in a certain way such that each T _i is a minimum Steiner tree in a suitable contracted graph G _i with less than terminals. In the rectilinear case, there exists a variant of the dynamic programming method that runs in O ^*(2.386 ^k ). In this case, our splitting technique yields an improvement to O ^*(2.335 ^k ).     

Approximation algorithms for finding and partitioning unit-disk graphs into co-<Emphasis Type="Italic">k</Emphasis>-plexes

This article studies a degree-bounded generalization of independent sets called co-k-plexes. Constant factor approximation algorithms are developed for the maximum co-k-plex problem on unit-disk graphs. The related problem of minimum co-k-plex coloring that generalizes classical vertex coloring is also studied in the context of unit-disk graphs. We extend several classical approximation results for independent sets in UDGs to co-k-plexes, and settle a recent conjecture on the approximability of co-k-plex coloring in UDGs.     

On the cost of controlling unstable systems: The case of boundary controls

We discuss the cost of controlling parabolic equations of the formy _t + δ² y +kδy = 0 in a bounded smooth domain Ώ ofℝ ^d by means of a boundary control. More precisely, we are interested in the cost of controlling from zero initial state to a given final state (in a suitable approximate sense) at timeT > 0 and in the behavior of this cost ask → ∞. We introduce finite-dimensional Galerkin approximations and prove that they are exactly controllable. Moreover, we also prove that the cost of controlling converges exponentially to zero ask → ∞. This proves, roughly speaking, that when the system becomes more unstable it is easier to control. The system under consideration does not admit a variational formulation. Thus, in order to introduce its Galerkin approximation, we first approximate it by means of a singular perturbation. We also develop a method for the construction of special Galerkin bases well adapted to the control problem. Dedicated to John E. Lagnese on his 60th Birthday. Supported by project PB93-1203 of the DGICYT (Spain) and grant CHRX-CT94-0471 of the European Union.     

Absorbing Angles,Steiner Minimal Trees,and Antipodality

We give a new proof that a star {op _i :i=1,…,k} in a normed plane is a Steiner minimal tree of vertices {o,p ₁,…,p _k } if and only if all angles formed by the edges at o are absorbing (Swanepoel in Networks 36: 104–113, 2000). The proof is simpler and yet more conceptual than the original one. We also find a new sufficient condition for higher-dimensional normed spaces to share this characterization. In particular, a star {op _i :i=1,…,k} in any CL-space is a Steiner minimal tree of vertices {o,p ₁,…,p _k } if and only if all angles are absorbing, which in turn holds if and only if all distances between the normalizations \frac1||p_i||p_i\frac{1}{\Vert p_{i}\Vert}p_{i} equal 2. CL-spaces include the mixed ℓ ₁ and ℓ _∞ sum of finitely many copies of ℝ.     

A hybrid numerical-asymptotic boundary integral method for high-frequency acoustic scattering

We propose a new robust method for the computation of scattering of high-frequency acoustic plane waves by smooth convex objects in 2D. We formulate this problem by the direct boundary integral method, using the classical combined potential approach. By exploiting the known asymptotics of the solution, we devise particular expansions, valid in various zones of the boundary, which express the solution of the integral equation as a product of explicit oscillatory functions and more slowly varying unknown amplitudes. The amplitudes are approximated by polynomials (of minimum degree d) in each zone using a Galerkin scheme. We prove that the underlying bilinear form is continuous in L ₂, with a continuity constant that grows mildly in the wavenumber k. We also show that the bilinear form is uniformly L ₂-coercive, independent of k, for all k sufficiently large. (The latter result depends on rather delicate Fourier analysis and is restricted in 2D to circular domains, but it also applies to spheres in higher dimensions.) Using these results and the asymptotic expansion of the solution, we prove superalgebraic convergence of our numerical method as d → ∞ for fixed k. We also prove that, as k → ∞, d has to increase only very modestly to maintain a fixed error bound (d ∼ k ^1/9 is a typical behaviour). Numerical experiments show that the method suffers minimal loss of accuracy as k →∞, for a fixed number of degrees of freedom. Numerical solutions with a relative error of about 10⁻⁵ are obtained on domains of size for k up to 800 using about 60 degrees of freedom.     

Diophantinc approximation by linear forms on manifolds

The following Khintchine-type theorem is proved for manifoldsM embedded in ℝ ^k which satisfy some mild curvature conditions. The inequality |q·x| <Ψ(|q|) whereΨ(r) → 0 asr → ∞ has finitely or infinitely many solutionsqεℤ ^k for almost all (in induced measure) points x onM according as the sum Σ _r ^{= 1/∞} Ψ(r)r ^k−2 converges or diverges (the divergent case requires a slightly stronger curvature condition than the convergent case). Also, the Hausdorff dimension is obtained for the set (of induced measure 0) of point inM satisfying the inequality infinitely often whenψ(r) =r ^−t . τ >k − 1.     

An acyclic extension of the braid group

We relate Artin's braid groupB _℞=lim_→B_n to a certain groupF′ ofpl-homeomorphisms of the interval. Namely, there exists a short exact sequence 1→B _∞→A→F′→1 whereH _kA=0,k≥1.     

Generalization of the fricke theorem on entire functions of finite index

We prove that, for every sequence (a _k) of complex numbers satisfying the conditions Σ(1/|a _k |) < ∞ and |a _k+1| − |a _k | ↗ ∞ (k → ∞), there exists a continuous functionl decreasing to 0 on [0, + ∞] and such thatf(z) = Π(1 −z/|a _k |) is an entire function of finitel-index.     

Loop-Erased Random Walk on Finite Graphs and the Rayleigh Process

Let (G _n ) _n=1^∞ be a sequence of finite graphs, and let Y _t be the length of a loop-erased random walk on G _n after t steps. We show that for a large family of sequences of finite graphs, which includes the case in which G _n is the d-dimensional torus of size-length n for d≥4, the process (Y _t ) _t=0^∞, suitably normalized, converges to the Rayleigh process introduced by Evans, Pitman, and Winter. Our proof relies heavily on ideas of Peres and Revelle, who used loop-erased random walks to show that the uniform spanning tree on large finite graphs converges to the Brownian continuum random tree of Aldous. Supported in part by NSF Grant DMS-0504882.     

Hypergraphs with independent neighborhoods

For each k ≥ 2, let ρ _k ∈ (0, 1) be the largest number such that there exist k-uniform hypergraphs on n vertices with independent neighborhoods and (ρ _k + o(1))( _k ⁿ ) edges as n → ∞. We prove that ρ _k = 1 − 2logk/k + Θ(log log k/k) as k → ∞. This disproves a conjecture of Füredi and the last two authors.     

Approximations and Lower Bounds for the Length of Minimal Euclidean Steiner Trees

We give a new lower bound on the length of the minimal Steiner tree with a given topology joining given terminals in Euclidean space, in terms of toroidal images. The lower bound is equal to the length when the topology is full. We use the lower bound to prove bounds on the “error” e in the length of an approximate Steiner tree, in terms of the maximum deviation d of an interior angle of the tree from 120°. Such bounds are useful for validating algorithms computing minimal Steiner trees. In addition we give a number of examples illustrating features of the relationship between e and d, and make a conjecture which, if true, would somewhat strengthen our bounds on the error. J. H. Rubinstein, J. Weng: Research supported by the Australian Research Council N. Wormald: Research supported by the Australian Research Council and the Canada Research Chairs Program. Research partly carried out while the author was in the Department of Mathematics and Statistics, University of Melbourne     

Asymptotics for Two-Dimensional Atoms

We prove that the ground state energy of an atom confined to two dimensions with an infinitely heavy nucleus of charge Z > 0 and N quantum electrons of charge −1 is E(N,Z)=-\frac12Z²ln Z+(E^TF(l)+\frac12c^H)Z²+o(Z²){E(N,Z)=-\frac{1}{2}Z^2{\rm ln} Z+(E^{\rm TF}(\lambda)+\frac{1}{2}c^{\rm H})Z^2+o(Z^2)} when Z → ∞ and N/Z → λ, where E ^TF(λ) is given by a Thomas–Fermi type variational problem and c ^H ≈ −2.2339 is an explicit constant. We also show that the radius of a two-dimensional neutral atom is unbounded when Z → ∞, which is contrary to the expected behavior of three-dimensional atoms.     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.     

Numerical evaluation of Goursat’s infinite integral

The infinite integral ò₀^￥x dx/(1+x⁶sin²x)\int_0^{\infty}x\,dx/(1+x^6\sin^2x) converges but is hard to evaluate because the integrand f(x) = x/(1 + x ⁶sin² x) is a non-convergent and unbounded function, indeed f(kπ) = kπ→ ∞ (k→ ∞). We present an efficient method to evaluate the above integral in high accuracy and actually obtain an approximate value in up to 73 significant digits on an octuple precision system in C++.     

Approximation algorithms for a vehicle routing problem

In this paper we investigate a vehicle routing problem motivated by a real-world application in cooperation with the German Automobile Association (ADAC). The general task is to assign service requests to service units and to plan tours for the units such as to minimize the overall cost. The characteristics of this large-scale problem due to the data volume involve strict real-time requirements. We show that the problem of finding a feasible dispatch for service units starting at their current position and serving at most k requests is NP-complete for each fixed k ≥ 2. We also present a polynomial time (2k − 1)-approximation algorithm, where again k denotes the maximal number of requests served by a single service unit. For the boundary case when k equals the total number |E| of requests (and thus there are no limitations on the tour length), we provide a -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs.     

A 2 + ɛ approximation algorithm for the k-MST problem

For any ɛ > 0 we give a (2 + ɛ)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [10] the algorithm extends to a (2 + ɛ)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality. Research supported by NSF CAREER award NSF CCR-9502747, NSF grants CCR-0205594 and CCR-0098180, an Alfred Sloan Fellowship, and a Packard Fellowship. Research supported by an NSERC Discovery grant.     

Nonexistence of invariant graphs in all supercritical energy levels of mechanical Lagrangians in T 2

Let (T², g) be a smooth Riemannian structure in the torus T². We show that given ε > 0 and any C^∞ function U : T² → ℝ there exists a C¹ function U_ε with Lipschitz derivatives that is ε-C⁰ close to U for which there are no continuous invariant graphs in any supercritical energy level of the mechanical Lagrangian L_ε : TT² → ℝ given by . We also show that given n ∈ ℕ, the set of C^∞ potentials U : T² → ℝ for which there are no continuous invariant graphs in any supercritical energy level E ≤ n of is C⁰ dense in the set of C^∞ functions. Partially supported by CNPq, FAPERJ-Cientistas do nosso estado.     

Aperture-Angle and Hausdorff-Approximation of Convex Figures

The aperture angle α(x,Q) of a point x ∉ Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q⊂C is the minimum aperture angle of any x∈C∖Q with respect to Q. We show that for any compact convex set C in the plane and any k>2, there is an inscribed convex k-gon Q⊂C with aperture angle approximation error . This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance σ, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k>2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most  . This research was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-311-D00763). NICTA is funded through the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.     

On bounded solutions of abstract differential equations

Summary We construct nontrivial bounded solutions of an abstract evolution equationu'(t)=Au(t) (—∞<t<∞) whereA generates a (C ₀) semigroup of operators {T _t;t≥0} such thatT _t converges strongly to zero ast→∞.

---

Riassunto Si costruiscono soluzioni limitate non triviali di una equazioneu'(t)=Au(t) (—∞<t<∞) doveA è il generatore di un semigruppo di operatori {T _t;t≥0} tale cheT _t converge fortemente verso 0 pert→∞.

---

---

Supported by National Science Foundation grant GP-12722.