Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three

We consider the problem of enumerating the permutations containing exactly k occurrences of a pattern of length 3. This enumeration has received a lot of interest recently, and there are a lot of known results. This paper presents an alternative approach to the problem, which yields a proof for a formula which so far only was conjectured (by Noonan and Zeilberger). This approach is based on bijections from permutations to certain lattice paths with “jumps,” which were first considered by Krattenthaler.     

Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model

The limit laws of three cost measures are derived of two algorithms for finding the maximum in a single-channel broadcast communication model. Both algorithms use coin flips and comparisons. Besides the ubiquitous normal limit law, the Dickman distribution also appears in a natural way. The method of proof proceeds along the line via the method of moments and the “asymptotic transfers,” which roughly bridges the asymptotics of the “conquering cost of the subproblems” and that of the total cost. Such a general approach has proved very fruitful for a number of problems in the analysis of recursive algorithms.     

Influence diagnostics and outlier tests for varying coefficient mixed models

In this paper, we consider subset deletion diagnostics for fixed effects (coefficient functions), random effects and one variance component in varying coefficient mixed models (VCMMs). Some simple updated formulas are obtained, and based on which, Cook’s distance, joint influence and conditional influence are also investigated. Besides, since mean shift outlier models (MSOMs) are also efficient to detect outliers, we establish an equivalence between deletion models and MSOMs, which is not only suitable for fixed effects but also for random effects, and test statistics for outliers are then constructed. As a byproduct, we obtain the nonparametric “delete = replace” identity. Our influence diagnostics methods are illustrated through a simulated example and a real data set.     

Algorithmic Aspects of Tree Amalgamation

The amalgamation of leaf-labeled trees into a single (super)tree that “displays” each of the input trees is an important problem in classification. We discuss various approaches to this problem and show that a simple and well-known polynomial-time algorithm can be used to solve this problem whenever the input set of trees contains a minimum size subset that uniquely determines the supertree. Our results exploit a recently established combinatorial property concerning the structure of such collections of trees.     

Māl, enunciations, and the prehistory of Arabic algebra

Medieval Arabic algebra books intended for practical training generally have in common a first “book” which is divided into two sections: one on the methods of solving simplified equations and manipulating expressions, followed by one consisting of worked-out problems. By paying close attention to the wording of the problems in the books of al-Khwārizmī, Abū Kāmil, and Ibn Badr, we reveal the different ways the word māl was used. In the enunciation of a problem it is a common noun meaning “quantity,” while in the solution it is the proper noun naming the square of “thing” (shay '). We then look into the differences between the wording of enunciations and equations, which clarify certain problems solved without “thing,” and help explain the development of algebra before the time of al-Khwārizmī.     

Passage to the limit in Proposition I, Book I of Newton's Principia

The purpose of this paper is to analyze the way in which Newton uses his polygon model and passes to the limit in Proposition I, Book I of his Principia. It will be evident from his method that the limit of the polygon is indeed the orbital arc of the body and that his approximation of the actual continuous force situation by a series of impulses passes correctly in the limit into the continuous centripetal force situation. The analysis of the polygon model is done in two ways: (1) using the modern concepts of force, linear momentum, linear impulse, and velocity, and (2) using Newton's concepts of motive force and quantity of motion. It should be clearly understood that the term “force” without the adjective “motive,” is used in the modern sense, which is that force is a vector which is the time rate of change of the linear momentum. Newton did not use the word “force” in this modern sense. The symbol F denotes modern force. For Newton “force” was “motive force,” which is measured by the change in the quantity of motion of a body. Newton's “quantity of motion” is proportional to the magnitude of the modern vector momentum. Motive force is a scalar and the symbol F_m is used for motive force.     

Enumeration of Lozenge Tilings of Hexagons with Cut-Off Corners

Motivated by the enumeration of a class of plane partitions studied by Proctor and by considerations about symmetry classes of plane partitions, we consider the problem of enumerating lozenge tilings of a hexagon with “maximal staircases” removed from some of its vertices. The case of one vertex corresponds to Proctor's problem. For two vertices there are several cases to consider, and most of them lead to nice enumeration formulas. For three or more vertices there do not seem to exist nice product formulas in general, but in one special situation a lot of factorization occurs, and we pose the problem of finding a formula for the number of tilings in this case.     

Automata and logics over finitely varying functions

We extend some of the classical connections between automata and logic due to Büchi (1960) [5] and McNaughton and Papert (1971) [12] to languages of finitely varying functions or “signals”. In particular, we introduce a natural class of automata for generating finitely varying functions called ’s, and show that it coincides in terms of language definability with a natural monadic second-order logic interpreted over finitely varying functions Rabinovich (2002) [15]. We also identify a “counter-free” subclass of ’s which characterise the first-order definable languages of finitely varying functions. Our proofs mainly factor through the classical results for word languages. These results have applications in automata characterisations for continuously interpreted real-time logics like Metric Temporal Logic (MTL) Chevalier et al. (2006, 2007) [6] and [7].     

Tree decompositions of graphs: Saving memory in dynamic programming

We propose a simple and effective heuristic to save memory in dynamic programming on tree decompositions when solving graph optimization problems. The introduced “anchor technique” is based on a tree-like set covering problem. We substantiate our findings by experimental results. Our strategy has negligible computational overhead concerning running time but achieves memory savings for nice tree decompositions and path decompositions between 60% and 98%.     

Idempotent lattices, Renner monoids and cross section lattices of the special orthogonal algebraic monoids

Let MSO_n (n is even) be the special orthogonal algebraic monoid, T a maximal torus of the unit group, and the Zariski closure of T in the whole matrix monoid M_n. In this paper we explicitly determine the idempotent lattice , the Renner monoid , and the cross section lattice Λ of MSO_n in terms of the Weyl group and the concept of admissible sets (see Definition 3.1). It turns out that there is a one-to-one relationship between and the admissible subsets, and that is a submonoid of  , the Renner monoid M_n. Also Λ is a sublattice of Λ_n, the cross section lattice of M_n.     

The monopolist’s problem: existence, relaxation, and approximation

We study a variational problem arising from a generalization of an economic model introduced by Rochet and Choné in [5]. In this model a monopolist proposes a set Y of products with price list . Each rational consumer chooses which product to buy by solving a personal minimum problem, taking into account his/her tastes and economic possibilities. The monopolist looks for the optimal price list which minimizes costs, hence maximizes the profit. This leads to a minimum problem for functionals (the “pessimistic cost expectation”) and (the “optimistic cost expectation”), which are in turn defined through two nested variational problems. We prove that the minimum of exists and coincides with the infimum of . We also provide a variational approximation of by smooth functionals defined in finite dimensional Euclidean spaces.Received: 2 March 2004, Accepted: 19 October 2004, Published online: 22 December 2004Mathematics Subject Classification (2000): 49J45, 91B     

Uniqueness of Minimal Projections in Smooth Matrix Spaces

Let X=(M(n, m), ·), where · fulfills Condition 0.3 and W=M(n, 1)+M(1, m). A formula for a minimal projection from X onto W is given in (E. W. Cheney and W. A. Light, 1985, “Approximation Theory in Tensor Product Spaces,” Lecture Notes in Mathematics, Springer-Verlag, Berlin; E. J. Halton and W. A. Light, 1985, Math. Proc. Cambridge Philos. Soc.97, 127–136; and W. A. Light, 1986, Math. Z.191, 633–643). We will show that this projection is the unique minimal projection (see Theorem 2.1).     

Noncommutative algebras related with Schubert calculus on Coxeter groups

For any finite Coxeter system (W,S) we construct a certain noncommutative algebra, the so-called bracket algebra, together with a family of commuting elements, the so-called Dunkl elements. The Dunkl elements conjecturally generate an algebra which is canonically isomorphic to the coinvariant algebra of the Coxeter group W. We prove this conjecture for classical Coxeter groups and I₂(m). We define a “quantization” and a multiparameter deformation of our construction and show that for Lie groups of classical type and G₂, the algebra generated by Dunkl’s elements in the quantized bracket algebra is canonically isomorphic to the small quantum cohomology ring of the corresponding flag variety, as described by B. Kim. For crystallographic Coxeter systems we define the so-called quantum Bruhat representation of the corresponding bracket algebra. We study in more detail the structure of the relations in B_n-, D_n- and G₂-bracket algebras, and as an application, discover a Pieri-type formula in the B_n-bracket algebra. As a corollary, we obtain a Pieri-type formula for multiplication of an arbitrary B_n-Schubert class by some special ones. Our Pieri-type formula is a generalization of Pieri’s formulas obtained by A. Lascoux and M.-P. Schützenberger for flag varieties of type A. We also introduce a super-version of the bracket algebra together with a family of pairwise anticommutative elements, the so-called flat connections with constant coefficients, which describes “a noncommutative differential geometry on a finite Coxeter group” in the sense of S. Majid.     

The bidimensional interproximation problem and mixed splines

Interproximation methods for surfaces can be used to construct a smooth surface interpolating some data points and passing through specified regions. In this paper we study the use of mixed splines, that is smoothing splines with additional interpolation constraints, to solve the interproximation problem for surfaces in the case of scattered data. The solution is obtained by solving a linear system whose structure can be improved by using “bell-shaped” thin plate splines.     

The rate of convergence for the cyclic projections algorithm III: Regularity of convex sets

The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the “convex feasibility” problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the “angles” between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the “norm” of the product of the (nonlinear) metric projections onto related convex sets.In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the “linear regularity property” of Bauschke and Borwein, the “normal property” of Jameson (as well as Bakan, Deutsch, and Li’s generalization of Jameson’s normal property), the “strong conical hull intersection property” of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well.     

Nearly monotone and nearly convex approximation by smooth splines in ,

Given a monotone or convex function on a finite interval we construct splines of arbitrarily high order having maximum smoothness which are “nearly monotone” or “nearly convex” and provide the rate of -approximation which can be estimated in terms of the third or fourth (classical or Ditzian–Totik) moduli of smoothness (for uniformly spaced or Chebyshev knots). It is known that these estimates are impossible in terms of higher moduli and are no longer true for “purely monotone” and “purely convex” spline approximation.     

Cohomologies of the Poisson Superalgebra [Erratum]

In S. E. Konstein, A. G. Smirnov, and I. V. Tyutin “Cohomologies of the Poisson superalgebra” (Vol. 143, No. 2, May, 2005) on page 628, the second line in Theorem 1.3 should be: “and let .”The Editorial Board apologizes for this error.     

Newton's solution to the equiangular spiral problem and a new solution using only the equiangular property

This paper is a study of Proposition IX of Book I of Newton's Principia, the problem of determining the centripetal force for an equiangular spiral. In Newton's main proof of this proposition there is an error concerning his reason for the figure SPRQT being “given in kind,” and a very interesting technique of varying things in the neighborhood of a limit. This main proof utilized Newton's formula for the limit of SP²QT²/QR given in Corollary I to Proposition VI of the Principia. Newton also gave an alternate proof which utilized his formula for SY²PV given in Corollary III to Proposition VI. The “given” of Proposition IX was “a spiral PQS, cutting all the radii SP, SQ, &c., in a given angle.” Both the main proof and the alternate proof implicitly depend on the property of the equiangular spiral that the radius of curvature at any point is proportional to the pole distance SP. We here offer a new proof of Newton's proposition which does not depend on this implicit assumption.     

The invariant polynomials characterizing U(n) tensor operators p, q,…, q, 0,…, 0 having maximal null space

We make use of the “path sum” function to prove that the family of stretched operator functions characterized by the operator irrep labels p,q,…,q, 0,…, 0 satisfy a pair of general difference equations. This family of functions is a generalization of Milne's p,q,…,q, 0, functions for U(n) and Biedenharn and Louck's p,q, 0 functions for U(3). The fact that this family of stretched operator functions are polynomials follows from a detailed study of their symmetries and zeros. As a further application of our general difference equations and symmetry properties we give an explicit formula for the polynomials characterized by the operator irrep labels p, 1, 0,…, 0.