On the order of certain close to regular graphs without a matching of given size

A graph G is a {d, d+k}-graph, if one vertex has degree d+k and the remaining vertices of G have degree d. In the special case of k = 0, the graph G is d-regular. Let k, p ⩾ 0 and d, n ⩾ 1 be integers such that n and p are of the same parity. If G is a connected {d, d+k{-graph of order n without a matching M of size 2|M| = n − p, then we show in this paper the following: If d = 2, then k ⩾ 2(p + 2) and

Symmetry of iteration graphs

We examine iteration graphs of the squaring function on the rings ℤ/nℤ when n = 2 ^k p, for p a Fermat prime. We describe several invariants associated to these graphs and use them to prove that the graphs are not symmetric when k = 3 and when k ⩾ 5 and are symmetric when k = 4.     

Repelling periodic points of given periods of rational functions

Let R(z) be a rational function of degree d≥2. Then R(z) has at least one repelling periodic point of given period k≥2, unless k = 4 and d = 2, or k = 3 and d≤3, or k = 2 and d≤8. Examples show that all exceptional cases occur.     

<Emphasis Type="Italic">k</Emphasis>-Free-like groups

The following results are proved. In Theorem 1, it is stated that there exist both finitely presented and not finitely presented 2-generated nonfree groups which are k-free-like for any k ⩾ 2. In Theorem 2, it is claimed that every nonvirtually cyclic (resp., noncyclic and torsion-free) hyperbolic m-generated group is k-free-like for every k ⩾ m + 1 (resp., k ⩾ m). Finally, Theorem 3 asserts that there exists a 2-generated periodic group G which is k-free-like for every k ⩾ 3. Supported by NSF (grant Nos. DMS 0455881 and DMS-0700811). (A. Yu. Olshanskii, M. V. Sapir) Supported by RFBR project No. 08-01-00573. (A. Yu. Olshanskii) Supported by BSF grant (USA–Israel). (M. V. Sapir) Translated from Algebra i Logika, Vol. 48, No. 2, pp. 245–257, March–April, 2009.     

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.     

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.     

Further results on ultraconvergence derivative recovery for odd-order rectangular finite elements

For rectangular finite element, we give a superconvergence method by SPR technique based on the generalization of a new ultraconvergence record and the sharp Green function estimates, by which we prove that the derivative has ultra-convergence of order O(h ^k+3) (k ⩾ 3 being odd) and displacement has order of O(h ^k+4) (k ⩾ 4 being even) at the locally symmetry points.      

On thek dimensional Piatetski-Shapiro prime number theorem

Thek-dimensional Piatetski-Shapiro prime number problem fork⩾3 is studied. Let π(x ₁ c ₁,⋯,c _k ) denote the number of primesp withp⩽x, , where 1<c ₁<⋯<c _k are fixed constants. It is proved that π(x;c ₁,⋯,c _k ) has an asymptotic formula ifc ₁ ⁻¹ +⋯+c _k ⁻¹ >k−k/(4k ²+2). Project supported by the National Natural Science Foundation of China (Grant No. 19801021) and the Natural Science Foundation of Shandong Province (Grant No.Q98A02110).     

Scheduling strategies and long-range dependence

Consider a single server queue with unit service rate fed by an arrival process of the following form: sessions arrive at the times of a Poisson process of rate λ, with each session lasting for an independent integer time τ ⩾ 1, where P(τ = k) = p _k with p _k ~ αk ^−(1+α) L(k), where 1 < α < 2 and L(·) is a slowly varying function. Each session brings in work at unit rate while it is active. Thus the work brought in by each arrival is regularly varying, and, because 1 < α < 2, the arrival process of work is long-range dependent. Assume that the stability condition λE[τ] < 1 holds. By simple arguments we show that for any stationary nonpreemptive service policy at the queue, the stationary sojourn time of a typical session must stochastically dominate a regularly varying random variable having infinite mean; this is true even if the duration of a session is known at the time it arrives. On the other hand, we show that there exist causal stationary preemptive policies, which do not need knowledge of the session durations at the time of arrival, for which the stationary sojourn time of a typical session is stochastically dominated by a regularly varying random variable having finite mean. These results indicate that scheduling policies can have a significant influence on the extent to which long-range dependence in the arrivals influences the performance of communication networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Diameter and diametrical pairs of points in ultrametric spaces

Let F(X) be the set of finite nonempty subsets of a set X. We have found the necessary and sufficient conditions under which for a given function τ: F(X) → ℝ there is an ultrametric on X such that τ(A) = diamA for every A ∈ F(X). For finite nondegenerate ultrametric spaces (X, d) it is shown that X together with the subset of diametrical pairs of points of X forms a complete k-partite graph, k ⩾ 2, and, conversely, every finite complete k-partite graph with k ⩾ 2 can be obtained by this way. We use this result to characterize the finite ultrametric spaces (X, d) having the minimal card{(x, y): d(x, y) = diamX, x, y ∈ X} for given card X.     

A [k,k+1]-factor containing given Hamiltonian cycle

Letk⩾2 be an integer and let G be a graph of ordern with minimum degree at leastk, n⩾8k -16 for evenn and n⩾6k - 13 for oddn. If the degree sum of each pair of nonadjacent vertices of G is at least n, then for any given Hamiltonian cycleC. G has a [k, k + 1]-factor containingC Preject supported partially by an exchange program between the Chinese Academy of Sciences and the Japan Society for Promotion of Sciences and by the National Natural Science Foundation of China (Grant No. 19136012)     

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.      

DEGREE CONDITIONS OF INDUCED MATCHING EXTENDABLE GRAPHS

Abstract. A simple graph G is induced matching extendable,shortly IM-extendable,if every in-duced matching of G is included in a perfect matching of G. The degree conditions of IM-extend-able graphs are researched in this paper. The main results are as follows：     

2-Normalization of lattices

Let τ be a type of algebras. A valuation of terms of type τ is a function v assigning to each term t of type τ a value v(t) ⩾ 0. For k ⩾ 1, an identity s ≈ t of type τ is said to be k-normal (with respect to valuation v) if either s = t or both s and t have value ⩾ k. Taking k = 1 with respect to the usual depth valuation of terms gives the well-known property of normality of identities. A variety is called k-normal (with respect to the valuation v) if all its identities are k-normal. For any variety V, there is a least k-normal variety N _k (V) containing V, namely the variety determined by the set of all k-normal identities of V. The concept of k-normalization was introduced by K. Denecke and S. L. Wismath in their paper (Algebra Univers., 50, 2003, pp.107–128) and an algebraic characterization of the elements of N _k (V) in terms of the algebras in V was given in (Algebra Univers., 51, 2004, pp. 395–409). In this paper we study the algebras of the variety N ₂(V) where V is the type (2, 2) variety L of lattices and our valuation is the usual depth valuation of terms. We introduce a construction called the 3-level inflation of a lattice, and use the order-theoretic properties of lattices to show that the variety N ₂(L) is precisely the class of all 3-level inflations of lattices. We also produce a finite equational basis for the variety N ₂(L). This research was supported by Research Project MSM6198959214 of the Czech Government and by NSERC of Canada.     

Linear isometries of Hardy spaces

According to results established by DeLeeuw-Rudin-Wermer and by Forelli,all linear isometries of any Hardy space H~p(p≥1,p≠2)on the open unit discΔof C are represented by weighted composition operators defined by inner functions onΔ.After reviewing(and completing when p=∞)some of those results,the present report deals with a characterization of periodic and almost periodic semigroups of linear isometries of H~p.     

A classification of some regular p-groups and its applications

In this paper we classify regular p-groups with type invariants (e/it, 1, 1, 1) for e⩾2 and (1, 1, 1, 1, 1). As a by-product, we give a new approach to the classification of groups of order p ⁵, p⩾5 a prime.     

On extremal sizes of locally k-tree graphs

A graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k ⩾ 0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k ⩾ 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n-vertex locally k-tree graph is between Ω(n) and O(n ²), where both bounds are asymptotically tight. In contrast, the number of edges in an n-vertex k-tree is always linear in n.     

Moment inequalities and weak convergence for negatively associated sequences

A probability inequality for S_n and somepth moment (p⩾2) inequalities for |S_n| and max 1⩽k⩽n | S_k| are established. Here S_n is the partial sum of a negatively associated sequence. Based on these inequalities, a weak invariance principle for strictly stationary negatively associated sequences is proved under some general conditions. Project supported by the National Natural Science Foundation of China, the Doctoral Program Foundation of the State Education Commission of China and the High Eductional Natural Science Foundation of Guangdong Province.     

An extension of the Hoeffding inequality to unbounded random variables

Let S = X ₁ + ⋯ + X _n be a sum of independent random variables such that 0 ⩽ X _k ⩽ 1 for all k. Write p = E S/n and q = 1 − p. Let 0 < t < q. In this paper, we extend the Hoeffding inequality [16, Theorem 1]

The number of powers of 2 in a representation of large even integers (I)

Under the Generalized Riemann Hypothesis, it is proved that for any integer k⩾770 there is N_k>0 depending onk only such that every even integer ⩾N_k is a sum of two odd prime numbers andk powers of 2. The research is partially supported by RGC research grant (HKU 518/96P). The first author is supported by Post-Doctoral Fellowship of The University of Hong Kong.