A method of finding automorphism groups of endomorphism monoids of relational systems

For any set X and any relation ρ on X, let T(X,ρ) be the semigroup of all maps a:X→X that preserve ρ. Let S(X) be the symmetric group on X. If ρ is reflexive, the group of automorphisms of T(X,ρ) is isomorphic to N_S(X)(T(X,ρ)), the normalizer of T(X,ρ) in S(X), that is, the group of permutations on X that preserve T(X,ρ) under conjugation. The elements of N_S(X)(T(X,ρ)) have been described for the class of so-called dense relations ρ. The paper is dedicated to applications of this result.     

On the computation of the hull number of a graph

Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted I_h[S], is the smallest convex set containing S. A set S is a hull set of G if I_h[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph.     

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

Coincidences of projections and linear n-valued maps of tori

We prove that the Nielsen fixed point number N(φ) of an n-valued map φ:X?X of a compact connected triangulated orientable q-manifold without boundary is equal to the Nielsen coincidence number of the projections of the graph of φ, a subset of X×X, to the two factors. For certain q×q integer matrices A, there exist “linear” n-valued maps Φn,A,σ:Tq?Tq of q-tori that generalize the single-valued maps fA:Tq→Tq induced by the linear transformations TA:Rq→Rq defined by TA(v)=Av. By calculating the Nielsen coincidence number of the projections of its graph, we calculate N(Φn,A,σ) for a large class of linear n-valued maps.     

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.     

Degree-bounded factorizations of bipartite multigraphs and of pseudographs

For d≥1, s≥0 a (d,d+s)-graph is a graph whose degrees all lie in the interval {d,d+1,…,d+s}. For r≥1, a≥0 an (r,r+a)-factor of a graph G is a spanning (r,r+a)-subgraph of G. An (r,r+a)-factorization of a graph G is a decomposition of G into edge-disjoint (r,r+a)-factors. A graph is (r,r+a)-factorable if it has an (r,r+a)-factorization.We prove a number of results about (r,r+a)-factorizations of (d,d+s)-bipartite multigraphs and of (d,d+s)-pseudographs (multigraphs with loops permitted). For example, for t≥1 let β(r,s,a,t) be the least integer such that, if d≥β(r,s,a,t) then every (d,d+s)-bipartite multigraph G is (r,r+a)-factorable with x(r,r+a)-factors for at least t different values of x. Then we show that

     

Characterization of a class of bivariate distribution functions

Let F_X,Y(x,y) be a bivariate distribution function and P_n(x), Q_m(y), n, m = 0, 1, 2,…, the orthonormal polynomials of the two marginal distributions F_X(x) and F_Y(y), respectively. Some necessary conditions are derived for the co-efficients c_n, n = 0, 1, 2,…, if the conditional expectation E[P_n(X) ∥ Y] = c_nQ_n(Y) holds for n = 0, 1, 2,…. Several examples are given to show the application of these necessary conditions.     

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

Extensions of a theorem of Cauchy-Liouville

We deal with the equations Δpu+f(u)=0 and Δpu+(p−1)g(u)p|∇u|+f(u)=0 in RN, where g(t) is a continuous function in (0,∞), p>1 and f(t) is a smooth function for t>0. Under appropriate conditions on g and f we show that the corresponding equation cannot have nontrivial non-negative entire solutions.     

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.     

List coloring of Cartesian products of graphs

A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χ_l(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χ_l(G) and χ_l(H). On the other hand, we prove that χ_l(G×H)?min{χ_l(G)+col(H),col(G)+χ_l(H)}-1 and construct examples of graphs G and H for which our bound is tight.     

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.     

Well-posedness of a class of perturbed optimization problems in Banach spaces

Let X be a Banach space and Z a nonempty subset of X. Let J:Z→R be a lower semicontinuous function bounded from below and p?1. This paper is concerned with the perturbed optimization problem of finding z₀∈Z such that ‖x−z₀p^‖+J(z₀)=infz∈Z{‖x−zp^‖+J(z)}, which is denoted by minJ(x,Z). The notions of the J-strictly convex with respect to Z and of the Kadec with respect to Z are introduced and used in the present paper. It is proved that if X is a Kadec Banach space with respect to Z and Z is a closed relatively boundedly weakly compact subset, then the set of all x∈X for which every minimizing sequence of the problem minJ(x,Z) has a converging subsequence is a dense Gδ-subset of X?Z₀, where Z₀ is the set of all points z∈Z such that z is a solution of the problem minJ(z,Z). If additionally p>1 and X is J-strictly convex with respect to Z, then the set of all x∈X for which the problem minJ(x,Z) is well-posed is a dense Gδ-subset of X?Z₀.     

Some representations of solutions of elliptic equations

The Dirichlet problem for the region of the plane inside closed smooth curve C for second-order elliptic equations is considered. It is shown that under certain circumstances the solution u can be written uniquely in the form u(P) = ∝_cF(P, Q) g(Q) ds_Q, where F(P, Q) is the fundamental solution of the elliptic equation, and g?L² if the boundary value function f is absolutely continuous with square integrable derivative (f?W); and u(P) = p(F(P, ·)) where p is a unique bounded linear functional on W if f?L². These representations are valid in the exterior of C also. As special cases with slight modifications, the exterior Dirichlet problems for the Helmholtz and Laplace equations are mentioned.It is shown also that if kernel F(P′, Q), with P′ and Q on C, has a complete set of eigenfunctions {ψ_k(P′)} then u(P) can be expanded in a series of their extensions {ψ_k(P)}, where ψ_k(P) = λ_k ∝_cF(P, Q) ψ_k(Q) ds_Q.     

Continuity of iteration and approximation of iterative roots

Motivated by computing iterative roots for general continuous functions, in this paper we prove the continuity of the iteration operators T_n, defined by T_nf=fⁿ. We apply the continuity and introduce the concept of continuity degree to answer positively the approximation question: If lim_m→∞F_m=F, can we find an iterative root f_m of F_m of order n for each m∈N such that the sequence (f_m) tends to the iterative root of F of order n associated with a given initial function? We not only give the construction of such an approximating sequence (f_m) but also illustrate the approximation of iterative roots with an example. Some remarks are presented in order to compare our approximation with the Hyers-Ulam stability.     

Maps preserving peripheral spectrum of Jordan semi-triple products of operators

Let A and B be (not necessarily unital or closed) standard operator algebras on complex Banach spaces X and Y, respectively. For a bounded linear operator A on X, the peripheral spectrum σ_π(A) of A is the set σ_π(A)={z∈σ(A):|z|=max_ω∈σ(A)|ω|}, where σ(A) denotes the spectrum of A. Assume that Φ:A→B is a map the range of which contains all operators of rank at most two. It is shown that the map Φ satisfies the condition that σ_π(BAB)=σ_π(Φ(B)Φ(A)Φ(B)) for all A,B∈A if and only if there exists a scalar λ∈C with λ³=1 and either there exists an invertible operator T∈B(X,Y) such that Φ(A)=λTAT^-1 for every A∈A; or there exists an invertible operator T∈B(X^∗,Y) such that Φ(A)=λTA^∗T^-1 for every A∈A. If X=H and Y=K are complex Hilbert spaces, the maps preserving the peripheral spectrum of the Jordan skew semi-triple product BA^∗B are also characterized. Such maps are of the form A?UAU^∗ or A?UA^tU^∗, where U∈B(H,K) is a unitary operator, A^t denotes the transpose of A in an arbitrary but fixed orthonormal basis of H.     

Construction of determinantal representation of trigonometric polynomials

For a pair of n×n Hermitian matrices H and K, a real ternary homogeneous polynomial defined by F(t,x,y)=det(tI_n+xH+yK) is hyperbolic with respect to (1,0,0). The Fiedler conjecture (or Lax conjecture) is recently affirmed, namely, for any real ternary hyperbolic polynomial F(t,x,y), there exist real symmetric matrices S₁ and S₂ such that F(t,x,y)=det(tI_n+xS₁+yS₂). In this paper, we give a constructive proof of the existence of symmetric matrices for the ternary forms associated with trigonometric polynomials.     

On the determination of the basin of attraction of a periodic orbit in two-dimensional systems

We consider the general nonlinear differential equation with x∈R² and develop a method to determine the basin of attraction of a periodic orbit. Borg's criterion provides a method to prove existence, uniqueness and exponential stability of a periodic orbit and to determine a subset of its basin of attraction. In order to use the criterion one has to find a function W∈C¹(R²,R) such that LW(x)=W^′(x)+L(x) is negative for all x∈K, where K is a positively invariant set. Here, L(x) is a given function and W^′(x) denotes the orbital derivative of W. In this paper we prove the existence and smoothness of a function W such that LW(x)=−μ‖f(x)‖. We approximate the function W, which satisfies the linear partial differential equation W^′(x)=〈∇W(x),f(x)〉=−μ‖f(x)‖−L(x), using radial basis functions and obtain an approximation w such that Lw(x)<0. Using radial basis functions again, we determine a positively invariant set K so that we can apply Borg's criterion. As an example we apply the method to the Van-der-Pol equation.     

Certain sufficient conditions of uniformity for systems of functions of many-valued logic

For any finite system A of functions of the k-valued logic taking values in the set E _s = {0,1,…, s ? 1}, k ≥ s ≥ 2, such that the closed class generated by restriction of functions from A on the set E _s contains a near-unanimity function, it is proved that there exist constants c and d such that for an arbitrary function f ∈ [A] the depth D _A (f) and the complexity L _A (f) of f in the class of formulas over A satisfy the relation D _A (f) ≤ clog₂ L _A (f) + d.