On deformation of associative algebras and graph homology

Deformation theory of associative algebras and in particular of Poisson algebras is reviewed. The role of an “almost contraction” leading to a canonical solution of the corresponding Maurer–Cartan equation is noted. This role is reminiscent of the Homotopical Perturbation Lemma, with the infinitesimal deformation cocycle as “initiator.”Applied to star-products, we show how Moyal's formula can be obtained using such an almost contraction and conjecture that the “merger operation” provides a canonical solution at least in the case of linear Poisson structures.     

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.”     

Semi-parametric multivariate modelling when the marginals are the same

A model is developed for multivariate distributions which have nearly the same marginals, up to shift and scale. This model, based on “interpolation” of characteristic functions, gives a new notion of “correlation”. It allows straightforward nonparametric estimation of the common marginal distribution, which avoids the “curse of dimensionality” present when nonparametically estimating the full multivariate distribution. The method is illustrated with environmental monitoring network data, where multivariate modelling with common marginals is often appropriate.     

Exploiting structure in quantified formulas

We study the computational problem “find the value of the quantified formula obtained by quantifying the variables in a sum of terms.” The “sum” can be based on any commutative monoid, the “quantifiers” need only satisfy two simple conditions, and the variables can have any finite domain. This problem is a generalization of the problem “given a sum-of-products of terms, find the value of the sum” studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448–476]. A data structure called a “structure tree” is defined which displays information about “subproblems” that can be solved independently during the process of evaluating the formula. Some formulas have “good” structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By “generic algorithm,” we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of “local reductions” based on the “local replacement” of terms. Such local reductions “preserve formula structure” in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure.     

Claw-free graphs. III. Circular interval graphs

Construct a graph as follows. Take a circle, and a collection of intervals from it, no three of which have union the entire circle; take a finite set of points V from the circle; and make a graph with vertex set V in which two vertices are adjacent if they both belong to one of the intervals. Such graphs are “long circular interval graphs,” and they form an important subclass of the class of all claw-free graphs. In this paper we characterize them by excluded induced subgraphs. This is a step towards the main goal of this series, to find a structural characterization of all claw-free graphs.This paper also gives an analysis of the connected claw-free graphs G with a clique the deletion of which disconnects G into two parts both with at least two vertices.     

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.     

Euler's partition theorem and the combinatorics of ℓ-sequences

Euler's partition theorem states that the number of partitions of an integer N into odd parts is equal to the number of partitions of N in which the ratio of successive parts is greater than 1. It was shown by Bousquet-Mélou and Eriksson in [M. Bousquet-Mélou, K. Eriksson, Lecture hall partitions II, Ramanujan J. 1 (2) (1997) 165–185] that a similar result holds when “odd parts” is replaced by “parts that are sums of successive terms of an ℓ-sequence” and the ratio “1” is replaced by a root of the characteristic polynomial of the ℓ-sequence. This generalization of Euler's theorem is intrinsically different from the many others that have appeared, as it involves a family of partitions constrained by the ratio of successive parts.In this paper, we provide a surprisingly simple bijection for this result, a question suggested by Richard Stanley. In fact, we give a parametrized family of bijections, that include, as special cases, Sylvester's bijection and a bijection for the lecture hall theorem. We introduce Sylvester diagrams as a way to visualize these bijections and deduce their properties.In proving the bijections, we uncover the intrinsic role played by the combinatorics of ℓ-sequences and use this structure to give a combinatorial characterization of the partitions defined by the ratio constraint. Several open questions suggested by this work are described.     

An experimental comparison of four graph drawing algorithms

In this paper we present an extensive experimental study comparing four general-purpose graph drawing algorithms. The four algorithms take as input general graphs (with no restrictions whatsoever on connectivity, planarity, etc.) and construct orthogonal grid drawings, which are widely used in software and database visualization applications. The test data (available by anonymous ftp) are 11,582 graphs, ranging from 10 to 100 vertices, which have been generated from a core set of 112 graphs used in “real-life” software engineering and database applications. The experiments provide a detailed quantitative evaluation of the performance of the four algorithms, and show that they exhibit trade-offs between “aesthetic” properties (e.g., crossings, bends, edge length) and running time.     

The inverse problem for certain tree parameters

Let p be a graph parameter that assigns a positive integer value to every graph. The inverse problem for p asks for a graph within a prescribed class (here, we will only be concerned with trees), given the value of p. In this context, it is of interest to know whether such a graph can be found for all or at least almost all integer values of p. We will provide a very general setting for this type of problem over the set of all trees, describe some simple examples and finally consider the interesting parameter “number of subtrees”, where the problem can be reduced to some number-theoretic considerations. Specifically, we will prove that every positive integer, with only 34 exceptions, is the number of subtrees of some tree.     

Elements in accepting an explanation

This paper addresses the question of what criteria influenced the acceptance of two “explanations” by grade 5 students. The students accepted the use of deductive reasoning as explanatory, as well as using reasoning by analogy in their own explanations. The “explanations” can be interpreted as proofs by mathematical induction. The main weakness of mathematical induction as a form of explanation was the arbitrariness of the initial step. The induction step did not seem to trouble these students. Other elements in their acceptance of explanations were concreteness, familiarity, and opportunities for multiple interpretations.     

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ī.     

The perception of randomness

Psychologists have studied people's intuitive notions of randomness by two kinds of tasks: judgment tasks (e.g., “is this series like a coin?” or “which of these series is most like a coin?”), and production tasks (e.g., “produce a series like a coin”). People's notion of randomness is biased in that they see clumps or streaks in truly random series and expect more alternation, or shorter runs, than are there. Similarly, they produce series with higher than expected alternation rates. Production tasks are subject to other biases as well, resulting from various functional limitations. The subjectively ideal random sequence obeys “local representativeness”; namely, in short segments of it, it represents both the relative frequencies (e.g., for a coin, 50%–50%) and the irregularity (avoidance of runs and other patterns). The extent to which this bias is a handicap in the real world is addressed.     

Polynomial identity rings as rings of functions

We generalize the usual relationship between irreducible Zariski closed subsets of the affine space, their defining ideals, coordinate rings, and function fields, to a non-commutative setting, where “varieties” carry a PGL_n-action, regular and rational “functions” on them are matrix-valued, “coordinate rings” are prime polynomial identity algebras, and “function fields” are central simple algebras of degree n. In particular, a prime polynomial identity algebra of degree n is finitely generated if and only if it arises as the “coordinate ring” of a “variety” in this setting. For n=1 our definitions and results reduce to those of classical affine algebraic geometry.     

Formal and precise derivation of the Green functions for a simple potential

In formal scattering theory, the Green functions are obtained as solutions of a distributional equation. In this paper, we use the Sturm–Liouville theory to compute the Green functions within a rigorous mathematical theory. We shall show that both the Sturm–Liouville theory and the formal treatment yield the same Green functions. We shall also show how the analyticity of the Green functions as functions of the energy keeps track of the so-called “incoming” and “outgoing” boundary conditions.     

CDS simulation and pattern formation of phase separation

Several properties of the generation and evolution of phase separating patterns for binary material studied by CDS model are proposed. The main conclusions are (1) for alloys spinodal decomposition, the conceptions of “macro-pattern” and “micropattern” are posed by “black-and- white graph” and “gray-scale graph” respectively. We find that though the four forms of map f that represent the self-evolution of order parameter in a cell (lattice) are similar to each other in “macro-pattern”, there are evident differences in their micro-pattern, e.g., some different fine netted structures in the black domain and the white domain are found by the micro-pattern, so that distinct mechanical and physical behaviors shall be obtained. (2) If the two constitutions of block copolymers are not symmetric (i.e. r ≠ 0.5), a pattern called “grain-strip cross pattern” is discovered, in the 0.43 <r <0.45.     

Parameterized graph cleaning problems

We investigate the Induced Subgraph Isomorphism problem with non-standard parameterization, where the parameter is the difference |V(G)|−|V(H)| with H and G being the smaller and the larger input graph, respectively. Intuitively, we can interpret this problem as “cleaning” the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We show fixed-parameter tractability of the cases where both H and G are planar and H is 3-connected, or H is a tree and G is arbitrary. We also prove that the problem when H and G are both 3-connected planar graphs is NP-complete without parameterization.     

Line Insertions in Totally Positive Matrices

It is obvious that between any two rows (columns) of an m-by-n totally nonnegative matrix a new row (column) may be inserted to form an (m+1)-by-n (m-by-(n+1)) totally nonnegative matrix. The analogous question, in which “totally nonnegative” is replaced by “totally positive” arises, for example, in completion problems and in extension of collocation matrices, and its answer is not obvious. Here, the totally positive case is answered affirmatively, and in the process an analysis of totally positive linear systems, that may be of independent interest, is used.     

A general framework of compactly supported splines and wavelets

Let {V_k} be a nested sequence of closed subspaces that constitute a multiresolution analysis of L²( ). We characterize the family Φ = {φ} where each φ generates this multiresolution analysis such that the two-scale relation of φ is governed by a finite sequence. In particular, we identify the ε Φ that has minimum support. We also characterize the collection Ψ of functions η such that each η generates the orthogonal complementary subspaces W_k of V_k, . In particular, the minimally supported ψ ε Ψ is determined. Hence, the “B-spline” and “B-wavelet” pair (, ψ) provides the most economical and computational efficient “spline” representations and “wavelet” decompositions of L² functions from the “spline” spaces V_k and “wavelet” spaces W_k, k . A very general duality principle, which yields the dual bases of both {(·−j):j and {η(·−j):j } for any η ε Ψ by essentially interchanging the pair of two-scale sequences with the pair of decomposition sequences, is also established. For many filtering applications, it is very important to select a multiresolution for which both and ψ have linear phases. Hence, “non-symmetric” and ψ, such as the compactly supported orthogonal ones introduced by Daubechies, are sometimes undesirable for these applications. Conditions on linear-phase φ and ψ are established in this paper. In particular, even-order polynomial B-splines and B-wavelets φ_m and ψ_m have linear phases, but the odd-order B-wavelet only has generalized linear phases.