The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

Decomposition of bipartite graphs into closed trails

Let Lct(G) denote the set of all lengths of closed trails that exist in an even graph G. A sequence (t ₁,..., t _p ) of elements of Lct(G) adding up to |E(G)| is G-realisable provided there is a sequence (T ₁,..., t _p ) of pairwise edge-disjoint closed trails in G such that T _i is of length T _i for i = 1,..., p. The graph G is arbitrarily decomposable into closed trails if all possible sequences are G-realisable. In the paper it is proved that if a ⩾ 1 is an odd integer and M _a,a is a perfect matching in K _a,a , then the graph K _a,a -M _a,a is arbitrarily decomposable into closed trails.      

Decomposition of Complete Bipartite Even Graphs into Closed Trails

We prove that any complete bipartite graph K _a,b , where a, b are even integers, can be decomposed into closed trails with prescribed even lengths.     

Decompositions of Km,n into cubes

For a complete bipartite graph to be decomposable into isomorphic cubes, certain conditions on the number of cube and bipartition vertices must hold. We prove these necessary conditions sufficient in some cases. For cubes of fixed dimension d (indeed for d-regular bipartite graphs in general) we show that proving sufficiency can be reduced to decomposing a finite number of complete bipartite graphs. When t = 2^d−1 and r is the remainder on dividing t by d, we show K_t,t is decomposable into d-cubes and an r-factor, where if r > 0 this r-factor itself is decomposable into r-cubes. © 1996 John Wiley & Sons, Inc.     

Commuting decompositions of complete graphs

We say that two graphs G and H with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number r, the complete multigraph K is decomposable into commuting perfect matchings if and only if n is a 2‐power. Also, it is shown that the complete graph K_n is decomposable into commuting Hamilton cycles if and only if n is a prime number. © 2006 Wiley Periodicals, Inc. J Combin Designs     

An elementary approach to gap theorems

Using elementary comparison geometry, we prove: Let (M, g) be a simply-connected complete Riemannian manifold of dimension ≥ 3. Suppose that the sectional curvature K satisfies −1 − s(r) ≤ K ≤ −1, where r denotes distance to a fixed point in M. If lim _{r → ∞} e^2r s(r) = 0, then (M, g) has to be isometric to ℍ ⁿ . The same proof also yields that if K satisfies −s(r) ≤ K ≤ 0 where lim _{r → ∞} r ² s(r) = 0, then (M, g) is isometric to ℝ ⁿ , a result due to Greene and Wu. Our second result is a local one: Let (M, g) be any Riemannian manifold. For a ∈ ℝ, if K ≤ a on a geodesic ball B _p (R) in M and K = a on ∂B _p (R), then K = a on B _p (R).     

On the essential dimension of cyclic <Emphasis Type="Italic">p</Emphasis>-groups

Let p be a prime number, let K be a field of characteristic not p, containing the p-th roots of unity, and let r≥1 be an integer. We compute the essential dimension of ℤ/p ^r ℤ over K (Theorem 4.1). In particular, i) We have ed_ℚ(ℤ/8ℤ)=4, a result which was conjectured by Buhler and Reichstein in 1995 (unpublished). ii) We have ed_ℚ(ℤ/p ^r ℤ)≥p ^r-1.     

Density results in the Δ20 e-degrees

We show that the Δ⁰ ₂ enumeration degrees are dense. We also show that for every nonzero n-c. e. e-degree a, with n≥ 3, one can always find a nonzero 3-c. e. e-degree b such that b < a on the other hand there is a nonzero ωc. e. e-degree which bounds no nonzero n-c. e. e-degree. Received: 13 June 2000 / Published online: 3 October 2001     

Almost poised basic hypergeometric series

Given a basic hypergeometric series with numerator parametersa ₁,a ₂, ...,a _r and denominator parametersb ₂, ...,b _r, we say it isalmost poised ifb _i, =a ₁ q ^δ,i a _i,δ_i = 0, 1 or 2, for 2 ≤i ≤r. Identities are given for almost poised series withr = 3 andr = 5 when a₁, =q ⁻²ⁿ. Partially supported by N.S.F. Grant No. DMS-8521580.     

Propertyf −1(S) =g −1(S) for entire and meromorphicP-adic functions

LetW be an algebraically closed filed of characteristic zero, letK be an algebraically closed field of characteristic zero, complete for an ultrametric absolute value, and letA(K) (resp. ℳ(K)) be the set of entire (resp. meromorphic) functions inK. For everyn≥7, we show that the setS _n(b) of zeros of the polynomialx ⁿ−b (b≠0) is such that, iff, g ∈W[x] or iff, g ∈A(K), satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), thenf ⁿ=g ⁿ. For everyn≥14, we show thatS _n(b) is such that iff, g ∈W({tx}) or iff, g ∈ ℳ(K) satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), then eitherf ⁿ=g ⁿ, orfg is a constant. Analogous properties are true for complex entire and meromorphic functions withn≥8 andn≥15, respectively. For everyn≥9, we show that the setY _n(c) of zeros of the polynomial , (withc≠0 and 1) is an ursim ofn points forW[x], and forA(K). For everyn≥16, we show thatY _n(c) is an ursim ofn points forW(x), and for ℳ(K). We follow a method based on thep-adic Nevanlinna Theory and use certain improvement of a lemma obtained by Frank and Reinders.     

Diagonal equations over function fields

LetK be a function field in one variable over ℂ anda ₁,...,a _m ,b non-zero elements ofK, such thatb is linearly independent froma ₁,...,a _m over ℂ. We show that forn sufficiently large, the equation ∑ _i=1 ^m a _i x _i ⁿ has no non-constant solutions inK.     

An inequality for Tutte polynomials

Let G be a graph without loops or bridges and a, b be positive real numbers with b ≥ a(a+2). We show that the Tutte polynomial of G satisfies the inequality T _G (b, 0)T _G (0, b) ≥ T _G (a, a)². Our result was inspired by a conjecture of Merino and Welsh that T _G (1, 1) ≤ max{T _G (2, 0),T _G (0, 2)}.     

On the Terai-Jésmanowicz conjecture

In this paper, we prove that if a, b and c are pairwise coprime positive integers such that a^2＋b^2=c^r,a〉b,a≡3 （mod4）,b≡2 （mod4） and c-1 is not a square, thena a^x＋b^y=c^z has only the positive integer solution （x, y, z） = （2, 2, r）.
Let m and r be positive integers with 2｜m and 2 r, define the integers Ur, Vr by （m ＋√-1）^r=Vr＋Ur√-1. If a = ｜Ur｜,b=｜Vr｜,c = m^2＋1 with m ≡ 2 （mod 4）,a ≡ 3 （mod 4）, and if r 〈 m/√1.5log3（m^2＋1）-1, then a^x ＋ b^y = c^z has only the positive integer solution （x,y, z） = （2, 2, r）. The argument here is elementary.     

On the Hamilton-Waterloo Problem

 The Hamilton-Waterloo problem asks for a 2-factorisation of K _v in which r of the 2-factors consist of cycles of lengths a ₁,a ₂,…,a _t and the remaining s 2-factors consist of cycles of lengths b ₁,b ₂,…,b _u (where necessarily ∑ _i=1 ^t a _i =∑ _j=1 ^u b _j =v). In this paper we consider the Hamilton-Waterloo problem in the case a _i =m, 1≤i≤t and b _j =n, 1≤j≤u. We obtain some general constructions, and apply these to obtain results for (m,n)∈{(4,6),(4,8),(4,16),(8,16),(3,5),(3,15),(5,15)}. Received: July 5, 2000     

The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences

Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.     

Finiteness properties of minimax and coatomic local cohomology modules

Let R be a noetherian ring, \mathfraka{\mathfrak{a}} an ideal of R, and M an R-module. We prove that for a finite module M, if Hⁱ_\mathfraka(M){{\rm H}^{i}_{\mathfrak{a}}(M)} is minimax for all i ≥ r ≥ 1, then Hⁱ_\mathfraka(M){{\rm H}^{i}_{\mathfrak{a}}(M)} is artinian for i ≥ r. A local–global principle for minimax local cohomology modules is shown. If Hⁱ_\mathfraka(M){{\rm H}^{i}_{\mathfrak{a}}(M)} is coatomic for i ≤ r (M finite) then Hⁱ_\mathfraka(M){{\rm H}^{i}_{\mathfrak{a}}(M)} is finite for i ≤ r. We give conditions for a module which is locally minimax to be a minimax module. A non-vanishing theorem and some vanishing theorems are proved for local cohomology modules.     

On the difference between the number of prime divisors at consecutive integers

Suppose thatg(n) is equal to the number of divisors ofn, counting multiplicity, or the number of divisors ofn, a≠0 is an integer, andN(x,b)=|{n∶n≤x, g(n+a)−g(n)=b orb+1}|. In the paper we prove that sup _b N(x,b)≤C(a)x)(log log 10 _x )^−1/2 and that there exists a constantC(a,μ)>0 such that, given an integerb |b|≤μ(log logx)^1/2,x≥x _o, the inequalityN(x,b)≥C(a,μ)x(log logx(^−1/2) is valid. Translated fromMatematicheskie Zametki, Vol. 66, No. 4, pp. 579–595, October, 1999.     

Cryptosystems based on semi-distributive algebras

We propose a new cryptographic scheme of ElGamal type. The scheme is based on algebraic systems defined in the paper—semialgebras (Sect. 2). The main examples are semialgebras of polynomial mappings over a finite field K, and their factor-semialgebras. Given such a semialgebra R, one chooses an invertible element a ∈ R ^* of finite order r, and a random integer s. One chooses also a finite dimensional K-submodule V of R. The 4-tuple (R, V, a, b) where b = a ^s forms the public key for the cryptosystem, while r and s form the secret key. A plain text can be viewed as a sequence of elements of the field K. That sequence is divided into blocks of length dim(V) which, in turn, correspond to uniquely determined elements X _i of V. We propose three different methods (A, B, and C, see Definition 1.1) of encoding/decoding the sequence of X _i . The complexity of cracking the proposed cryptosystem is based on the Discrete Logarithm Problem for polynomial mappings (see Sect. 1.1). No methods of cracking the problem, except for the “brute force” (see Sect. 1.1) with Ω(r) time, are known so far.      

Limiting angles of Γ-martingales

Suppose that M is a complete, simply connected Riemannian manifold of non-positive sectional curvature with dimension m≥ 3 and that, outside a fixed compact set, the sectional curvatures are bounded above by −c ₁/{r ² ln r} and below by −c ₂ r ², where c ₁ and c ₂ are two positive constants and r is the geodesic distance from a fixed point. We show that, when κ≥ 1 satisfies certain conditions, the angular part of a κ-quasi-conformal Γ-martingale on M tends to a limit as time tends to infinity and the closure of the support of the distribution of this limit is the entire sphere at infinity. This improves both a result of Le for Brownian motion and also results concerning the non-existence of κ-quasi-conformal harmonic maps from certain types of Riemannian manifolds into M. Received: 19 September 1997     

On the generalization of the D. H. Lehmer problem

Let n ≥ 2 be a fixed positive integer, q ≥ 3 and c be two integers with （n, q） = （c, q） = 1. We denote by rn（51, 52, C; q） （δ 〈 δ1,δ2≤ 1） the number of all pairs of integers a, b satisfying ab ≡ c（mod q）, 1 〈 a ≤δ1q, 1 ≤ b≤δ2q, （a,q） = （b,q） = 1 and nt（a＋b）. The main purpose of this paper is to study the asymptotic properties of rn （δ1, δ2, c; q）, and give a sharp asymptotic formula for it.