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)]².     

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)     

Region of variability of two subclasses of univalent functions

Let F₁ (F₂ respectively) denote the class of analytic functions f in the unit disk |z|<1 with f(0)=0=f^′(0)−1 satisfying the condition RePf(z)<3/2 (RePf(z)>−1/2 respectively) in |z|<1, where Pf(z)=1+zf^″(z)/f^′(z). For any fixed z₀ in the unit disk and λ∈[0,1), we shall determine the region of variability for logf^′(z₀) when f ranges over the class and , respectively.     

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.     

Construction of generators of quasi-interpolation operators of high approximation orders in spaces of polyharmonic splines

The paper presents a simple procedure for the construction of quasi-interpolation operators in spaces of m-harmonic splines in R^d, which reproduce polynomials of high degree. The procedure starts from a generator ?₀, which is easy to derive but with corresponding quasi-interpolation operator reproducing only linear polynomials, and recursively defines generators ?₁,?₂,…,?_m−1 with corresponding quasi-interpolation operators reproducing polynomials of degree up to 3,5,…,2m−1 respectively. The construction of ?_j from ?_j−1 is explicit, simple and independent of m. The special case d=1 and the special cases d=2,m=2,3,4 are discussed in details.     

Picard Groups of Rings of Coinvariants

Let k be a field, H a Hopf k-algebra with bijective antipode, A a right H-comodule algebra and C a Hopf algebra with bijective antipode which is also a right H-module coalgebra. Under some appropriate assumptions, and assuming that the set of grouplike elements G(A ⊗ C) of the coring A ⊗ C is a group, we show how to calculate, via an exact sequence, the Picard group of the subring of coinvariants in terms of the Picard group of A and various subgroups of G(A ⊗ C). Presented by: Claus Ringel.     

Connectedness of curve complex of surface

For a closed orientable surface Sg of genus not smaller than 2,C(Sg) is the curve complex on S g whose vertices consist of the isotopy classes of nontrivial circles on Sg. It has been showed that any two vertices in C(Sg) can be connected by an edge path,and C(Sg) has an infinite diameter. We show that for 0 ≤i≤3g-5,two i-simplices can be connected by an(i +1)-path in C(Sg),and the diameter of C(Sg) under such a distance is infinite.     

A Classification of Regular Embeddings of Graphs of Order a Product of Two Primes

In this paper, we classify the regular embeddings of arc-transitive simple graphs of order pq for any two primes p and q (not necessarily distinct) into orientable surfaces. Our classification is obtained by direct analysis of the structure of arc-regular subgroups (with cyclic vertex-stabilizers) of the automorphism groups of such graphs. This work is independent of the classification of primitive permutation groups of degree p or degree pq for p q and it is also independent of the classification of the arc-transitive graphs of order pq for p q.     

Classification of extensions of classifiable -algebras

For a certain class of extensions of C^*-algebras in which B and A belong to classifiable classes of C^*-algebras, we show that the functor which sends to its associated six term exact sequence in K-theory and the positive cones of K₀(B) and K₀(A) is a classification functor. We give two independent applications addressing the classification of a class of C^*-algebras arising from substitutional shift spaces on one hand and of graph algebras on the other. The former application leads to the answer of a question of Carlsen and the first named author concerning the completeness of stabilized Matsumoto algebras as an invariant of flow equivalence. The latter leads to the first classification result for nonsimple graph C^*-algebras.     

Complexity of the pipeline computation of a family of inner products

We are interested in the minimum time T(S) necessary for computing a family S = { < S_i, S_j >: ? S_i, S_j?R^p, (i, j) ?E } of inner products of order p, on a systolic array of order p × 2. We first prove that the determination of T(S) is equivalent to the partition problem and is thus NP-complete. Then we show that the designing of an algorithm which runs in time T(S) + 1 is equivalent to the problem of finding an undirected bipartite eulerian multigraph with the smallest number of edges, which contains a given undirected bipartite graph, and can therefore be solved in polynomial time.     

Behavior at infinity of solutions of an equation of Osserman-Keller type

We study the behavior at infinity of solutions of equations of the form Δu=u^p, where p>1, in dimensions n?3. In particular we extend results proved by Loewner and Nirenberg in Contribution to Analysis, 1974, pp. 245-272 for the case p=(n+2)/(n−2), n?3, to values of p in the range p>n/(n−2), n?3.     

Stability of Solution of a Class of Quasilinear Elliptic Equations

In this paper, using capacity theory and extension theorem of Lipschitz functions we first discuss the uniqueness of weak solution of nonhomogeneous quasilinear elliptic equationsin space W(θ,p)(Ω), which is bigger than W1,p(Ω). Next, using revise reverse Holder inequality we prove that if ωc is uniformly p-think, then there exists a neighborhood U of p, such that for all t ∈U, the weak solutions of equation corresponding t are bounded uniformly. Finally, we get the stability of weak solutions on exponent p.     

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     

Resolutions of subsets of finite sets of points in projective space

Abstract

Eisenbud et al. proved a number of results regarding Gröbner bases and initial ideals of those ideals J in the free associative algebra K ?X ₁,…, X _n ? which contain the commutator ideal. We prove similar results for ideals which contains the anti-commutator ideal (the defining ideal of the exterior algebra). We define one weak notion of generic initial ideals in K ?X ₁,…, X _n ?, and show that generic initial ideals of ideals containing the anti-commutator ideal, or the commutator ideal, are finitely generated.     

The representations of the Drazin inverse of differences of two matrices

In this paper, we give explicit representations of (P ± Q)^D, (P ± PQ)^D and (PQ)^# of two matrices P and Q, as a function of P, Q, P^D and Q^D, under the conditions P³Q = QP and Q³P = PQ.