The curve selection lemma and the Morse-Sard theorem

We use an inequality due to Bochnak and Lojasiewicz, which follows from the Curve Selection Lemma of real algebraic geometry in order to prove that, given a C(r) function f : U subset of R(m) -> R, we have lim(y -> xy is an element of crit(f)) vertical bar f(y) - f(x)vertical bar/vertical bar y - x vertical bar(r) = 0, for all x is an element of crit(f)` boolean AND U, where crit( f) = {x is an element of U vertical bar df ( x) = 0}. This shows that the so-called Morse decomposition of the critical set, used in the classical proof of the Morse-Sard theorem, is not necessary: the conclusion of the Morse decomposition lemma holds for the whole critical set. We use this result to give a simple proof of the classical Morse-Sard theorem ( with sharp differentiability assumptions).

Invariant theory and reversible-equivariant vector fields

In this paper we present results for the systematic study of reversible-equivariant vector fields - namely, in the simultaneous presence of symmetries and reversing symmetries - by employing algebraic techniques from invariant theory for compact Lie groups. The Hilbert-Poincare series and their associated Molien formulae are introduced,and we prove the character formulae for the computation of dimensions of spaces of homogeneous anti-invariant polynomial functions and reversible-equivariant polynomial mappings. A symbolic algorithm is obtained for the computation of generators for the module of reversible-equivariant polynomial mappings over the ring of invariant polynomials. We show that this computation can be obtained directly from a well-known situation, namely from the generators of the ring of invariants and the module of the equivariants. (C) 2008 Elsevier B.V, All rights reserved.

Twofold adaptive partition of unity implicits

Partition of Unity Implicits (PUI) has been recently introduced for surface reconstruction from point clouds. In this work, we propose a PUI method that employs a set of well-observed solutions in order to produce geometrically pleasant results without requiring time consuming or mathematically overloaded computations. One feature of our technique is the use of multivariate orthogonal polynomials in the least-squares approximation, which allows the recursive refinement of the local fittings in terms of the degree of the polynomial. However, since the use of high-order approximations based only on the number of available points is not reliable, we introduce the concept of coverage domain. In addition, the method relies on the use of an algebraically defined triangulation to handle two important tasks in PUI: the spatial decomposition and an adaptive polygonization. As the spatial subdivision is based on tetrahedra, the generated mesh may present poorly-shaped triangles that are improved in this work by means a specific vertex displacement technique. Furthermore, we also address sharp features and raw data treatment. A further contribution is based on the PUI locality property that leads to an intuitive scheme for improving or repairing the surface by means of editing local functions.

Real map germs and higher open book structures

The paper focusses on the existence of higher open book structures defined by real map germs psi : (R(m), 0) -> (R(p), 0) such that Sing psi boolean AND psi(-1)(0) subset of {0}. A general existence criterion is proved, with view to weighted-homogeneous maps.

Conformal deformation of equilibrium measures in normal random ensembles

We investigate the eigenvalue statistics of ensembles of normal random matrices when their order N tends to infinite. In the model, the eigenvalues have uniform density within a region determined by a simple analytic polynomial curve. We study the conformal deformations of equilibrium measures of normal random ensembles to the real line and give sufficient conditions for it to weakly converge to a Wigner measure.

Opinion dynamics of learning agents: does seeking consensus lead to disagreement?

We study opinion dynamics in a population of interacting adaptive agents voting on a set of issues represented by vectors. We consider agents who can classify issues into one of two categories and can arrive at their opinions using an adaptive algorithm. Adaptation comes from learning and the information for the learning process comes from interacting with other neighboring agents and trying to change the internal state in order to concur with their opinions. The change in the internal state is driven by the information contained in the issue and in the opinion of the other agent. We present results in a simple yet rich context where each agent uses a Boolean perceptron to state their opinion. If the update occurs with information asynchronously exchanged among pairs of agents, then the typical case, if the number of issues is kept small, is the evolution into a society torn by the emergence of factions with extreme opposite beliefs. This occurs even when seeking consensus with agents with opposite opinions. If the number of issues is large, the dynamics becomes trapped, the society does not evolve into factions and a distribution of moderate opinions is observed. The synchronous case is technically simpler and is studied by formulating the problem in terms of differential equations that describe the evolution of order parameters that measure the consensus between pairs of agents. We show that for a large number of issues and unidirectional information flow, global consensus is a fixed point; however, the approach to this consensus is glassy for large societies.

A general Trotter-Kato formula for a class of evolution operators

In this article we prove new results concerning the existence and various properties of an evolution system U(A+B)(t, s)0 <= s <= t <= T generated by the sum -(A(t) + B(t)) of two linear, time-dependent, and generally unbounded operators defined on time-dependent domains in a complex and separable Banach space B. In particular, writing L(B) for the algebra of all linear bounded operators on B, we can express U(A+B)(t, s)0 <= s <= t <= T as the strong limit in C(8) of a product of the holomorphic contraction semigroups generated by -A (t) and - B(t), respectively, thereby proving a product formula of the Trotter-Kato type under very general conditions which allow the domain D(A(t) + B(t)) to evolve with time provided there exists a fixed set D subset of boolean AND(t is an element of)[0,T] D(A(t) + B(t)) everywhere dense in B. We obtain a special case of our formula when B(t) = 0, which, in effect, allows us to reconstruct U(A)(t, s)0 <=(s)<=(t)<=(T) very simply in terms of the semigroup generated by -A(t). We then illustrate our results by considering various examples of nonautonomous parabolic initial-boundary value problems, including one related to the theory of timedependent singular perturbations of self-adjoint operators. We finally mention what we think remains an open problem for the corresponding equations of Schrodinger type in quantum mechanics.

A Trotter-Kato product formula for a class of non-autonomous evolution equations

In this article dedicated to Professor V. Lakshmikantham on the occasion of the celebration of his 84th birthday, we announce new results concerning the existence and various properties of an evolution system UA+B(t, s)(0 <= s <= t <= T) generated by the sum -(A(t)+B(t)) of two linear, time-dependent and generally unbounded operators defined on time-dependent domains in a complex and separable Banach space B. In particular, writing G(B) for the algebra of all linear bounded operators on B, we can express UA+B(t, s)(0 <= s <= t <= T) as the strong limit in L(B) of a product of the holomorphic contraction semigroups generated by -A(t) and -B(t), thereby getting a product formula of the Trotter-Kato type under very general conditions which allow the domain D(A(t)+B(t)) to evolve with time provided there exists a fixed set D subset of boolean AND D-t epsilon[0,D-T](A(t)+B(t)) everywhere dense in B. We then mention several possible applications of our product formula to various classes of non-autonomous parabolic initial-boundary value problems, as well as to evolution problems of Schrodinger type related to the theory of time-dependent singular perturbations of self-adjoint operators in quantum mechanics. We defer all the proofs and all the details of the applications to a separate publication. (C) 2008 Elsevier Ltd. All rights reserved.

Footemineite, the Mn-analog of atencioite, from the Foote mine, Kings Mountain, Cleveland County, North Carolina, USA, and its relationship with other roscherite-group minerals

Footemineite, ideally Ca2Mn2+square Mn22+Be4(PO4)(6)(OH)(4)-6H(2)O, triclinic, is a new member of the roscherite group. It occurs on thin fractures crossing quartz-microcline-spodumene pegmatite at the Foote mine, Kings Mountain, Cleveland County, North Carolina, U.S.A. Associated minerals are albite, analcime, eosphorite, siderite/rhodochrosite, fairfieldite, fluorapatite, quartz, milarite, and pyrite. Footemineite forms prismatic to bladed generally rough to barrel-shaped crystals up to about 1.5 mm long and I mm in diameter. Its color is yellow, the streak is white, and the luster is vitreous to slightly pearly. Footemineite is transparent and non-fluorescent. Twinning is simple, by reflection, with twin boundaries across the length of the crystals. Cleavage is good on {0 (1) over bar1}) and {100}. Density (calc.) is 2.873 g/cm(3). Footemineite is biaxial (-), n(alpha) = 1.620(2), n(beta) = 1.627(2), n(gamma) = 1.634(2) (white light). 2V(obs) = 80 degrees, 2V(calc) = 89.6 degrees. Orientation: X boolean AND b similar to 12 degrees, Y boolean AND c similar to 15 degrees, Z boolean AND a similar to 15 degrees. Elongation direction is c, dispersion: r > v or r < v, weak. Pleochroism: beta (brownish yellow) > alpha = gamma (yellow). Mossbauer and IR spectra are given. The chemical composition is (EDS mode electron microprobe, Li and Be by ICP-OES, Fe3+:Fe2+ y Mossbauer, H2O by TG data, wt%): Li2O 0.23, BeO 9.54, CaO 9.43, SrO 0.23, BaO 0.24, MgO 0.18, MnO 26.16, FeO 2.77, Fe2O3 0.62, Al2O3 0.14, P2O5 36.58, SiO2 0.42, H2O 13.1, total 99.64. The empirical formula is (Ca1.89Sr0.03Ba0.02)Sigma(1.94)(Mn-0.90(2+)square(0.10))Sigma(1.00)(square 0.78Li0.17Mg0.05) Sigma(1.00)(Mn3.252+Fe0.432+ Fe0.093+Al0.03)Sigma(3.80) Be-4.30(P5.81Si0.08O24)[(OH)3.64(H2O)0.36]Sigma(4.00)center dot 6.00H(2)O . The strongest reflection peaks of the powder diffraction pattern [d, angstrom (1, %) (hkl)] are 9.575 (53) (010), 5.998 (100) (0 (1) over bar1), 4.848 (26) (021), 3.192 (44) (210), 3.003 (14) (0 (2) over bar2), 2.803 (38) ((1) over bar 03), 2.650 (29) ((2) over bar 02), 2.424 (14) (231). Single-crystal unit-cell parameters are a = 6.788(2), b = 9.972(3), c = 10.014(2) A, (x = 73.84(2), beta = 85.34(2), gamma = 87.44(2)degrees,V = 648.74 angstrom(3), Z = 1. The space group is P (1) over bar. Crystal structure was refined to R = 0.0347 with 1273 independent reflections (F > 2(5). Footemineite is dimorphous with roscherite, and isostructural with atencioite. It is identical with the mineral from Foote mine described as ""triclinic roscherite."" The name is for the Foote mine, type locality for this and several other minerals.

Multilevel Training of Binary Morphological Operators

The design of binary morphological operators that are translation-invariant and locally defined by a finite neighborhood window corresponds to the problem of designing Boolean functions. As in any supervised classification problem, morphological operators designed from a training sample also suffer from overfitting. Large neighborhood tends to lead to performance degradation of the designed operator. This work proposes a multilevel design approach to deal with the issue of designing large neighborhood-based operators. The main idea is inspired by stacked generalization (a multilevel classifier design approach) and consists of, at each training level, combining the outcomes of the previous level operators. The final operator is a multilevel operator that ultimately depends on a larger neighborhood than of the individual operators that have been combined. Experimental results show that two-level operators obtained by combining operators designed on subwindows of a large window consistently outperform the single-level operators designed on the full window. They also show that iterating two-level operators is an effective multilevel approach to obtain better results.

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M = (V, E, A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C = {C(1), ... , C(k)} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is Sigma(k)(i=1) vertical bar C(i)vertical bar. The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

QUASISTATIONARY DISTRIBUTIONS AND FLEMING-VIOT PROCESSES IN FINITE SPACES

Consider a continuous-time Markov process with transition rates matrix Q in the state space Lambda boolean OR {0}. In In the associated Fleming-Viot process N particles evolve independently in A with transition rates matrix Q until one of them attempts to jump to state 0. At this moment the particle jumps to one of the positions of the other particles, chosen uniformly at random. When Lambda is finite, we show that the empirical distribution of the particles at a fixed time converges as N -> infinity to the distribution of a single particle at the same time conditioned on not touching {0}. Furthermore, the empirical profile of the unique invariant measure for the Fleming-Viot process with N particles converges as N -> infinity to the unique quasistationary distribution of the one-particle motion. A key element of the approach is to show that the two-particle correlations are of order 1/N.

Examples of Self-Iterating Lie Algebras, 2

We study properties of self-iterating Lie algebras in positive characteristic. Let R = K[t(i)vertical bar i is an element of N]/(t(i)(p)vertical bar i is an element of N) be the truncated polynomial ring. Let partial derivative(i) = partial derivative/partial derivative t(i), i is an element of N, denote the respective derivations. Consider the operators v(1) = partial derivative(1) + t(0)(partial derivative(2) + t(1)(partial derivative(3) + t(2)(partial derivative(4) + t(3)(partial derivative(5) + t(4)(partial derivative(6) + ...))))); v(2) = partial derivative(2) + t(1)(partial derivative(3) + t(2)(partial derivative(4) + t(3)(partial derivative(5) + t(4)(partial derivative(6) + ...)))). Let L = Lie(p)(v(1), v(2)) subset of Der R be the restricted Lie algebra generated by these derivations. We establish the following properties of this algebra in case p = 2, 3. a) L has a polynomial growth with Gelfand-Kirillov dimension lnp/ln((1+root 5)/2). b) the associative envelope A = Alg(v(1), v(2)) of L has Gelfand-Kirillov dimension 2 lnp/ln((1+root 5)/2). c) L has a nil-p-mapping. d) L, A and the augmentation ideal of the restricted enveloping algebra u = u(0)(L) are direct sums of two locally nilpotent subalgebras. The question whether u is a nil-algebra remains open. e) the restricted enveloping algebra u(L) is of intermediate growth. These properties resemble those of Grigorchuk and Gupta-Sidki groups.