Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees

In this paper, we present algorithms for enumerating, without repetitions, all triangulations and non-crossing geometric spanning trees on a given set of n points in the plane under edge inclusion constraint (i.e., some edges are required to be included in the graph). We will first extend the lexicographically ordered triangulations introduced by Bespamyatnikh to the edge-constrained case, and then we prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based on the edge-constrained lexicographically largest triangulation. More specifically, we prove that all edge-constrained triangulations can be transformed to the lexicographically largest triangulation among them by O(n²) greedy flips, i.e., by greedily increasing the lexicographical ordering of the edge list, and a similar result also holds for a set of edge-constrained non-crossing spanning trees. Our enumeration algorithms generate each output triangulation and non-crossing spanning tree in O(loglogn) and O(n²) time, respectively, based on the reverse search technique.     

Fast Enumeration Algorithms for Non-crossing Geometric Graphs

A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs.     

Abelian and Hamiltonian groupoids

In this work, we investigate some groupoids that are Abelian algebras and Hamiltonian algebras. An algebra is Abelian if for every polynomial operation and for all elements a, b, [`(c)] \bar{c} , [`(d)] \bar{d} the implication t( a,[`(c)] ) = t( a,[`(d)] ) T t( b,[`(c)] ) = t( b,[`(d)] ) t\left( {a,\bar{c}} \right) = t\left( {a,\bar{d}} \right) \Rightarrow t\left( {b,\bar{c}} \right) = t\left( {b,\bar{d}} \right) holds. An algebra is Hamiltonian if every subalgebra is a block of some congruence on the algebra. R. J. Warne in 1994 described the structure of the Abelian semigroups. In this work, we describe the Abelian groupoids with identity, the Abelian finite quasigroups, and the Abelian semigroups S such that abS = aS and Sba = Sa for all a, b ∈ S. We prove that a finite Abelian quasigroup is a Hamiltonian algebra. We characterize the Hamiltonian groupoids with identity and semigroups under the condition of Abelianity of these algebras.     

On the equipartition of plane convex bodies and convex polygons

In this paper we consider the problem of partitioning a plane compact convex body into equal-area parts, i.e., an equipartition, by means of chords. We prove two basic results that hold with some specific exceptions: (a) When chords are pairwise non-crossing, the dual tree of the partition has to be a path, (b) A convex n-gon admits no equipartition produced by more than n chords having a common interior point.     

Large Newforms of the Quantized Cat Map Revisited

We study the eigenfunctions of the quantized cat map, desymmetrized by Hecke operators. In the papers (Olofsson in Ann Henri Poincaré 10(6):1111–1139, 2009; Math Phys 286(3):1051–1072, 2009) it was observed that when the inverse of Planck’s constant is a prime exponent N = p ⁿ , with n > 2, half of these eigenfunctions become large at some points, and half remains small for all points. In this paper we study the large eigenfunctions more carefully. In particular, we answer the question of for which q the L ^q norms remain bounded as N goes to infinity. The answer is q ≤ 4.     

On the Classification of <Emphasis Type="Italic">N</Emphasis>-Points Concentrating Solutions for Mean Field Equations and the Symmetry Properties of the <Emphasis Type="Italic">N</Emphasis>-Vortex Singular Hamiltonian on the Unit Disk

Motivated by the analysis of the multiple bubbling phenomenon (Bartolucci et al. in Commun. Partial Differ. Equ. 29(7–8):1241–1265, 2004) for a singular mean field equation on the unit disk (Bartolucci and Montefusco in Nonlinearity 19:611–631, 2006), for any N≥3 we characterize a subset of the 2π/N-symmetric part of the critical set of the N-vortex singular Hamiltonian. In particular we prove that this critical subset is of saddle type. As a consequence of our result, and motivated by a recently posed open problem (Bartolucci et al. in Commun. Partial Differ. Equ. 29(7–8):1241–1265, 2004), we can prove the existence of a multiple bubbling sequence of solutions for the singular mean field equation.     

Enumerative Properties of NC (B) (p,q)

We determine the rank generating function, the zeta polynomial and the M?bius function for the poset NC ^(B) (p, q) of annular non-crossing partitions of type B, where p and q are two positive integers. We give an alternative treatment of some of these results in the case q = 1, for which this poset is a lattice. We also consider the general case of multiannular noncrossing partitions of type B, and prove that this reduces to the cases of non-crossing partitions of type B in the annulus and the disc.     

Hamiltonization of Higher-Order Nonlinear Ordinary Differential Equations and the Jacobi Last Multiplier

It is known that Jacobi’s last multiplier is directly connected to the deduction of a Lagrangian via Rao’s formula (Madhava Rao in Proc. Benaras Math. Soc. (N.S.) 2:53–59, 1940). In this paper we explicitly demonstrate that it also plays an important role in Hamiltonian theory. In particular, we apply the recent results obtained by Torres del Castillo (J. Phys. A Math. Theor. 43:265202, 2009) and deduce the Hamiltonian of a second-order ODE of the Lienard type, namely, [(x)\ddot]+f(x)[(x)\dot]²+g(x)=0\ddot{x}+f(x){\dot{x}}^{2}+g(x)=0. In addition, we consider cases where the coefficient functions may also depend on the independent variable t. We illustrate our construction with various examples taken from astrophysics, cosmology and the Painlevé-Gambier class of differential equations. Finally we discuss the Hamiltonization of third-order equations using Nambu-Hamiltonian mechanics.     

On high order symmetric and symplectic trigonometrically fitted Runge-Kutta methods with an even number of stages

The existence and construction of symplectic 2s-stage variable coefficients Runge-Kutta (RK) methods that integrate exactly IVPs whose solution is a trigonometrical polynomial of order s with a given frequency ω is considered. The resulting methods, that can be considered as trigonometrical collocation methods, are fully implicit, symmetric and symplectic RK methods with variable nodes and coefficients that are even functions of ν=ω h (h is the step size), and for ω→0 they tend to the conventional RK Gauss methods. The present analysis extends previous results on two-stage symplectic exponentially fitted integrators of Van de Vyver (Comput. Phys. Commun. 174: 255–262, 2006) and Calvo et al. (J. Comput. Appl. Math. 218: 421–434, 2008) to symmetric and symplectic trigonometrically fitted methods of high order. The algebraic order of the trigonometrically fitted symmetric and symplectic 2s-stage methods is shown to be 4s like in conventional RK Gauss methods. Finally, some numerical experiments with oscillatory Hamiltonian systems are presented.     

Abelian and Hamiltonian varieties of groupoids

We study certain groupoids generating Abelian, strongly Abelian, and Hamiltonian varieties. An algebra is Abelian if t( a,[`(c)] ) = t( a,[`(d)] ) ? t( b,[`(c)] ) = t( b,[`(d)] ) t\left( {a,\bar{c}} \right) = t\left( {a,\bar{d}} \right) \to t\left( {b,\bar{c}} \right) = t\left( {b,\bar{d}} \right) for any polynomial operation on the algebra and for all elements a, b, [`(c)] \bar{c} , [`(d)] \bar{d} . An algebra is strongly Abelian if t( a,[`(c)] ) = t( b,[`(d)] ) ? t( e,[`(c)] ) = t( e,[`(d)] ) t\left( {a,\bar{c}} \right) = t\left( {b,\bar{d}} \right) \to t\left( {e,\bar{c}} \right) = t\left( {e,\bar{d}} \right) for any polynomial operation on the algebra and for arbitrary elements a, b, e, [`(c)] \bar{c} , [`(d)] \bar{d} . An algebra is Hamiltonian if any subalgebra of the algebra is a congruence class. A variety is Abelian (strongly Abelian, Hamiltonian) if all algebras in a respective class are Abelian (strongly Abelian, Hamiltonian). We describe semigroups, groupoids with unity, and quasigroups generating Abelian, strongly Abelian, and Hamiltonian varieties.     

The embracing Voronoi diagram and closest embracing number

A point q is embraced by a set of points S if q is interior to the convex hull of S [8]. In some illumination applications where points of S are lights and q is a point to be illuminated, the embracing concept is related to a good illumination [4, 6], also known as the ∆-guarding [12] and the well-covering [10]. In this paper, we are not only interested in convex dependency (which is actually the embracing notion) but also in proximity. Suppose that the sites of S are lights or antennas with limited range; due to their limited power, they cover a disk of a given radius r centered at the sites of S. Only the points lying in such disks are illuminated. If we want to embrace the point q with the minimum range r, we need to know which is the closest light s _q to q such that q lies in the convex hull formed by s _q and the lights of S closer to q than s _q . This subset of S related to point q is called the closest embracing set for q in relation to S and its cardinality is the closest embracing number of q. By assigning every point q in the convex hull of S to its closest embracing site s _q , we obtain a partition of the convex hull that we call the embracing Voronoi diagram of S. This paper proves some properties of the embracing Voronoi diagrams and describes algorithms to compute such diagrams, as well as the levels in which the convex hull is decomposed regarding the closest embracing number.     

A Kuran Type Regularity Criterion for Sub-Laplacians

The aim of this paper is to show the strong connection between regularity of bounded open set boundary points and quasi-boundedness, on the same set, of the fundamental solution of stratified Lie group sub-Laplacians. In the euclidean case the theorem was proved by Kuran (J Lond Math Soc 2(19):301–311, 1979). We later give two examples using some direct consequences of main theorem.     

Phase Spaces and Deformation Theory

In the papers (Laudal in Contemporary Mathematics, vol. 391, [2005]; Geometry of time-spaces, Report No. 03, [2006/2007]), we introduced the notion of (non-commutative) phase algebras (spaces) Ph ⁿ (A), n=0,1,…,∞ associated to any associative algebra A (space), defined over a field k. The purpose of this paper is to study this construction in some more detail. This seems to give us a possible framework for the study of non-commutative partial differential equations. We refer to the paper (Laudal in Phase spaces and deformation theory, Report No. 09, [2006/2007]), for the applications to non-commutative deformation theory, Massey products and for the construction of the versal family of families of modules. See also (Laudal in Homology, Homotopy, Appl. 4:357–396, [2002]; Proceedings of NATO Advanced Research Workshop, Computational Commutative and Non-Commutative Algebraic Geometry, [2004]).      

Subalgebras of Orthomodular Lattices

Sachs (Can J Math 14:451–460, 1962) showed that a Boolean algebra is determined by its lattice of subalgebras. We establish the corresponding result for orthomodular lattices. We show that an orthomodular lattice L is determined by its lattice of subalgebras Sub(L), as well as by its poset of Boolean subalgebras BSub(L). The domain BSub(L) has recently found use in an approach to the foundations of quantum mechanics initiated by Butterfield and Isham (Int J Theor Phys 37(11):2669–2733, 1998, Int J Theor Phys 38(3):827–859, 1999), at least in the case where L is the orthomodular lattice of projections of a Hilbert space, or von Neumann algebra. The results here may add some additional perspective to this line of work.     

A note on sensitivity of semigroup actions

It is well known that for a transitive dynamical system (X,f) sensitivity to initial conditions follows from the assumption that the periodic points are dense. This was done by several authors: Banks, Brooks, Cairns, Davis and Stacey (Am. Math. Mon. 99, 332–334, 1992), Silverman (Rocky Mt. J. Math. 22, 353–375, 1992) and Glasner and Weiss (Nonlinearity 6, 1067–1075, 1993). In the latter article Glasner and Weiss established a stronger result (for compact metric systems) which implies that a transitive non-minimal compact metric system (X,f) with dense set of almost periodic points is sensitive. This is true also for group actions as was proved in the book of Glasner (Ergodic Theory via Joinings, 2003). Our aim is to generalize these results in the frame of a unified approach for a wide class of topological semigroup actions including one-parameter semigroup actions on Polish spaces.     

Weak Coupling Limit and Localized Oscillations in Euclidean Invariant Hamiltonian Systems

We prove the existence of time-periodic and spatially localized oscillations (discrete breathers) in a class of planar Euclidean-invariant Hamiltonian systems consisting of a finite number of interacting particles. This result is obtained in an “anticontinuous” limit, where atomic masses split into two groups that have different orders of magnitude (the mass ratio tending to infinity) and several degrees of freedom become weakly coupled. This kind of approach was introduced by MacKay and Aubry (Nonlinearity 7:1623–1643, 1994) (and further developed by Livi et al. in Nonlinearity 10:1421–1434, 1997) for one-dimensional Hamiltonian lattices. We extend their method to planar Euclidean-invariant systems and prove the existence of reversible discrete breathers in a general setting. In addition, we show the existence of nonlinear normal modes near the anticontinuous limit.      

Minimum Clique Partition in Unit Disk Graphs

The minimum clique partition (MCP) problem is that of partitioning the vertex set of a given graph into a minimum number of cliques. Given n points in the plane, the corresponding unit disk graph (UDG) has these points as vertices, and edges connecting points at distance at most 1. MCP in UDGs is known to be NP-hard and several constant factor approximations are known, including a recent PTAS. We present two improved approximation algorithms for MCP in UDGs with a realization: (I) A polynomial time approximation scheme (PTAS) running in time n^O(1/e2){n^{O(1/\varepsilon^2)}}. This improves on a previous PTAS with n^O(1/e4){n^{O(1/\varepsilon^4)}} running time by Pirwani and Salavatipour (arXiv:0904.2203v1, 2009). (II) A randomized quadratic-time algorithm with approximation ratio 2.16. This improves on a ratio 3 algorithm with O(n ²) running time by Cerioli et al. (Electron. Notes Discret. Math. 18:73–79, 2004).     

Well-posedness for a mean field model of Ginzburg–Landau vortices with opposite degrees

In this paper we analyze the hydrodynamic equations for Ginzburg–Landau vortices as derived by E (Phys. Rev. B. 50(3):1126–1135, 1994). In particular, we are interested in the mean field model describing the evolution of two patches of vortices with equal and opposite degrees. Many results are already available for the case of a single density of vortices with uniform degree. This model does not take into account the vortex annihilation, hence it can also be seen as a particular instance of the signed measures system obtained in Ambrosio et al. (Ann. Inst. H. Poincaré Anal. Non Linéaire 28(2):217–246, 2011) and related to the Chapman et al. (Eur. J. Appl. Math. 7(2):97–111, 1996) formulation. We establish global existence of L ^p solutions, exploiting some optimal transport techniques introduced in this context in Ambrosio and Serfaty (Commun. Pure Appl. Math. LXI(11):1495–1539, 2008). We prove uniqueness for L ^∞ solutions, as expected by analogy with the incompressible Euler equations in fluidodynamics. We also consider the corresponding Dirichlet problem in a bounded domain. Moreover, we show some simple examples of 1-dimensional dynamic.     

Orbital stability of spherical galactic models

We consider the three dimensional gravitational Vlasov Poisson system which is a canonical model in astrophysics to describe the dynamics of galactic clusters. A well known conjecture (Binney, Tremaine in Galactic Dynamics, Princeton University Press, Princeton, 1987) is the stability of spherical models which are nonincreasing radially symmetric steady states solutions. This conjecture was proved at the linear level by several authors in the continuation of the breakthrough work by Antonov (Sov. Astron. 4:859–867, 1961). In the previous work (Lemou et al. in A new variational approach to the stability of gravitational systems, submitted, 2011), we derived the stability of anisotropic models under spherically symmetric perturbations using fundamental monotonicity properties of the Hamiltonian under suitable generalized symmetric rearrangements first observed in the physics literature (Lynden-Bell in Mon. Not. R. Astron. Soc. 144:189–217, 1969; Gardner in Phys. Fluids 6:839–840, 1963; Wiechen et al. in Mon. Not. R. Astron. Soc. 223:623–646, 1988; Aly in Mon. Not. R. Astron. Soc. 241:15, 1989). In this work, we show how this approach combined with a new generalized Antonov type coercivity property implies the orbital stability of spherical models under general perturbations.