On the m-capacitated peripatetic salesman problem with capacity restrictions

We consider a special case of the problem of finding m Hamiltonian cycles with capacity restrictions on the number of usages of the edges (m-Capacitated Peripatetic Salesman Problem or m-CPSP): the minimization and maximization 2-CPSP with edge weights chosen from an integer segment {1, q} with the edges capacities given as independent identically distributed random variables equal to 2 with probability p and 1 with probability (1 ? p). Some polynomial algorithms are proposed for 2-CPSP_min and 2-CPSP_max with average performance guarantees. In particular, when the edge weights are equal to 1 and 2, the algorithms have approximation ratios (19 ? 5p)/12 and (25 + 7p)/36 for the minimization and the maximization problem correspondingly.     

Some Boolean Algebras with Finitely Many Distinguished Ideals I

We consider the theory Th_prin of Boolean algebras with a principal ideal, the theory Th_max of Boolean algebras with a maximal ideal, the theory Th_ac of atomic Boolean algebras with an ideal where the supremum of the ideal exists, and the theory Th_sa of atomless Boolean algebras with an ideal where the supremum of the ideal exists. First, we find elementary invariants for Th_prin and Th_sa. If T is a theory in a first order language and α is a linear order with least element, then we let Sentalg(T) be the Lindenbaum-Tarski algebra with respect to T, and we let intalg(α) be the interval algebra of α. Using rank diagrams, we show that Sentalg(Th_prin) ? intalg(ω⁴), Sentalg(Th_max) ? intalg(ω³) ? Sentalg(Th_ac), and Sentalg(Th_sa) ? intalg(ω² + ω²). For Th_max and Th_ac we use Ershov's elementary invariants of these theories. We also show that the algebra of formulas of the theory Tx of Boolean algebras with finitely many ideals is atomic.     

Two new sets of ellipse-related concyclic points

Two new circles (denoted by Γ _I and Γ _E ) are shown to be associated with any ellipse. Their analogies with two circles described by Barlotti are described. Two further new circles—denoted by Ω and Γ—are shown to be associated with any general point P of the ellipse. Tight relationships link the circles Ω and Γ with the circle K (previously introduced by the present author), as well as with Monge’s orthoptic circle, with Barlotti’s circles and with the circles Γ _I and Γ _E . In particular, the circle Ω is orthogonal to Monge’s circle. A new special point of the ellipse (the point T) is described. New properties of Fagnano’s point are described.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

Multipoint Problem for Nonisotropic Partial Differential Equations with Constant Coefficients

We investigate the well-posedness of a problem with multipoint conditions with respect to a chosen variable t and periodic conditions with respect to coordinates x ₁,..., x _p for a nonisotropic (concerning differentiation with respect to t and x ₁,..., x _p) partial differential equation with constant complex coefficients. We establish conditions for the existence and uniqueness of a solution of this problem and prove metric theorems on lower bounds for small denominators appearing in the course of the construction of its solution.     

Enumeration of rectangular arrays of zeros and ones

For r=1,2 the rectangular arrays of zeros and ones with r rows and n columns, with m_i zeros and r_i changes in the ith row, and with s_i vertical changes between the ith and (i+1)st rows, i=1,…,r-1, are enumerated. The number of arrays of zeros and ones with 3 rows and n columns, with r_i changes in the ith row, i=1,2,3, and with s_i vertical changes between the ith and (i+1)st rows, i=1,2, is also determined.     

Multipoint Problem with Multiple Nodes for Partial Differential Equations

We establish conditions for the existence and uniqueness of a solution of a problem with multipoint conditions with respect to a selected variable t (in the case of multiple nodes) and periodic conditions with respect to x ₁,..., x _p for a nonisotropic partial differential equation with constant complex coefficients. We prove metric theorems on lower bounds for small denominators appearing in the course of the solution of this problem.     

Pointwise bornological spaces

With each metric space (X,d) we can associate a bornological space (X,Bd) where Bd is the set of all subsets of X with finite diameter. Equivalently, Bd is the set of all subsets of X that are contained in a ball with finite radius. If the metric d can attain the value infinite, then the set of all subsets with finite diameter is no longer a bornology. Moreover, if d is no longer symmetric, then the set of subsets with finite diameter does not coincide with the set of subsets that are contained in a ball with finite radius. In this text we will introduce two structures that capture the concept of boundedness in both symmetric and non-symmetric extended metric spaces.     

Stability of the standing waves for a class of coupled nonlinear Klein-Gordon equations

This paper deals with the standing waves for a class of coupled nonlinear Klein-Gordon equations with space dimension N ≥ 3, 0 〈 p, q 〈 2/N-2 and p ＋ q 〈 4/N. By using the variational calculus and scaling argument, we establish the existence of standing waves with ground state, discuss the behavior of standing waves as a function of the frequency ω and give the sufficient conditions of the stability of the standing waves with the least energy for the equations under study.     

Deterministic symmetric rendezvous with tokens in a synchronous torus

In the rendezvous problem, the goal for two mobile agents is to meet whenever this is possible. In the rendezvous with detection problem, an additional goal for the agents is to detect the impossibility of a rendezvous (e.g., due to symmetrical initial positions of the agents) and stop. We consider the rendezvous problem with and without detection for identical anonymous mobile agents (i.e., running the same deterministic algorithm) with tokens in an anonymous synchronous torus with a sense of direction, and show that there is a striking computational difference between one and more tokens. Specifically, we show that (1) two agents with a constant number of unmovable tokens, or with one movable token each, cannot rendezvous in an n×n torus if they have o(logn) memory, while they can solve the rendezvous with detection problem in an n×m torus as long as they have one unmovable token and O(logn+logm) memory; in contrast, (2) when two agents have two movable tokens each then the rendezvous problem (respectively, rendezvous with detection problem) is solvable with constant memory in an arbitrary n×m (respectively, n×n) torus; and finally, (3) two agents with three movable tokens each and constant memory can solve the rendezvous with detection problem in an n×m torus. This is the first publication in the literature that studies tradeoffs between the number of tokens, memory and knowledge the agents need in order to meet in a torus.     

A class of vertex-transitive digraphs,II

(1). We determine the number of non-isomorphic classes of self-complementary circulant digraphs with pq vertices, where p and q are distinct primes. The non-isomorphic classes of these circulant digraphs with pq vertices are enumerated. (2). We also determine the number of non-isomorphic classes of self-complementary, vertex-transitive digraphs with a prime number p vertices, and the number of self-complementary strongly vertex-transitive digraphs with p vertices. The non-isomorphic classes of strongly vertex-transitive digraphs with p vertices are also enumerated.     

Average boundary conditions in Cauchy problems

We consider the general Cauchy problem with initial data in a Hilbert space and with a formal dissipative linear generator. A complete parametrization is known of the (abstract) boundary conditions which make this problem well set. We exhibit a distinguished subset $\text{B}$_E of the set $\text{B}$ of boundary conditions and demonstrate explicitly that the evolution associated with each B in $\text{B}$ can be represented as a (time independent) average over the evolutions associated with B′ in $\text{B}$_E. Applications are discussed to Schrödinger equations in bounded regions or with singular potentials.     

Cohomology of Subregular Tilting Modules for Small Quantum Groups

Let U be a quantumgroup with divid d powers at root ofunity constructed froma rootsystem R .Let u U b th small quantumgroup.Th cohomologyof u with trivial coefficients was computed by Ginzburg and Kumar.It turns out to be isomorphic to the functions algebra of the nilpotent cone of a semisimpl algebraic group with root system R .In this not we calculate cohomology of u with coefficients in simplest reducible tilting modul with nontrivial cohomology.It appears to b isomorphic to th functions algebra of th closure of the subregular nilpotent orbit.     

Geodesic flow on three-dimensional ellipsoids with equal semi-axes

Following on from our previous study of the geodesic flow on three dimensional ellipsoid with equal middle semi-axes, here we study the remaining cases: Ellipsoids with two sets of equal semi-axes with SO(2) × SO(2) symmetry, ellipsoids with equal larger or smaller semiaxes with SO(2) symmetry, and ellipsoids with three semi-axes coinciding with SO(3) symmetry. All of these cases are Liouville-integrable, and reduction of the symmetry leads to singular reduced systems on lower-dimensional ellipsoids. The critical values of the energy-momentum maps and their singular fibers are completely classified. In the cases with SO(2) symmetry there are corank 1 degenerate critical points; all other critical points are non-degenreate. We show that in the case with SO(2) × SO(2) symmetry three global action variables exist and the image of the energy surface under the energy-momentum map is a convex polyhedron. The case with SO(3) symmetry is non-commutatively integrable, and we show that the fibers over regular points of the energy-casimir map are T ² bundles over S ².      

Mesons and diquarks in a dense quark medium with color superconductivity

In the framework of the Nambu-Jona-Lasinio model with two quark flavors, we investigate the spectrum of meson and diquark excitations of dense quark matter in the phase with color superconductivity. The color SU_c(3) symmetry is spontaneously broken to SU_c(2) in this phase. But instead of the expected five Goldstone bosons in the mass spectrum, we observe only three, among which two bosons obey the quadratic dispersion law. We find the doublet of light diquark states with the mass ∼ 15 MeV and also the heavy diquark resonance (SU_c(2) singlet) with the mass ∼ 1100 MeV. The π-and σ-mesons have the mass ∼ 330 Mev in the phase with color superconductivity. The π-mesons are then stable particles, while the σ-meson is stable only in the chiral limit in which the current quark mass m₀ becomes zero. If m₀ ≠ 0, then the σ-meson mixes with diquarks in the phase with color superconductivity and becomes a resonance with the width ∼ 30 MeV. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 150, No. 1, pp. 95–111, January, 2007.     

Traveling fronts in diffusive and cooperative Lotka–Volterra system with nonlocal delays

This paper is concerned with a diffusive and cooperative Lotka–Volterra model with distributed delays and nonlocal spatial effect. By using an iterative technique recently developed by Wang, Li and Ruan (Traveling wave fronts in reaction-diffusion systems with spatio-temporal delays, J. Differential Equations 222 (2006), 185–232), sufficient conditions are established for the existence of traveling wave front solutions connecting the zero and the positive equilibria by choosing different kernels. The result is an extension of an existing result for Fisher-KPP equation with nonlocal delay and is somewhat parallel to the existing result for diffusive and cooperative Lotka–Volterra system with discrete delays.     

Axisymmetrical rotating jets

The article presents computation results for a free jet emerging from a nozzle of radius R with Mach number M = 1 and nonrated value n = 3. The jet rotates at the nozzle outlet with constant angular velocity ω = 2 and corresponding circular velocity W = ωr (r < R ). The computation results for this jet are compared with those for a laminar (non-rotating) jet with the same fluid-dynamic parameters. The numerical results corroborate the theoretical conclusions concerning the effect of jet rotation on flow structure. Specifically, it is confirmed that the mixing of the jet with the surrounding gas is more intense and that a strongly twisted jet exhibits backflow toward the nozzle in the axial region. Translated from Prikladnaya Matematika i Informatika, No. 28, pp. 44–49, 2008.     

A Multipoint Problem for Pseudodifferential Equations

We investigate the well-posedness of a problem with multipoint conditions with respect to a chosen variable t and periodic conditions with respect to coordinates x ₁,...,x _p for equations unsolved with respect to the leading derivative with respect to t and containing pseudodifferential operators. We establish conditions for the unique solvability of this problem and prove metric assertions related to lower bounds for small denominators appearing in the course of its solution.     

Some Boolean algebras with finitely many distinguished ideals II

We describe the countably saturated models and prime models (up to isomorphism) of the theory Th_prin of Boolean algebras with a principal ideal, the theory Th_max of Boolean algebras with a maximal ideal, the theory Th_ac of atomic Boolean algebras with an ideal such that the supremum of the ideal exists, and the theory Th_sa of atomless Boolean algebras with an ideal such that the supremum of the ideal exists. We prove that there are infinitely many completions of the theory of Boolean algebras with a distinguished ideal that do not have a countably saturated model. Also, we give a sufficient condition for a model of the theory T_X of Boolean algebras with distinguished ideals to be elementarily equivalent to a countably saturated model of T_X.