Chip-Firing Games on Directed Graphs

We consider the following (solitary) game: each node of a directed graph contains a pile of chips. A move consists of selecting a node with at least as many chips as its outdegree, and sending one chip along each outgoing edge to its neighbors. We extend to directed graphs several results on the undirected version obtained earlier by the authors, P. Shor, and G. Tardos, and we discuss some new topics such as periodicity, reachability, and probabilistic aspects.Among the new results specifically concerning digraphs, we relate the length of the shortest period of an infinite game to the length of the longest terminating game, and also to the access time of random walks on the same graph. These questions involve a study of the Laplace operator for directed graphs. We show that for many graphs, in particular for undirected graphs, the problem whether a given position of the chips can be reached from the initial position is polynomial time solvable.Finally, we show how the basic properties of the probabilistic abacus can be derived from our results.     

A posteriori error analysis of round-off errors in the numerical solution of ordinary differential equations

We prove sharp, computable error estimates for the propagation of errors in the numerical solution of ordinary differential equations. The new estimates extend previous estimates of the influence of data errors and discretization errors with a new term accounting for the propagation of numerical round-off errors, showing that the accumulated round-off error is inversely proportional to the square root of the step size. As a consequence, the numeric precision eventually sets the limit for the pointwise computability of accurate solutions of any ODE. The theoretical results are supported by numerically computed solutions and error estimates for the Lorenz system and the van der Pol oscillator.     

Lower Bounds on the Size of Maximum Independent Sets and Matchings in Hypergraphs of Rank Three

In this paper, we study lower bounds on the size of a maximum independent set and a maximum matching in a hypergraph of rank three. The rank in a hypergraph is the size of a maximum edge in the hypergraph. A hypergraph is simple if no two edges contain exactly the same vertices. Let H be a hypergraph and let and be the size of a maximum independent set and a maximum matching, respectively, in H, where a set of vertices in H is independent (also called strongly independent in the literature) if no two vertices in the set belong to a common edge. Let H be a hypergraph of rank at most three and maximum degree at most three. We show that with equality if and only if H is the Fano plane. In fact, we show that if H is connected and different from the Fano plane, then and we characterize the hypergraphs achieving equality in this bound. Using this result, we show that that if H is a simple connected 3‐uniform hypergraph of order at least 8 and with maximum degree at most three, then and there is a connected 3‐uniform hypergraph H of order 19 achieving this lower bound. Finally, we show that if H is a connected hypergraph of rank at most three that is not a complete hypergraph on vertices, where denotes the maximum degree in H, then and this bound is asymptotically best possible. © 2012 Wiley Periodicals, Inc. J. Graph Theory     

The Cartan,Choquet and Kellogg properties for the fine topology on metric spaces

We prove the Cartan and Choquet properties for the fine topology on a complete metric space equipped with a doubling measure supporting a p-Poincaré inequality, 1 < p < ∞. We apply these key tools to establish a fine version of the Kellogg property, characterize finely continuous functions by means of quasicontinuous functions, and show that capacitary measures associated with Cheeger supersolutions are supported by the fine boundary of the set.     

A variational principle for adaptive approximation of ordinary differential equations

Summary A variational principle, inspired by optimal control, yields a simple derivation of an error representation, global error=local errorweight, for general approximation of functions of solutions to ordinary differential equations. This error representation is then approximated by a sum of computable error indicators, to obtain a useful global error indicator for adaptive mesh refinements. A uniqueness formulation is provided for desirable error representations of adaptive algorithms. Mathematics Subject Classification (2000):65L70, 65G50This work has been supported by the EU–TMR project HCL # ERBFMRXCT960033, the EU–TMR grant # ERBFMRX-CT98-0234 (Viscosity Solutions and their Applications), the Swedish Science Foundation, UdelaR and UdeM in Uruguay, the Swedish Network for Applied Mathematics, the Parallel and Scientific Computing Institute (PSCI) and the Swedish National Board for Industrial and Technical Development (NUTEK).     

Moser iteration for (quasi)minimizers on metric spaces

We study regularity properties of quasiminimizers of the p-Dirichlet integral on metric measure spaces. We adapt the Moser iteration technique to this setting and show that it can be applied without an underlying differential equation. However, we have been able to run the Moser iteration fully only for minimizers. We prove Caccioppoli inequalities and local boundedness properties for quasisub- and quasisuperminimizers. This is done in metric spaces equipped with a doubling measure and supporting a weak (1, p)-Poincaré inequality. The metric space is not required to be complete. We also provide an example which shows that the dilation constant from the weak Poincaré inequality is essential in the condition on the balls in the Harnack inequality. This fact seems to have been overlooked in the earlier literature on nonlinear potential theory on metric spaces.     

Multicriteria Semi-Obnoxious Network Location Problems (MSNLP) with Sum and Center Objectives

Locating a facility is often modeled as either the maxisum or the minisum problem, reflecting whether the facility is undesirable (obnoxious) or desirable. But many facilities are both desirable and undesirable at the same time, e.g., an airport. This can be modeled as a multicriteria network location problem, where some of the sum-objectives are maximized (push effect) and some of the sum-objectives are minimized (pull effect).We present a polynomial time algorithm for this model along with some basic theoretical results, and generalize the results also to incorporate maximin and minimax objectives. In fact, the method works for any piecewise linear objective functions. Finally, we present some computational results.     

Bier Spheres and Posets

In 1992 Thomas Bier presented a strikingly simple method to produce a huge number of simplicial (n – 2)-spheres on 2n vertices, as deleted joins of a simplicial complex on n vertices with its combinatorial Alexander dual. Here we interpret his construction as giving the poset of all the intervals in a boolean algebra that “cut across an ideal.” Thus we arrive at a substantial generalization of Bier’s construction: the Bier posets Bier(P, I) of an arbitrary bounded poset P of finite length. In the case of face posets of PL spheres this yields cellular “generalized Bier spheres.” In the case of Eulerian or Cohen–Macaulay posets P we show that the Bier posets Bier(P, I) inherit these properties. In the boolean case originally considered by Bier, we show that all the spheres produced by his construction are shellable, which yields “many shellable spheres,” most of which lack convex realization. Finally, we present simple explicit formulas for the g-vectors of these simplicial spheres and verify that they satisfy a strong form of the g-conjecture for spheres.     

CRYRING at the LSR at FLAIR

FLAIR will be the next-generation facility for physics with low-energy antiprotons, providing antiprotons at energies from tens of MeV down to rest. It will also offer unique possibilities for physics with highly charged ions at very low energies. The FLAIR facility will have two deceleration rings, the LSR which will decelerate antiprotons to 300 keV and the USR which will bring them down further to 20 keV. The LSR will consist of the present CRYRING at the Manne Siegbahn Laboratory. During the next few years, CRYRING will be modified with respect to injection and extraction, to allow injection of 30 MeV antiprotons and to provide it with both fast (single-turn) and slow (resonant) extraction at a variable energy. We here describe plans and preparations for the transfer of CRYRING to FLAIR, giving, in particular, an overview of new components for injection and extraction.