Enumeration of perfect matchings of a type of Cartesian products of graphs

Let G be a graph and let Pm(G) denote the number of perfect matchings of G.We denote the path with m vertices by P_m and the Cartesian product of graphs G and H by G×H. In this paper, as the continuance of our paper [W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math. 32 (2004) 175-188], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results:1. Let T be a tree and let C_n denote the cycle with n vertices. Then Pm(C₄×T)=∏(2+α²), where the product ranges over all eigenvalues α of T. Moreover, we prove that Pm(C₄×T) is always a square or double a square.2. Let T be a tree. Then Pm(P₄×T)=∏(1+3α²+α⁴), where the product ranges over all non-negative eigenvalues α of T.3. Let T be a tree with a perfect matching. Then Pm(P₃×T)=∏(2+α²), where the product ranges over all positive eigenvalues α of T. Moreover, we prove that Pm(C₄×T)=[Pm(P₃×T)]².     

Systems of sets of lengths of Puiseux monoids

In this paper we study the system of sets of lengths of non-finitely generated atomic Puiseux monoids (a Puiseux monoid is an additive submonoid of ${\mathbb{Q}}_{\ge 0}$). We begin by presenting a BF-monoid M with full system of sets of lengths, which means that for each subset S of ${\mathbb{Z}}_{\ge 2}$ there exists an element $x\in M$ whose set of lengths $\mathsf{L}(x)$ is S. It is well known that systems of sets of lengths do not characterize numerical monoids. Here, we prove that systems of sets of lengths do not characterize non-finitely generated atomic Puiseux monoids. In a recent paper, Geroldinger and Schmid found the intersection of systems of sets of lengths of numerical monoids. Motivated by this, we extend their result to the setting of atomic Puiseux monoids. Finally, we relate the sets of lengths of the Puiseux monoid $P=〈1/p|p\text{is prime}〉$ with the Goldbach's conjecture; in particular, we show that $\mathsf{L}(2)$ is precisely the set of Goldbach's numbers.     

Filtration of components of processes of random evolution

The problem of estimation of a nonobservable component θ_t for a two-dimensional process (θ_t, ξ_t) of random evolution (θ _t,ξ_t);x_t, 0≤t≤T, is investigated on the basis of observations of ξ_s. s≤t, where x _t is a homogeneous Markov process with infinitesimal operator Q. Applications to stochastic models of a (B,S)-market of securities is described under conditions of incomplete market. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 12, pp. 1701–1705, December, 1998.     

Boundedness of solutions of a system of integro-differential equations

Let b: [?1, 0] →$\text{R}$ be a nondecreasing, strictly convex C²-function with b(? 1) = 0, and let g: $\text{R}$ⁿ → $\text{R}$ⁿ be a locally Lipschitzian mapping, which is the gradient of a function G: $\text{R}$ⁿ → $\text{R}$. Consider the following vector-valued integro-differential equation of the Levin-Nohel type

$\text{x}\text{?}\text{(t)=?∝}{}_{\mathrm{?1}}{}^0\text{b(θ)g(x(t + θ))dθ}$

. (E) This equation is used in applications to model various viscoelastic phenomena. By LaSalle's invariance principle, every bounded solution x(t) goes to a connected set of zeros of g, as time t goes to infinity. It is the purpose of this paper to give several geometric criteria assuring the boundedness of solutions of (E) or some of its components.     

Distribution of Cardinalities of Row Spaces of Boolean Matrices of Order n

Let R(A) denote the row space of a Boolean matrix A of order n. We show that if n 7, then the cardinality |R(A)| (2^n–1 - 2^n–5, 2^n–1 - 2^n–6) U (2^n–1 - 2^n–6, 2^n–1). This result confirms a conjecture in [1].AMS Subject Classification (1991): 05B20 06E05 15A36Support partially by the Postdoctoral Science Foundation of China.Dedicated to Professor Chao Ko on the occasion of his 90th birthday     

Minima of initial segments of infinite sequences of reals

Suppose that 〈x_k〉_k∈? is a countable sequence of real numbers. Working in the usual subsystems for reverse mathematics, RCA₀ suffices to prove the existence of a sequence of reals 〈u_k〉_k∈? such that for each k, u_k is the minimum of {x₀, x₁, …, x_k}. However, if we wish to prove the existence of a sequence of integer indices of minima of initial segments of 〈x_k〉_k∈?, the stronger subsystem WKL₀ is required. Following the presentation of these reverse mathematics results, we will derive computability theoretic corollaries and use them to illustrate a distinction between computable analysis and constructive analysis. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Limits of chromatic zeros of some families of maps

Two families of maps are considered, one consisting of maps with two pentagons separated by n 5-rings, the other of maps with two n-gons separated by two n-rings. For each family, a homogeneous linear recursion is derived for the corresponding family of chromatic polynomials. It is shown that B₅, B₇, and B₁₀ are limits of sequences of zeros from one or another of the families, where $\text{B}{}_{\mathrm{n}}\text{= 2(1+}\text{cos}\text{2π}\text{n}\text{)}$.     

A characterization of p-bases of rings of constants

We obtain two equivalent conditions for m polynomials in n variables to form a p-basis of a ring of constants of some polynomial K-derivation, where K is a unique factorization domain of characteristic p > 0. One of these conditions involves Jacobians while the other some properties of factors. In the case m = n this extends the known theorem of Nousiainen, and we obtain a new formulation of the Jacobian conjecture in positive characteristic.     

Continuum cardinality of the set of solutions of one class of equations that contain the function of frequency of ternary digits of a number

We study the equation ν ₁(x) = x, where ν ₁(x) is the function of frequency of the digit 1 in the ternary expansion of x. We prove that this equation has a unique rational root and a continuum set of irrational solutions. An algorithm for the construction of solutions is proposed. We also describe the topological and metric properties of the set of all solutions. Some additional facts about the equations ν _i (x) = x, i = 0, 2, are given. Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 10, pp. 1414–1421, October, 2008.     

Polarizations of Prym varieties of pairs of coverings

To any pair of coverings f_i:X → X_i, i=1, 2, of smooth projective curves one can associate an abelian subvariety of the Jacobian J_X, the Prym variety P(f₁, f₂) of the pair (f₁, f₂). In some cases we can compute the type of the restriction of the canonical principal polarization of J_X. We obtain 2 families of Prym-Tyurin varieties of exponent 6. Received: 2 September 2004     

Finiteness of integrals of functions of Levy processes

We prove necessary and sufficient conditions for the almostsure convergence of the integrals

and thus of ,where M_t = sup{|X_s|: s t} is the two-sided maximum processcorresponding to a Lévy process (X_t)_{t 0}, a(·)is a non-decreasing function on [0, ) with a(0) = 0, g(·)is a positive non-increasing function on (0, ), possibly withg(0 + ) = , and f(·) is a positive non-decreasing functionon [0, ) with f(0) = 0. The conditions are expressed in termsof the canonical measure, (·), of the process X_t. Thespecial case when a(x) = 0, f(x) = x and g(·) is equivalentto the tail of (at zero or infinity) leads to an interestingcomparison of M_t with the largest jump of X_t in (0, t]. Some results concerning the convergence at zero and infinityof integrals like t g(a(t) + |X_t|) dt, t g(S_t) dt,and t g(R_t) dt, where S_t is the supremum process and R_t= S_t – X_t is the process reflected in its supremum, arealso given. We also consider the convergence of integrals suchas , etc.     

Rates of Convergence of Means of Euclidean Functionals

Let L be the Euclidean functional with p-th power-weighted edges. Examples include the sum of the p-th power-weighted lengths of the edges in minimal spanning trees, traveling salesman tours, and minimal matchings. Motivated by the works of Steele, Redmond and Yukich (Ann. Appl. Probab. 4, 1057–1073, 1994, Stoch. Process. Appl. 61, 289–304, 1996) have shown that for n i.i.d. sample points {X ₁,…,X _n } from [0,1] ^d , L({X ₁,…,X _n })/n ^(d−p)/d converges a.s. to a finite constant. Here we bound the rate of convergence of EL({X ₁,…,X _n })/n ^(d−p)/d . Y. Koo supported by the BK21 project of the Department of Mathematics, Sungkyunkwan University. S. Lee supported by the BK21 project of the Department of Mathematics, Yonsei University.     

Rings of quotients of f-rings by gabriel filters of ideals

The article examines the role of Gabriel filters of ideals in the ontext of semiprime f-rings. It is shown that for every 2-convex semiprime f-ring Aand every multiplicative filter B of dense ideals the ring of quotients of A by B, namely the direct limit of the Hom _A (I, A) over all I∈ B, is an l-subring of QA, the maximum ring of quotients. Relative to the category of all commutative rings with identity, it is shown that for every 2-convex semiprime f-ring A qA, the classical ring of quotients, is the largest flat epimorphic extension of A. If Ais also a Prüfer ring then it follows that every extension of Ain qA is of the form S ^-1A for a suitable multiplicative subset S. The paper also examines when a Utumi ring of quotients of a semiprime f-ring is obtained from a Gabriel filter. For a ring of continuous functions C(X), with Xcompact, this is so for each C(U) and C ^*(U), when Uis dense open, but not for an arbitrary direct limit of C(U),taken over a filter base of dense open sets. In conclusion, it is shown that, for a complemented semiprime f-ring A, the ideals of Awhich are torsion radicals with respect to some hereditary torsion theory are precisely the intersections of minimal prime ideals of A.     

Isomorphisms of lattices of subalgebras of semirings of continuous nonnegative functions

In this work, lattice isomorphisms of semirings C ⁺(X) of continuous nonnegative functions over an arbitrary topological space X are characterized. It is proved that any isomorphism of lattices of all subalgebras with a unit of semirings C ⁺(X) and C ⁺(Y) is induced by a unique isomorphism of semirings. The same result is also correct for lattices of all subalgebras excepting the case of two-point Tychonovization of spaces.     

Codimensions of products and of intersections of verbally primeT-ideals

By Kemer’s theory [9],T idealsJ ₁ ∪…∪J _r andJ ₁ …J _r, where eachJ _i is verbally prime, are of fundamental importance in the theory of P.I. algebras. We calculate, approximately and asymptotically, the codimensions of suchT-ideals, thereby extending the corresponding results about matrix algebras. In all such cases, the exponential growth of the codimensions is calculated; in particular, it is always an integer. Partially supported by NSF grant DMS 9303230. Partially supported by NSF grant DMS 9101488.     

Uniformity of a certain systems of functions of many-valued logic

For any finite system A of functions of many-valued logic taking values in the set {0,1} such that a projection of A generates the class of all monotone boolean functions, it is proved that there exists constants c and d such that for an arbitrary function f ε [A] the depth D(f) and the complexity L(f) of f in the class of formulas over A satisfy the relation D(f) ≤ clog₂ L(f) + d.     

On the sum of digits of some sequences of integers

Let b ≥ 2 be a fixed positive integer. We show for a wide variety of sequences {a _n } _n=1 ^∞ that for almost all n the sum of digits of a _n in base b is at least c _b log n, where c _b is a constant depending on b and on the sequence. Our approach covers several integer sequences arising from number theory and combinatorics.