Kepler, Kugeln, Cluster, Katastrophen

Zusammenfassung. Dieser Überblick skizziert Theorie und Anwendungen von Kugelpackungen, ausgehend von den klassischen Problemen von Kepler und Newton. Der weitaus wichtigste Bereich der regelmäßigen, gitterförmigen Kugelpackungen einschließlich der Anwendungen auf Codes wird kurz gehalten, weil es dazu ausgiebig Literatur gibt. Dagegen wird ausführlicher auf die in den letzten Jahren stark entwickelten endlichen Kugelpackungen eingegangen, die gute Modelle für die in der Nanotechnik wichtigen Microcluster sind. In jeder der relativ knapp gehaltenen Sektionen wird das zum Verständnis Unerlässliche an Theorie angegeben, sowie mindestens ein überraschendes oder im Wortsinn merkwürdiges Phänomen. Außerdem wird auf weiterführende Literatur verwiesen. Für Einsteiger sei insbesondere M. Leppmeiers Buch [L] empfohlen.     

A three-stage, VSVO, Hermite-Birkhoff-Taylor, ODE solver

The new variable-step, variable-order, ODE solver, HBT(p) of order p, presented in this paper, combines a three-stage Runge-Kutta method of order 3 with a Taylor series method of order p-2 to solve initial value problems , where y:R→R^d and f:R×R^d→R^d. The order conditions satisfied by HBT(p) are formulated and they lead to Vandermonde-type linear algebraic systems whose solutions are the coefficients in the formulae for HBT(p). A detailed formulation of variable-step HBT(p) in both fixed-order and variable-order modes is presented. The new method and the Taylor series method have similar regions of absolute stability. To obtain high-accuracy results at high order, this method has been implemented in multiple precision.     

Segments,rectangles, contours

Two sets H and V of horizontal and vertical segments, respectively, determine a subdivision M of the plane into regions. A nontrivial region is one whose boundary contains an end-portion of nonzero length of at least one segment, and the nontrivial contour of M is the collection of boundaries of nontrivial regions. In this paper we consider several problems pertaining to H and V, such as the construction of the nontrivial contour of M, of the external contour of M, and of a path between two points in the plane avoiding the segments (route-in-a-maze). We show that, if |H| + |V| = n, all of these problems are solved in time O(n log n), by making use of a static data structure, called the adjacency map, which can be searched in time O(log n) and can be constructed in time O(n log n). The algorithms for the nontrivial and external contour are shown to be optimal.     

A Remark on Bernstein,Prokhorov, Bennett,Hoeffding, and Talagrand Inequalities

Let X ₁,..., X_n be independent random variables such that {X_j 1}=1 and E X _j=0 for all j. We prove an upper bound for the tail probabilities of the sum M _n=X₁+...+ X_n. Namely, we prove the inequality {M _nx} 3.7 {S_n x}, where S _n=₁+...+ _n is a sum of centered independent identically distributed Bernoulli random variables such that E S _n ² =ME M _n ² and {_k=1}=E S _n ² /(n+E S _n ² ) for all k (we call a random variable Bernoulli if it assumes at most two values). The inequality holds for x at which the survival function x{S _nx} has a jump down. For remaining x, the inequality still holds provided that we interpolate the function between the adjacent jump points linearly or log-linearly. If necessary, in order to estimate {S _nx} one can use special bounds for binomial probabilities. Up to the factor at most 2.375, the inequality is final. The inequality improves the classical Bernstein, Prokhorov, Bennett, Hoeffding, Talagrand, and other bounds.     

Benchmarking curriculum-based course timetabling: formulations,data formats,instances, validation,visualization, and results

We propose a set of formulations for the Curriculum-Based Course Timetabling problem, with the aim of “capturing” many real-world formulations, and thus encouraging researchers to “reduce” their specific problems to one of them, gaining the opportunity to compare and assess their results. This work is accompanied by a web application that maintains all the necessary infrastructures for benchmarking: validators, data formats, instances, reference scores, lower bounds, solutions, and visualizers. All instances proposed here are based on real data from various universities and they represent a variety of possible situations.     

Woodhouse, babbage, peacock, and modern Algebra

In a recent article, J. M. Dubbey [Historia Mathematica 4 (1977), 295–302] showed that George Peacock's A Treatise on Algebra (1830) was similar to an unpublished work written by Charles Babbage in 1821. Evidently perplexed about the absence of a dispute over priority, Dubbey concluded that Peacock had unconsciously assimilated Babbage's ideas, and that Babbage was too busy with other activities to be concerned. The thesis of this article is that the innovative aspects of the work of both Babbage and Peacock are extensions of ideas put forth in 1803 by Robert Woodhouse, and that probably neither Babbage nor Peacock was overly concerned with acknowledgments because their approach to algebra was not unique at Cambridge.     

Entropy,Universal Coding,Approximation, and Bases Properties

We shall present here results concerning the metric entropy of spaces of linear and nonlinear approximation under very general conditions. Our first result computes the metric entropy of the linear and m-terms approximation classes according to a quasi-greedy basis verifying the Temlyakov property. This theorem shows that the second index r is not visible throughout the behavior of the metric entropy. However, metric entropy does discriminate between linear and nonlinear approximation. Our second result extends and refines a result obtained in a Hilbertian framework by Donoho, proving that under orthosymmetry conditions, m-terms approximation classes are characterized by the metric entropy. Since these theorems are given under the general context of quasi-greedy bases verifying the Temlyakov property, they have a large spectrum of applications. For instance, it is proved in the last section that they can be applied in the case of L _p norms for R ^d for 1 < p < \infty. We show that the lower bounds needed for this paper in fact follow from quite simple large deviation inequalities concerning hypergeometric or binomial distributions. To prove the upper bounds, we provide a very simple universal coding based on a thresholding-quantizing constructive procedure.     

Associative,Idempotent, Symmetric,and Order-preserving Operations on Chains

We characterize the associative, idempotent, symmetric, and order-preserving binary operations on (finite) chains in terms of properties of (the Hasse diagram of) their associated semilattice order. In particular, we prove that the number of associative, idempotent, symmetric, and order-preserving operations on an n-element chain is the n^th Catalan number.

     

Right-angularity, flag complexes, asphericity

The ??polyhedral product functor?? produces a space from a simplicial complex L and a collection of pairs of spaces, {(A(i), B(i))}, where i ranges over the vertex set of L. We give necessary and sufficient conditions for the resulting space to be aspherical. There are two similar constructions, each of which starts with a space X and a collection of subspaces, {X _i }, where ${i \in \{0,1. . . . , n\}}$ , and then produces a new space. We also give conditions for the results of these constructions to be aspherical. All three techniques can be used to produce examples of closed aspherical manifolds.     

Weyl modules, Demazure modules, KR-modules, crystals, fusion products and limit constructions

We study finite-dimensional representations of current algebras, loop algebras and their quantized versions. For the current algebra of a simple Lie algebra of type ADE, we show that Kirillov-Reshetikhin modules and Weyl modules are in fact all Demazure modules. As a consequence one obtains an elementary proof of the dimension formula for Weyl modules for the current and the loop algebra. Further, we show that the crystals of the Weyl and the Demazure module are the same up to some additional label zero arrows for the Weyl module.For the current algebra Cg of an arbitrary simple Lie algebra, the fusion product of Demazure modules of the same level turns out to be again a Demazure module. As an application we construct the Cg-module structure of the Kac-Moody algebra -module V(?Λ₀) as a semi-infinite fusion product of finite-dimensional Cg-modules.     

Permutations,periodicity, and chaos

Let f: I → I be a continuous function on a closed interval I. If there exists x?I which has period 3 with respect to f, then Li and Yorke [1] proved that f is chaotic in the sense that there are not only points x?I of arbitrarily large period, but also uncountably many points x?I which are not even asymptotically periodic with respect to f. By using only elementary combinatorial facts about permutations, it is shown that if there is a point x?I of period p with respect to f, where p is divisible by 3, 5, or 7, then f is chaotic. The proof is followed by a study of some related combinatorial problems in symmetric groups.     

Triangulated functors,homological functors,tilts, and lifts

 Let T be a triangulated category and let X be an object of T. This paper studies the questions: Does there exist a triangulated functor G : D(ℤ)  T with G(ℤ)≌X? Does there exist a triangulated functor H : T  D(ℤ) with h⁰ ⊚ H ⋍ Hom_T (X, −)? To what extent are G and H unique? One spin off is a proof that the homotopy category of spectra is not the stable category of any Frobenius category with set indexed coproducts. Received: 8 March 2002 / Revised version: 18 October 2002 Published online: 14 February 2003 Mathematics Subject Classification (2000): 18E30, 55U35     

Instability,complexity, and evolution

In this paper, we consider a new class of random dynamical systems that contains, in particular, neural networks and complicated circuits. For these systems, we consider the viability problem: we suppose that the system survives only the system state is in a prescribed domain Π of the phase space. The approach developed here is based on some fundamental ideas proposed by A. Kolmogorov, R. Thom, M. Gromov, L. Valiant, L. Van Valen, and others. Under some conditions it is shown that almost all systems from this class with fixed parameters are unstable in the following sense: the probability P _t to leave Π within the time interval [0, t] tends to 1 as t → ∞. However, it is allowed to change these parameters sometimes (“evolutionary” case), then it may happen that P _t  < 1 − δ  < 1 for all t (“stable evolution”). Furthermore, we study the properties of such a stable evolution assuming that the system parameters are encoded by a dicsrete code. This allows us to apply complexity theory, coding, algorithms, etc. Evolution is a Markov process of modification of this code. Under some conditions we show that the stable evolution of unstable systems possesses the following general fundamental property: the relative Kolmogorov complexity of the code cannot be bounded by a constant as t → ∞. For circuit models, we define complexity characteristics of these circuits. We find that these complexities also have a tendency to increase during stable evolution. We give concrete examples of stable evolution. Bibliography: 80 titles. To the memory of A. N. Livshitz Published in Zapiski Nauchnykh Seminarov POMI, Vol. 360, 2008, pp. 31–69.     

Diameter,width, closest line pair,and parametric searching

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, anO(n ^1+ε) algorithm for computing the diameter of a point set in 3-space, anO(^8/5+ε) algorithm for computing the width of such a set, and onO(n ^8/5+ε) algorithm for computing the closest pair in a set ofn lines in space. All these algorithms are deterministic. Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

A bijection for triangulations, quadrangulations, pentagulations, etc.

A d-angulation is a planar map with faces of degree d. We present for each integer d?3 a bijection between the class of d-angulations of girth d (i.e., with no cycle of length less than d) and a class of decorated plane trees. Each of the bijections is obtained by specializing a “master bijection” which extends an earlier construction of the first author. Our construction unifies known bijections by Fusy, Poulalhon and Schaeffer for triangulations (d=3) and by Schaeffer for quadrangulations (d=4). For d?5, both the bijections and the enumerative results are new.We also extend our bijections so as to enumerate p-gonal d-angulations (d-angulations with a simple boundary of length p) of girth d. We thereby recover bijectively the results of Brown for simple p-gonal triangulations and simple 2p-gonal quadrangulations and establish new results for d?5.A key ingredient in our proofs is a class of orientations characterizing d-angulations of girth d. Earlier results by Schnyder and by De Fraysseix and Ossona de Mendez showed that simple triangulations and simple quadrangulations are characterized by the existence of orientations having respectively indegree 3 and 2 at each inner vertex. We extend this characterization by showing that a d-angulation has girth d if and only if the graph obtained by duplicating each edge d−2 times admits an orientation having indegree d at each inner vertex.