A characterization of k-normal varieties

Let v be a valuation of terms of type , assigning to each term t of type a value v(t) 0. Let k 1 be a natural number. An identity of type is called k-normal if either s = t or both s and t have value k, and otherwise is called non-k-normal. A variety V of type is said to be k-normal if all its identities are k-normal, and non-k-normal otherwise. In the latter case, there is a unique smallest k-normal variety to contain V , called the k-normalization of V. Inthe case k = 1, for the usual depth valuation of terms, these notions coincide with the well-known concepts of normal identity, normal variety, and normalization of a variety. I. Chajda has characterized the normalization of a variety by means of choice algebras. In this paper we generalize his results to a characterization of the k-normalization of a variety, using k-choice algebras. We also introduce the concept of a k-inflation algebra, and for the case that v is the usual depth valuation of terms, we prove that a variety V is k-normal iff it is closed under the formation of k-inflations, and that the k-normalization of V consists precisely of all homomorphic images of k-inflations of algebras in V .     

On Hong’s conjecture for power LCM matrices

A set S={x ₁,...,x _n } of n distinct positive integers is said to be gcd-closed if (x _i , x _j ) ∈ S for all 1 ⩽ i, j ⩽ n. Shaofang Hong conjectured in 2002 that for a given positive integer t there is a positive integer k(t) depending only on t, such that if n ⩽ k(t), then the power LCM matrix ([x _i , x _j ] ^t ) defined on any gcd-closed set S={x ₁,...,x _n } is nonsingular, but for n ⩾ k(t) + 1, there exists a gcd-closed set S={x ₁,...,x _n } such that the power LCM matrix ([x _i , x _j ] ^t ) on S is singular. In 1996, Hong proved k(1) = 7 and noted k(t) ⩾ 7 for all t ⩾ 2. This paper develops Hong’s method and provides a new idea to calculate the determinant of the LCM matrix on a gcd-closed set and proves that k(t) ⩾ 8 for all t ⩾ 2. We further prove that k(t) ⩾ 9 iff a special Diophantine equation, which we call the LCM equation, has no t-th power solution and conjecture that k(t) = 8 for all t ⩾ 2, namely, the LCM equation has t-th power solution for all t ⩾ 2.     

Some combinatorial constructions for optimal perfect deletion-correcting codes

There are two kinds of perfect t-deletion-correcting codes of length k over an alphabet of size v, those where the coordinates may be equal and those where all coordinates must be different. We call these two kinds of codes T*(k − t, k, v)-codes and T(k − t, k, v)-codes respectively. The cardinality of a T(k − t, k, v)-code is determined by its parameters, while T*(k − t, k, v)-codes do not necessarily have a fixed size. Let N(k − t, k, v) denote the maximum number of codewords in any T*(k − t, k, v)-code. A T*(k − t, k, v)-code with N(k − t, k, v) codewords is said to be optimal. In this paper, some combinatorial constructions for optimal T*(2, k, v)-codes are developed. Using these constructions, we are able to determine the values of N(2, 4, v) for all positive integers v. The values of N(2, 5, v) are also determined for almost all positive integers v, except for v = 13, 15, 19, 27 and 34.      

线性时滞微分方程稳定性分析和数值例子

§ 1　IntroductionFunctional differential equations have a wide range of applications in science andengineering.The simplestand perhapsmostnatural type of functional differential equationis a“delay differential equation”,that is,differential equation with dependence on the paststate.The simplest type of pastdependence is thatit is carried through the state variablebut not through its derivative.Then the equation can be expressed as delay differentialequations(DDEs) .There are also a number…     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

On signed distance-k-domination in graphs

The signed distance-k-domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G, the open k-neighborhood of v, denoted by N _k (v), is the set N _k (v) = {u: u ≠ v and d(u, v) ⩽ k}. N _k [v] = N _k (v) ⋃ {v} is the closed k-neighborhood of v. A function f: V → {−1, 1} is a signed distance-k-dominating function of G, if for every vertex . The signed distance-k-domination number, denoted by γ _k,s (G), is the minimum weight of a signed distance-k-dominating function on G. The values of γ _2,s (G) are found for graphs with small diameter, paths, circuits. At the end it is proved that γ _2,s (T) is not bounded from below in general for any tree T.     

Operator-semistable, operator semi-selfdecomposable probability measures and related nested classes on p-adic vector spaces

Let V be a finite dimensional p-adic vector space and let τ be an operator in GL(V). A probability measure μ on V is called τ-decomposable or m ? [(L)\tilde]₀(t)\mu\in {\tilde L}_0(\tau) if μ = τ(μ)* ρ for some probability measure ρ on V. Moreover, when τ is contracting, if ρ is infinitely divisible, so is μ, and if ρ is embeddable, so is μ. These two subclasses of [(L)\tilde]₀(t){\tilde L}_0(\tau) are denoted by L ₀(τ) and L ₀ ^#(τ) respectively. When μ is infinitely divisible τ-decomposable for a contracting τ and has no idempotent factors, then it is τ-semi-selfdecomposable or operator semi-selfdecomposable. In this paper, sequences of decreasing subclasses of the above mentioned three classes, [(L)\tilde]_m(t) é L_m(t) é L^#_m(t), 1 ￡ m ￡ ￥{\tilde L}_m(\tau)\supset L_m(\tau) \supset L^\#_m(\tau), 1\le m\le \infty , are introduced and several properties and characterizations are studied. The results obtained here are p-adic vector space versions of those given for probability measures on Euclidean spaces.     

Structure of lattices of varieties and lattices of quasivarieties: similarity and difference. III

We give representations for lattices of varieties and lattices of quasivarieties in terms of inverse limits of lattices satisfying a number of additional conditions. Specifically, it is proved that, for any locally finite variety (quasivariety) of algebras V, L _v(V)[resp., L _q(V)] is isomorphic to an inverse limit of a family of finite join semidistributive at 0 (resp., finite lower bounded) lattices. A similar statement is shown to hold for lattices of pseudo-quasivarieties. Various applications are offered; in particular, we solve the problem of Lampe on comparing lattices of varieties with lattices of locally finite ones. Translated fromAlgebra i Logika, Vol. 34, No. 6, pp. 646-666, November-December, 1995.     

Large deviations for heavy-tailed random sums of independent random variables with dominatedly varying tails

We prove large deviation results on the partial and random sums Sn = ∑i=1n Xi,n≥1; S(t) = ∑i=1N(t) Xi, t≥0, where {N(t);t≥0} are non-negative integer-valued random variables and {Xn;n≥1} are independent non-negative random variables with distribution, Fn, of Xn, independent of {N(t); t≥0}. Special attention is paid to the distribution of dominated variation.     

On Enomoto’s problems in a bipartite graph

In this paper, we obtain the following result: Let k, n ₁ and n ₂ be three positive integers, and let G = (V ₁,V ₂;E) be a bipartite graph with |V1| = n ₁ and |V ₂| = n ₂ such that n ₁ ⩾ 2k + 1, n ₂ ⩾ 2k + 1 and |n ₁ − n ₂| ⩽ 1. If d(x) + d(y) ⩾ 2k + 2 for every x ∈ V ₁ and y ∈ V ₂ with xy $ \notin $ \notin E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph.     

On vertex-coloring edge-weighting of graphs

A k-edge-weighting w of a graph G is an assignment of an integer weight, w(e) ∈ {1,…,k}, to each edge e. An edge-weighting naturally induces a vertex coloring c by defining c(u) = Σ _e∋u w(e) for every u ∈ V (G). A k-edge-weighting of a graph G is vertex-coloring if the induced coloring c is proper, i.e., c(u) ≠ c(v) for any edge uv ∈ E(G). When k ≡ 2 (mod 4) and k ⩾ 6, we prove that if G is k-colorable and 2-connected, δ(G) ⩾ k − 1, then G admits a vertex-coloring k-edge-weighting. We also obtain several sufficient conditions for graphs to be vertex-coloring k-edge-weighting.      

On the distribution of reducible polynomials

Let ℛ _n (t) denote the set of all reducible polynomials p(X) over ℤ with degree n ≥ 2 and height ≤ t. We determine the true order of magnitude of the cardinality |ℛ _n (t)| of the set ℛ _n (t) by showing that, as t → ∞, t ² log t ≪ |ℛ₂(t)| ≪ t ² log t and t ⁿ ≪ |ℛ _n (t)| ≪ t _n for every fixed n ≥ 3. Further, for 1 < n/2 < k < n fixed let ℛ _k,n (t) ⊂ ℛ _n (t) such that p(X) ∈ ℛ _k,n (t) if and only if p(X) has an irreducible factor in ℤ[X] of degree k. Then, as t → ∞, we always have t ^k+1 ≪ |ℛ _k,n (t)| ≪ t ^k+1 and hence |ℛ _n−1,n (t)| ≫ |ℛ _n (t)| so that ℛ _n−1,n (t) is the dominating subclass of ℛ _n (t) since we can show that |ℛ _n (t)∖ℛ _n−1,n (t)| ≪ t ⁿ⁻¹(log t)².On the contrary, if R _n ^s (t) is the total number of all polynomials in ℛ _n (t) which split completely into linear factors over ℤ, then t ²(log t) ⁿ⁻¹ ≪ R _n ^s (t) ≪ t ² (log t) ⁿ⁻¹ (t → ∞) for every fixed n ≥ 2.      

Minus total domination in graphs

A three-valued function f: V → {−1, 0, 1} defined on the vertices of a graph G= (V, E) is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every υ ∈ V, f(N(υ)) ⩾ 1, where N(υ) consists of every vertex adjacent to υ. The weight of an MTDF is f(V) = Σf(υ), over all vertices υ ∈ V. The minus total domination number of a graph G, denoted γ _t ⁻(G), equals the minimum weight of an MTDF of G. In this paper, we discuss some properties of minus total domination on a graph G and obtain a few lower bounds for γ _t ⁻(G).     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

An equivalence between varieties of cyclic Post algebras and varieties generated by a finite field

In this paper we give a term equivalence between the simple k-cyclic Post algebra of order p, L _p,k, and the finite field F(p ^k) with constants F(p). By using Lagrange polynomials, we give an explicit procedure to obtain an interpretation Φ₁ of the variety V(L _p,k) generated by L _p,k into the variety V(F(p ^k)) generated by F(p ^k) and an interpretation Φ₂ of V(F(p ^k)) into V(L _p,k) such that Φ₂Φ₁(B) = B for every B ε V(L _p,k) and Φ₁Φ₂(R) = R for every R ε V(F(p ^k)).     

Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs

Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {s_i, t_i}⊆X_i⊆V(G) (i=1,2) and X₁∩X₂=∅. We here prove that if k is even and e(X_i)≤2k−1 (i=1,2), then there exist paths P₁ and P₂ such that P_i joins s_i and t_i, V(P_i)⊆X_i (i=1,2) and G − E(P₁∪P₂) is (k−2)-edge-connected (for odd k, if e(X₁)≤2k−2 and e(X₂)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.     

The <Emphasis Type="Italic">k</Emphasis>-point exponent set of primitive digraphs with girth 2

Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu, we order the vertices of D so that exPD（V1） ≤ exPD（V2） …≤ exPD（Vn）. Then exPD（Vk） is called the k- point exponent of D and is denoted by exPD （k）, 1≤ k ≤ n. In this paper we define e（n, k） ：= max{expD （k） ｜ D ∈ PD（n, 2）} and E（n, k） ：= {exPD（k）｜ D ∈ PD（n, 2）}, where PD（n, 2） is the set of all primitive digraphs of order n with girth 2. We completely determine e（n, k） and E（n, k） for all n, k with n ≥ 3 and 1 ≤ k ≤ n.     

Covering arrays of strength 3 and 4 from holey difference matrices

A covering array CA(N; t, k, v) is an N × k array with entries from a set X of v symbols such that every N × t sub-array contains all t-tuples over X at least once, where t is the strength of the array. The minimum size N for which a CA(N; t, k, v) exists is called the covering array number and denoted by CAN(t, k, v). Covering arrays are used in experiments to screen for interactions among t-subsets of k components. One of the main problems on covering arrays is to construct a CA(N; t, k, v) for given parameters (t, k, v) so that N is as small as possible. In this paper, we present some constructions of covering arrays of strengths 3 and 4 via holey difference matrices with prescribed properties. As a consequence, some of known bounds on covering array number are improved. In particular, it is proved that (1) CAN(3, 5, 2v) ≤ 2v ²(4v + 1) for any odd positive integer v with gcd(v, 9) ≠ 3; (2) CAN(3, 6, 6p) ≤ 216p ³ + 42p ² for any prime p > 5; and (3) CAN(4, 6, 2p) ≤ 16p ⁴ + 5p ³ for any prime p ≡ 1 (mod 4) greater than 5.     

Hyperidentities and solid varieties

Let V be a variety of type τ. A type τ hyperidentity of V is an identity of V which also holds in an additional stronger sense: for every substitution of terms of the variety (of appropriate arity) for the operation symbols in the identity, the resulting equation holds as an identity of the variety. Such identities were first introduced by Walter Taylor in [27] in 1981. A variety is called solid if all its identities also hold as hyperidentities. For example, the semigroup variety of rectangular bands is a solid variety. For any fixed type τ, the collection of all solid varieties of type τ forms a complete lattice which is a sublattice of the lattice L(τ) of all varieties of type τ. In this paper we give an overview of the study of hyperidentities and solid varieties, particularly for varieties of semigroups, culminating in the construction of an infinite collection of solid varieties of arbitrary type. This paper is dedicated to Walter Taylor. Received July 16, 2005; accepted in final form January 3, 2006. This paper is an expanded version of a talk presented at the Conference on Algebras, Lattices and Varieties in Honour of Walter Taylor, in Boulder Colorado, August 2004. The author’s research is supported by NSERC of Canada.     

An additive divisor problem with a growing number of factors

Let τk(n) be the number of representations ofn as the product ofk positive factors, τ(n)=τ(n). The asymptotics of Σ _n≤x τ _k (n)τ(n+1) for 80k ¹⁰ (lnlnx)³≤lnx is shown to be uniform with respect tok. Translated fromMatematicheskie Zametki, Vol. 61, No. 3, pp. 391–406, March, 1997. Translated by N. K. Kulman