Orbit structure and countable sections for actions of continuous groups

It is shown that if a second countable locally compact group G acts nonsingularly on an analytic measure space (S, μ), then there is a Borel subset E ? S such that EG is conull in S and each sG ∩ E is countable. It follows that the measure groupoid constructed from the equivalence relation s ～ sg on E may be simply described in terms of the measure groupoid made from the action of some countable group. Some simplifications are made in Mackey's theory of measure groupoids. A natural notion of “approximate finiteness” (AF) is introduced for nonsingular actions of G, and results are developed parallel to those for countable groups; several classes of examples arising naturally are shown to be AF. Results on “skew product” group actions are obtained, generalizing the countable case, and partially answering a question of Mackey. We also show that a group-measure space factor obtained from a continuous group action is isomorphic (as a von Neumann algebra) to one obtained from a discrete group action.     

An Empirical Study of MAX-2-SAT Phase Transitions

The decision version of the maximum satisfiability problem (MAX-SAT) is stated as follows: Given a set S of propositional clauses and an integer g, decide if there exists a truth assignment that falsifies at most g clauses in S, where g is called the allowance for false clauses. We conduct an extensive experiment on over a million of random instances of 2-SAT and identify statistically the relationship between g, n (number of variables) and m (number of clauses). In our experiment, we apply an efficient decision procedure based on the branch-and-bound method. The statistical data of the experiment confirm not only the “scaling window” of MAX-2-SAT discovered by Chayes, Kim and Borgs, but also the recent results of Coppersmith et al. While there is no easy-hard-easy pattern for the complexity of 2-SAT at the phase transition, we show that there is such a pattern for the decision problem of MAX-2-SAT associated with the phase transition. We also identify that the hardest problems are among those with high allowance for false clauses but low number of clauses.     

Non-conflicting ordering cones and vector optimization in inductive limits

Let (E, ξ)= ind (E_n, ξ_n) be an inductive limit of a sequence (E_n, ξ_n)_{n∈ N} of locally convex spaces and let every step (E_n, ξ_n) be endowed with a partial order by a pointed convex (solid) cone S_n. In the framework of inductive limits of partially ordered locally convex spaces, the notions of lastingly efficient points, lastingly weakly efficient points and lastingly globally properly efficient points are introduced. For several ordering cones, the notion of non-conflict is introduced. Under the requirement that the sequence (S_n)_{n∈ N} of ordering cones is non-conflicting, an existence theorem on lastingly weakly efficient points is presented. From this, an existence theorem on lastingly globally properly efficient points is deduced.     

Moment systems and orthogonal polynomials in several variables

The first part of this paper deals with general moment (“Appell”) systems on $\text{R}$^N generated by a Hamiltonian function H(x, D) and also with representations of GL(N) on the associated spaces of polynomials. The second part discusses the theory of Bernoulli generators on $\text{R}$^N determining systems of orthogonal polynomials that are extensions of the Meixner polynomials to several variables. Linear actions for these spaces are discussed. Some tensors related to the general Bernoulli generators are considered.     

The iterative instrumental variables method and the full information maximum likelihood method for estimating interdependent systems

The “iterative instrumental variables” (IIV) method for estimating interdependent systems, originally referred to as a symmetric counterpart to the “fix-point” (FP) method, shares its symmetry properties with Durbin's iterative method for performing the “full information maximum likelihood” (FIML) estimation. Classical interdependent systems are considered and identities may occur among the structural equations. Alternative symmetric procedures for obtaining FIML estimates are also dealt with, including the sequential maximization of the likelihood function with respect to the coefficients of one structural equation at a time.Two recent estimation methods developed by Brundy and Jorgenson (1971, Review of Economics and Statistics53, 207–224) as well as Dhrymes (1971, Austral. J. Statist.13, 168–175) can be considered the second approximation of the IIV method and Durbin's method respectively with the first approximation obtained by the “ordinary instrumental variables” (OIV) method. In practice the second approximation depends heavily on the choice of initial instrumental variables, although the asymptotic distribution is not changed by the continued iteration.     

Tabloïdes

A tabloïde is composed of two finite sets, E (the set of the rows) and F (the set of the columns), and of a function f: $\text{P}$(E) × $\text{P}$(F) → $\text{N}$, which is a Whitney's rank in its two variables. There are tabloids associated to matrices, to bipartite graphs and to ordinary graphs respectively in relation to linear rank, matchings and gammoids. Some of the properties of matrices can be generalized to tabloids (transposition, direct sum, inverse, product…). The properties of bipartite graphs which consists in “transmission” of matroids by matchings is used to define a class of tabloids (which strictly contains those which are associated to matrices). Finally, the problem of the representation of a tabloid on a field is studied.     

Gorenstein dimension of modules over homomorphisms

Given a homomorphism of commutative noetherian rings R→S and an S-module N, it is proved that the Gorenstein flat dimension of N over R, when finite, may be computed locally over S. When, in addition, the homomorphism is local and N is finitely generated over S, the Gorenstein flat dimension equals , where E is the injective hull of the residue field of R. This result is analogous to a theorem of André on flat dimension.     

On various averaging methods for a nonlinear oscillator with slow time-dependent potential and a nonconservative perturbation

The main aim of the paper is to compare various averaging methods for constructing asymptotic solutions of the Cauchy problem for the one-dimensional anharmonic oscillator with potential V (x, τ) depending on the slow time τ = ?t and with a small nonconservative term ?g( $ \dot x $ , x, τ), ? ? 1. This problem was discussed in numerous papers, and in some sense the present paper looks like a “methodological” one. Nevertheless, it seems that we present the definitive result in a form useful for many nonlinear problems as well. Namely, it is well known that the leading term of the asymptotic solution can be represented in the form $ X\left( {\frac{{S\left( \tau \right) + \varepsilon \varphi \left( \tau \right)}} {\varepsilon },I\left( \tau \right),\tau } \right) $ , where the phase S, the “slow” parameter I, and the so-called phase shift ? are found from the system of “averaged” equations. The pragmatic result is that one can take into account the phase shift ? by considering it as a part of S and by simultaneously changing the initial data for the equation for I in an appropriate way.     

Asymptotic and numerical study of resonant tunneling in two-dimensional quantum waveguides of variable cross section

A waveguide is considered that coincides with a strip having two narrows of width ?. The electron wave function satisfies the Helmholtz equation with Dirichlet boundary conditions. The part of the waveguide between the narrows plays the role of a resonator, and there arise conditions for electron resonant tunneling. This phenomenon means that, for an electron of energy E, the probability T(E) of passing from one part of the waveguide to the other through the resonator has a sharp peak at E = E _res, where E _res is a “resonant” energy. To analyze the operation of electronic devices based on resonant tunneling, it is important to know E _res and the behavior of T(E) for E close to E _res. Asymptotic formulas for the resonance energy and the transition and reflection coefficients as ? → 0 are derived. These formulas depend on the limit shape of the narrows. The limit waveguide near each narrow is assumed to coincide with a pair of vertical angles. The asymptotic results are compared with numerical ones obtained by approximately computing the waveguide scattering matrix. Based on this comparison, the range of ? is found in which the asymptotic approach agrees with the numerical results. The methods proposed are applicable to much more complicated models than that under consideration. Specifically, the same approach is suitable for an asymptotic and numerical analysis of tunneling in three-dimensional quantum waveguides of variable cross section.     

Classification of systems of Dyson-Schwinger equations in the Hopf algebra of decorated rooted trees

We consider systems of combinatorial Dyson-Schwinger equations (briefly, SDSE) , … , in the Connes-Kreimer Hopf algebra HI of rooted trees decorated by I={1,…,N}, where is the operator of grafting on a root decorated by i, and F₁,…,FN are non-constant formal series. The unique solution X=(X₁,…,XN) of this equation generates a graded subalgebra H(S) of HI. We characterise here all the families of formal series (F₁,…,FN) such that H(S) is a Hopf subalgebra. More precisely, we define three operations on SDSE (change of variables, dilatation and extension) and give two families of SDSE (cyclic and fundamental systems), and prove that any SDSE (S) such that H(S) is Hopf is the concatenation of several fundamental or cyclic systems after the application of a change of variables, a dilatation and iterated extensions.     

Bounds on a graph's security number

Let G=(V,E) be a graph. A set S⊆V is a defensive alliance if |N[x]∩S|?|N[x]-S| for every x∈S. Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attack by its neighbors outside of S. An entire set S is secure if any subset X⊆S, not just singletons, can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. The security number s(G) of G is the cardinality of a smallest secure set. Bounds on s(G) are presented.     

Clusters die hard: Time-correlated excitation in the Hamiltonian mean field model

The Hamiltonian mean field (HMF) model has a low-energy phase where N particles are trapped inside a cluster. Here, we investigate some properties of the trapping/untrapping mechanism of a single particle into/outside the cluster. Since the single particle dynamics of the HMF model resembles the one of a simple pendulum, each particle can be identified as a high-energy particle (HEP) or a low-energy particle (LEP), depending on whether its energy is above or below the separatrix energy. We then define the trapping ratio as the ratio of the number of LEP to the total number of particles and the “fully-clustered” and “excited” dynamical states as having either no HEP or at least one HEP. We analytically compute the phase-space average of the trapping ratio by using the Boltzmann–Gibbs stable stationary solution of the Vlasov equation associated with the N → ∞ limit of the HMF model. The same quantity, obtained numerically as a time average, is shown to be in very good agreement with the analytical calculation. Another important feature of the dynamical behavior of the system is that the dynamical state changes transitionally: the “fully-clustered” and “excited” states appear in turn. We find that the distribution of the lifetime of the “fully-clustered” state obeys a power law. This means that clusters die hard, and that the excitation of a particle from the cluster is not a Poisson process and might be controlled by some type of collective motion with long memory. Such behavior should not be specific of the HMF model and appear also in systems where itinerancy among different “quasi-stationary” states has been observed. It is also possible that it could mimick the behavior of transient motion in molecular clusters or some observed deterministic features of chemical reactions.     

Brownian Gibbs property for Airy line ensembles

Consider a collection of N Brownian bridges $B_{i}:[-N,N] \to \mathbb{R} $ , B _i (?N)=B _i (N)=0, 1≤i≤N, conditioned not to intersect. The edge-scaling limit of this system is obtained by taking a weak limit as N→∞ of the collection of curves scaled so that the point (0,2^1/2 N) is fixed and space is squeezed, horizontally by a factor of N ^2/3 and vertically by N ^1/3. If a parabola is added to each of the curves of this scaling limit, an x-translation invariant process sometimes called the multi-line Airy process is obtained. We prove the existence of a version of this process (which we call the Airy line ensemble) in which the curves are almost surely everywhere continuous and non-intersecting. This process naturally arises in the study of growth processes and random matrix ensembles, as do related processes with “wanderers” and “outliers”. We formulate our results to treat these relatives as well. Note that the law of the finite collection of Brownian bridges above has the property—called the Brownian Gibbs property—of being invariant under the following action. Select an index 1≤k≤N and erase B _k on a fixed time interval (a,b)?(?N,N); then replace this erased curve with a new curve on (a,b) according to the law of a Brownian bridge between the two existing endpoints (a,B _k (a)) and (b,B _k (b)), conditioned to intersect neither the curve above nor the one below. We show that this property is preserved under the edge-scaling limit and thus establish that the Airy line ensemble has the Brownian Gibbs property. An immediate consequence of the Brownian Gibbs property is a confirmation of the prediction of M. Prähofer and H. Spohn that each line of the Airy line ensemble is locally absolutely continuous with respect to Brownian motion. We also obtain a proof of the long-standing conjecture of K. Johansson that the top line of the Airy line ensemble minus a parabola attains its maximum at a unique point. This establishes the asymptotic law of the transversal fluctuation of last passage percolation with geometric weights. Our probabilistic approach complements the perspective of exactly solvable systems which is often taken in studying the multi-line Airy process, and readily yields several other interesting properties of this process.     

Characterization of the Quasi-Stationary State of an Impurity Driven by Monochromatic Light I: The Effective Theory

We consider an impurity (N-level atom) driven by monochromatic light in a host environment which is a fermionic thermal reservoir. The external light source is a time-periodic perturbation of the atomic Hamiltonian stimulating transitions between two atomic energy levels E ₁ and E _N and thus acts as an optical pump. The purpose of the present work is the analysis of the effective atomic dynamics resulting from the full microscopic time-evolution of the compound system. We prove, in particular, that the atomic dynamics of population relaxes for large times to a quasi-stationary state, that is, a stationary state up to small oscillations driven by the external light source. This state turns out to be uniquely determined by a balance condition. The latter is related to “generalized Einstein relations” of spontaneous/stimulated emission/absorption rates, which are conceptually similar to the phenomenological relations derived by Einstein in 1916. As an application we show from quantum mechanical first principles how an inversion of population of energy levels of an impurity in a crystal can appear. Our results are based on the spectral analysis of the generator of the evolution semigroup related to a non-autonomous Cauchy problem effectively describing the atomic dynamics.     

Dominating sets and domatic number of circular arc graphs

A dominating set of a graph G = (N,E) is a subset S of nodes such that every node is either in S or adjacent to a node which is in S. The domatic number of G is the size of a maximum cardinality partition of N into dominating sets. The problems of finding a minimum cardinality dominating set and the domatic number are both NP-complete even for special classes of graphs. In the present paper we give an O(n∣E∣) time algorithm that finds a minimum cardinality dominating set when G is a circular arc graph (intersection graph of arcs on a circle). The domatic number problem is solved in O(n² log n) time when G is a proper circular arc graph, and it is shown NP-complete for general circular arc graphs.     

A dynamical model of company growth

A theoretical method based on the concept of “system-size expansion” isapplied to the study of a nonlinear stochastic model of company growth, which treats the populations C and E, of the capital resources of the company and the number of employees, as interacting entities. These populations are assumed to have upper limits, C_max and E_max, as determined by the conditions prevailing in the market. Analytical expressions for the time evolution of both stochastic and deterministic aspects of the model are derived. An interesting feature of the model lies in the appearance of a “critical phenomenon”, in the nature of a phase transition, in the system when a certain parameter ξ of the problem approaches its critical value ξ_c. Finally, the nonlinearity of the model enables us to exploit the asymptotic expressions for the various quantities pertaining to the system for evaluating certain finite-size effects as well.     

Some results on exclusive sum graphs

Let N(Z) denote the set of all positive integers (integers). The sum graph G ⁺(S) of a finite subset S?N(Z) is the graph (S,E) with uv∈E if and only if u+v∈S. A graph G is said to be an (integral) sum graph if it is isomorphic to the sum graph of some S?N(Z). A sum labelling S is called an exclusive sum labelling if u+v∈S?V(G) for any edge uv∈E(G). We say that G is labeled exclusively. The least number r of isolated vertices such that G∪rK ₁ is an exclusive sum graph is called the exclusive sum number ε(G) of graph G. In this paper, we discuss the exclusive sum number of disjoint union of two graphs and the exclusive sum number of some graph classes.     

Security in graphs

Let G=(V,E) be a graph. A set S⊆V is a defensive alliance if |N[x]∩S|?|N[x]-S| for every x∈S. Thus, each vertex of a defensive alliance can, with the aid of its neighbors in S, be defended from attack by its neighbors outside of S. An entire set S is secure if any subset X⊆S can be defended from an attack from outside of S, under an appropriate definition of what such a defense implies. Necessary and sufficient conditions for a set to be secure are determined.     

Nonnegative rank-preserving operators

Analogues of characterizations of rank-preserving operators on field-valued matrices are determined for matrices witheentries in certain structures $\text{S}$ contained in the nonnegative reals. For example, if $\text{S}$ is the set of nonnegative members of a real unique factorization domain (e.g. the nonnegative reals or the nonnegative integers), M is the set of m×n matrices with entries in $\text{S}$, and min(m,n)?4, then a “linear” operator on M preserves the “rank” of each matrix in M if and only if it preserves the ranks of those matrices in M of ranks 1, 2, and 4. Notions of rank and linearity are defined analogously to the field-valued concepts. Other characterizations of rank-preserving operators for matrices over these and other structures $\text{S}$ are also given.