On a cardinal group invariant related to decompositions of Abelian groups

For each Abelian groupG, a cardinal invariant χ(G) is introduced and its properties are studied. In the special caseG = ℤ ⁿ , the cardinalχ(ℤ ⁿ ) is equal to the minimal cardinality of an essential subset of ℤ ⁿ , i.e., a of a subsetA ⊂ ℤ ⁿ such that, for any coloring of the group ℤ ⁿ inn colors, there exists an infinite one-color subset that is symmetric with respect to some pointα ofA. The estimaten( ^{n +} l)/2 ≤χ(ℤ ⁿ ) < 2n is proved for alln and the relationχ(ℤ ⁿ ) =n(n + 1)/2 forn ≤ 3. The structure of essential subsets of cardinalityχ(ℤ ⁿ ) in ℤ ⁿ is completely described forn ≤ 3. Translated fromMatematicheskie Zametki, Vol. 64, No. 3, pp. 341–350, September, 1998.     

Some zero-sum constants with weights

For an abelian group G, the Davenport constant D(G) is defined to be the smallest natural number k such that any sequence of k elements in G has a nonempty subsequence whose sum is zero (the identity element). Motivated by some recent developments around the notion of Davenport constant with weights, we study them in some basic cases. We also define a new combinatorial invariant related to (ℤ/nℤ) ^d , more in the spirit of some constants considered by Harborth and others and obtain its exact value in the case of (ℤ/nℤ)² where n is an odd integer.     

Decrease rate of the probabilities ofε-deviations for the means of stationary processes

The asymptotic behavior asn → ∞ of the normed sumsσn =n ⁻¹ Σ _k ⁼⁰ⁿ⁻¹ Xk for a stationary processX = (X _n ,n ∈ ℤ) is studied. For a fixedε > 0, upper estimates for P(sup _k≥n |σ _k | ≥ε) asn → ∞ are obtained. Translated fromMatematicheskie Zametki, Vol. 64, No. 3, pp. 366–372, September, 1998.     

Cobordism independence of Grassmann manifolds

This note proves that, forF = ℝ, ℂ or ℍ, the bordism classes of all non-bounding Grassmannian manifoldsG _k(F ^n+k), withk <n and having real dimensiond, constitute a linearly independent set in the unoriented bordism group N _d regarded as a ℤ₂-vector space.     

On exactlym times covers

In this paper it is shown that if every integer is covered bya ₁+n ₁ℤ,…,a _k +n _k ℤ exactlym times then for eachn=1,…,m there exist at least ( _n ^m ) subsetsI of {1,…k} such that ∑ _{i ∈ I} 1/n _i equalsn. The bound ( _n ^m ) is best possible. Research supported by the National Nature Science Foundation of P.R. of China.     

Sum Complexes—a New Family of Hypertrees

A k-dimensional hypertree X is a k-dimensional complex on n vertices with a full (k−1)-dimensional skeleton and \binomn-1k\binom{n-1}{k} facets such that H _k (X;ℚ)=0. Here we introduce the following family of simplicial complexes. Let n,k be integers with k+1 and n relatively prime, and let A be a (k+1)-element subset of the cyclic group ℤ _n . The sum complex X _A is the pure k-dimensional complex on the vertex set ℤ _n whose facets are σ⊂ℤ _n such that |σ|=k+1 and ∑ _x∈σ x∈A. It is shown that if n is prime, then the complex X _A is a k-hypertree for every choice of A. On the other hand, for n prime, X _A is k-collapsible iff A is an arithmetic progression in ℤ _n .     

On the pontryagin-steenrod-wu theorem

We present a short and direct proof (based on the Pontryagin-Thom construction) of the following Pontryagin-Steenrod-Wu theorem: (a) LetM be a connected orientable closed smooth (n + 1)-manifold,n≥3. Define the degree map deg: π ⁿ (M) →H ⁿ (M; ℤ) by the formula degf =f*[S ⁿ ], where [S ⁿ ] εH ⁿ (M; ℤ) is the fundamental class. The degree map is bijective, if there existsβ εH ₂(M, ℤ/2ℤ) such thatβ ·w ₂(M) ε 0. If suchβ does not exist, then deg is a 2-1 map; and (b) LetM be an orientable closed smooth (n+2)-manifold,n≥3. An elementα lies in the image of the degree map if and only ifρ ₂ α ·w ₂(M)=0, whereρ ₂: ℤ → ℤ/2ℤ is reduction modulo 2.     

On the existence of automorphisms with simple Lebesgue spectrum

It is shown that ifT is a measure preserving automorphism on a probability space (Ω,B, m) which admits a random variable X₀ with mean zero such that the stochastic sequence X₀ o T_n,n ε ℤ is orthonormal and spans L₀ ²(Ω,B,m), then for any integerk ≠ 0, the random variablesX o T^nk,n ε ℤ generateB modulom.     

Irregular wavelet frames on<Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>(ℝ<Superscript>n</Superscript>)

In this paper, we present the conditions on dilation parameter {s _j}_j that ensure a discrete irregular wavelet system {s _j ^n/2ψ(s _j ·−bk)} _{j∈ℤ,k∈ℤ} ⁿ to be a frame on L²(ℝⁿ), and for the wavelet frame we consider the perturbations of translation parameter b and frame function ψ respectively.     

The independence of initial vectors in the subdivision schemes

Starting with an initial vector λ = (λ(κ))κ∈z ∈ ep(Z), the subdivision scheme generates asequence (Snaλ)∞n=1 of vectors by the subdivision operator Saλ(κ) = ∑λ(j)a(k - 2j), k ∈ Z. j∈zSubdivision schemes play an important role in computer graphics and wavelet analysis. It is very interesting tounderstand under what conditions the sequence (Snaλ)∞n=1 converges to an Lp-function in an appropriate sense.This problem has been studied extensively. In this paper we show that the subdivision scheme converges forany initial vector in ep(Z) provided that it does for one nonzero vector in that space. Moreover, if the integertranslates of the refinable function are stable, the smoothness of the limit function corresponding to the vectorλ is also independent of λ.     

Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

A Note on Projecting the Cubic Lattice

It is shown that, given any (n−1)-dimensional lattice Λ, there is a vector v∈ℤ ⁿ such that the orthogonal projection of ℤ ⁿ onto v ^⊥ is, up to a similarity, arbitrarily close to Λ. The problem arises in attempting to find the largest cylinder anchored at two points of ℤ ⁿ and containing no other points of ℤ ⁿ .     

Meet and join matrices in the poset of exponential divisors

It is well-known that (ℤ₊, |) = (ℤ₊, GCD, LCM) is a lattice, where | is the usual divisibility relation and GCD and LCM stand for the greatest common divisor and the least common multiple of positive integers. The number $ d = \prod\nolimits_{k = 1}^r {p_k^{d^{(k)} } } $ d = \prod\nolimits_{k = 1}^r {p_k^{d^{(k)} } } is said to be an exponential divisor or an e-divisor of $ n = \prod\nolimits_{k = 1}^r {p_k^{n^{(k)} } } $ n = \prod\nolimits_{k = 1}^r {p_k^{n^{(k)} } } (n > 1), written as d | _e n, if d ^(k) for all prime divisors p _k of n. It is easy to see that (ℤ₊\{1}, | _e is a poset under the exponential divisibility relation but not a lattice, since the greatest common exponential divisor (GCED) and the least common exponential multiple (LCEM) do not always exist.     

Quotients of the unit ball of ℂn for a free action of ℤ

LetB _n be the unit ball of ℂⁿ and ℤ ≅ Γ ⊂ AutB _n be generated by a parabolic element of AutB _n. We show that the quotientB _n/Γ is biholomorphic to a holomorphically convex domain of ℂⁿ, whose automorphism group is explicity described. It follows thatB _n/ℤ is Stein for any free action of ℤ. Investigation partially supported by University of Bologna. Funds for selected research topics. The second author was supported by an Instituto Nazionale di Alta Matematica grant.     

On Small World Semiplanes with Generalised Schubert Cells

The well known “real-life examples” of small world graphs, including the graph of binary relation: “two persons on the earth know each other” contains cliques, so they have cycles of order 3 and 4. Some problems of Computer Science require explicit construction of regular algebraic graphs with small diameter but without small cycles. The well known examples here are generalised polygons, which are small world algebraic graphs i.e. graphs with the diameter d≤clog  _k−1(v), where v is order, k is the degree and c is the independent constant, semiplanes (regular bipartite graphs without cycles of order 4); graphs that can be homomorphically mapped onto the ordinary polygons. The problem of the existence of regular graphs satisfying these conditions with the degree ≥k and the diameter ≥d for each pair k≥3 and d≥3 is addressed in the paper. This problem is positively solved via the explicit construction. Generalised Schubert cells are defined in the spirit of Gelfand-Macpherson theorem for the Grassmanian. Constructed graph, induced on the generalised largest Schubert cells, is isomorphic to the well-known Wenger’s graph. We prove that the family of edge-transitive q-regular Wenger graphs of order 2q ⁿ , where integer n≥2 and q is prime power, q≥n, q>2 is a family of small world semiplanes. We observe the applications of some classes of small world graphs without small cycles to Cryptography and Coding Theory.     

Asymptotic results on infinite tandem queueing networks

We consider an infinite tandem queueing network consisting of ·/GI/1/∞ stations with i.i.d. service times. We investigate the asymptotic behavior of t(n, k), the inter-arrival times between customers n and n + 1 at station k, and that of w(n, k), the waiting time of customer n at station k. We establish a duality property by which w(n, k) and the “idle times”y(n, k) play symmetrical roles. This duality structure, interesting by itself, is also instrumental in proving some of the ergodic results. We consider two versions of the model: the quadrant and the half-plane. In the quadrant version, the sequences of boundary conditions {w(0,k), k∈ℕ} and {t(n, 0), n∈ℕ}, are given. In the half-plane version, the sequence {t(n, 0), n∈ℕ} is given. Under appropriate assumptions on the boundary conditions and on the services, we obtain ergodic results for both versions of the model. For the quadrant version, we prove the existence of temporally ergodic evolutions and of spatially ergodic ones. Furthermore, the process {t(n, k), n∈ℕ} converges weakly with k to a limiting distribution, which is invariant for the queueing operator. In the more difficult half plane problem, the aim is to obtain evolutions which are both temporally and spatially ergodic. We prove that 1/n∑ _k=1 ⁿ w(0, k) converges almost surely and in L ₁ to a finite constant. This constitutes a first step in trying to prove that {t(n,k), n∈ℤ} converges weakly with k to an invariant limiting distribution. Received: 23 March 1999 / Revised version: 5 January 2000 / Published online: 12 October 2000     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

p-Groupes abéliens de type (p,…,p) et disques ouverts p-adiques

Let k be an algebraically closed field of characteristic p>0, W(k) its ring of Witt vectors and R a complete discrete valuation ring dominating W(k). Consider finite groups G≃ (ℤ/pℤ) ⁿ , p≥ 2, n≥1. In a former paper we showed that a given realization of such a G as a group of k-automorphisms of k[[z]] must satisfy some conditions in order to have a lifting as a group of R-automorphisms of R[[Z]]. In this note, we give for every G (all p≥ 2, n>1) a realization as an automorphism group of k[[z]] which ca be lifted as a group of R-automorphisms of R[[Z]] for suitable R. Received: 22 December 1998     

On finitely presented,cancellative and commutative ordered monoids

We show that every finitely presented, cancellative and commutative ordered monoid is determined by a finitely generated and cancellative pseudoorder on the monoid (ℕ ⁿ ,+) for some positive integer n. Every cancellative pseudoorder on (ℕ ⁿ ,+) is determined by a submonoid of the group (ℤ ⁿ ,+), and we prove that the pseudoorder is finitely generated if and only if the submonoid is an affine monoid in ℤ ⁿ .     

Attainability of the minimal exponential growth rate for free products of finite cyclic groups

We consider free products of two finite cyclic groups of orders 2 and n, where n is a prime power. For any such group ℤ₂ * ℤ _n = 〈a, b | a ² = b ⁿ = 1〉, we prove that the minimal growth rate α _n is attained on the set of generators {a, b} and explicitly write out an integer polynomial whose maximal root is α _n . In the cases of n = 3, 4, this result was obtained earlier by A. Mann. We also show that under sufficiently general conditions, the minimal growth rates of a group G and of its central extension [(G)\tilde]\tilde G coincide and that the attainability of one implies the attainability of the other. As a corollary, the attainability is proved for some cyclic extensions of the above-mentioned free products, in particular, for groups 〈a, b | a ² = b ⁿ 〉, which are groups of torus knots for odd n.