Quasi-polynomials associated with Bass and Betti numbers of filtered modules

It is shown that if M is a finite module on a local noetherian ring A which is filtered by an f-good filtration F \Phi = (M_n) where f is a noetherian filtration on A, then the i-th Betti and the i-th Bass numbers of the modules (M_n) and (M / M_n) define quasi-polynomial functions whose period does not depend on i but only of the Rees ring of f. It is proved that the projective and injective dimension of the modules M / M_n are perodic for large n. In the particular case where f is a good filtration or a strongly A P filtration it is shown that the projective and injective dimension as well as the depth stabilize. As an application, using a result proved by Brodmann, we give an upper bound of the analytic spread of¶ f = (I_n) in terms of the limes inferior of depth (A / I_n).     

On the binomial arithmetical rank

The binomial arithmetical rank of a binomial ideal I is the smallest integer s for which there exist binomials f₁,..., f_s in I such that rad (I) = rad (f₁,..., f_s). We completely determine the binomial arithmetical rank for the ideals of monomial curves in P_KⁿP_K^n. In particular we prove that, if the characteristic of the field K is zero, then bar (I(C)) = n - 1 if C is complete intersection, otherwise bar (I(C)) = n. While it is known that if the characteristic of the field K is positive, then bar (I(C)) = n - 1 always.     

Mal'cev nilpotent algebras

We show that the Mal'cev semigroup identity x_n = y_n holds in the circle semigroup of an associative algebra over an infinite field precisely when the algebra is Lie nilpotent of class at most n. The Mal'cev semigroup law x_n = y_n holds in a group if and only if the group is nilpotent of class at most n.     

On Groups Associated with Transformation Semigroups

For a semigroup S of transformations (total or partial) of a finite n-element set X_n, denote by G_S the group of all the permutations h of X_n that preserve S under conjugation. It is shown that, unless S contains certain nilpotents and has a very restricted form, the alternating group Alt_n may not serve as G_S, so that Alt_n ⊆ G_S implies that G_S=S_n, and S is an S_n-normal semigroup.     

Abelian Kernels of Some Monoids of Injective Partial Transformations and an Application

In this paper we compute the abelian kernels of the monoids POI_n and POPI_n of all injective order preserving and respectively, orientation preserving, partial transformations on a chain with n elements. As an application, we show that the pseudovariety POPI generated by the monoids POPI_n (n epsilon N) is not contained in the Mal'cev product of the pseudovariety POI generated by the monoids POI_n (n epsilon N) with the pseudovariety Ab of all finite abelian groups.     

The 2-Pebbling Property and a Conjecture of Graham's

The pebbling number of a graph G, f(G), is the least m such that, however m pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. It is conjectured that for all graphs G and H, f(G 2H)hf(G)f(H).¶Let C_m and C_n be cycles. We prove that f(C_m 2C_n)hf(C_m) f(C_n) for all but a finite number of possible cases. We also prove that f(G2T)hf(G) f(T) when G has the 2-pebbling property and T is any tree.     

On matrix near-rings

Let R be a right near-ring with identity and M_n(R) be the near-ring of n 2 n matrices over R in the sense of Meldrum and Van der Walt. In this paper, M_n(R) is said to be s\sigma-generated if every n 2 n matrix A over R can be expressed as a sum of elements of X_n(R), where X_n(R)={f_ij^r | 1\leqq i, j\leqq n, r ? R}X_n(R)=\{f_{ij}^r\,|\,1\leqq i, j\leqq n, r\in R\}, is the generating set of M_n(R). We say that R is s\sigma-generated if M_n(R) is s\sigma-generated for every natural number n. The class of s\sigma-generated near-rings contains distributively generated and abstract affine near-rings. It is shown that this class admits homomorphic images. For abelian near-rings R, we prove that the zerosymmetric part of R is a ring, so the class of zerosymmetric abelian s\sigma-generated near-rings coincides with the class of rings. Further, for every n, there is a bijection between the two-sided subgroups of R and those of M_n(R).     

The Problem of Freeness for Euler Monoids and Möbius Groups

The Euler monoid E_n = {(a,b,t) epsilon Z³ : a² + b² = tⁿ, n S 1, is free if and only if n is odd (Theorem 1). We extend the results of Lyndon and Ullman, and Beardon concerning the set of those rational numbers mu epsilon (-2,2) for which the matrix Möbius group G_mu generated by A= and B = is not free (Theorems 2, 3, 4).     

Finding Large p-Colored Diameter Two Subgraphs

Given a coloring of the edges of the complete graph K on n vertices in k colors, a p-colored subgraph of K_n is any subgraph whose edges only use colors from some p element set. We show for k̿ and k\2hphk that there is always a p-colored diameter two subgraph of K_n containing at least [((k+p)n)/(2k)]\displaystyle{(k+p)n \over 2k} vertices and that this is best possible up to an additive constant l satisfying 0hl<k\2.     

A note on growth sequences of alternating groups

The aim of this paper is to give a lower bound for h(2, A_n), where h(2, A_n) is the maximum number such that A_n^{h(2, A_n)} A_n^{h(2, A_n)} can be generated by 2 elements, where A_n is the alternating group on n symbols, and n \geqq 5 n \geqq 5 . Kantor and Lubotzky (1990) gave a lower bound¶ \fracn!8 \frac{n!}{8} for sufficiently large n by the probability of generating the symmetric group. I have improved the above lower bound to \fracn!5 \frac{n!}{5} for large n, using a different method.     

On q-Olivier Functions

We consider words w₁· · · w_n with letters w_i ? {1, 2, 3, ?} w_i \in \{1, 2, 3, \ldots\} satisfying an up-up-down pattern like a₁ h a₂ h a₃ S a₄ h a₅ h a₆ S · · · . Attaching the (geometric) probability pq^i-1 to the letter i (with p = 1 -- q), every word gets a probability by assuming independence of letters. We are interested in the probability that a random word of length n satisfies the up-up-down condition. It turns out that one has to consider the 3 residue classes (mod 3) separately; then one can compute the associated probability generating function. They turn out to be q-analogues of so called Olivier functions.     

On the existence of certain measures appearing in distance geometry

Abstract. We prove the following result: Let X be a compact connected Hausdorff space and f be a continuous function on X x X. There exists some regular Borel probability measure m\mu on X such that the value of¶¶ ò\limit _X f(x,y)dm(y)\int\limit _X f(x,y)d\mu (y) is independent of the choice of x in X if and only if the following assertion holds: For each positive integer n and for all (not necessarily distinct) x₁,x₂,...,x_n,y₁,y₂,...,y_n in X, there exists an x in X such that¶¶ ?_i=1ⁿ f(x_i,x)=?_i=1ⁿ f(y_i,x).\sum\limits _{i=1}^n f(x_i,x)=\sum\limits _{i=1}^n f(y_i,x).     

A note on the complexity of the transportation problem with a permutable demand vector

In this note we investigate the computational complexity of the transportation problem with a permutable demand vector, TP-PD for short. In the TP-PD, the goal is to permute the elements of the given integer demand vector b=(b₁,…,b_n) in order to minimize the overall transportation costs. Meusel and Burkard [6] recently proved that the TP-PD is strongly NP-hard. In their NP-hardness reduction, the used demand values b_j, j=1,…,n, are large integers. In this note we show that the TP-PD remains strongly NP-hard even for the case where b_j]{0,3} for j=1,…,n. As a positive result, we show that the TP-PD becomes strongly polynomial time solvable if b_j] {0,1,2} holds for j=1,…,n. This result can be extended to the case where b_j]{3,3+1,3+2} for an integer 3.     

Integral Lie powers of a lattice for the cyclic group of order 2

Let L_n denote the n-th homogeneous component of the free Lie ring L(W) on a given \Bbb ZC₂{{\Bbb Z}}C_{2}-lattice W. This paper gives explicit formulae for the multiplicities of the three indecomposable \Bbb ZC₂{{\Bbb Z}}C_{2}-lattices in a Krull-Schmidt decomposition of L_n. In the case where W is a free \Bbb ZC₂{{\Bbb Z}}C_{2}-lattice, L_n is shown to have no non-zero direct summand on which C₂ acts trivially - this extends a result of R. M. Bryant for the special case where W is the regular \Bbb ZC₂{{\Bbb Z}}C_{2}-lattice. As an application, the structure of the higher dimensional modules associated to a non-cyclic free presentation of C₂ is determined.     

The differential Hilbert series of a local algebra

The differential Hilbert series of a commutative local algebra R/R₀ which is essentially of finite type is the generating function of the numerical function which associates with each n ? \Bbb N n\in \Bbb N the minimal number of generators of the algebra Pⁿ_R/R0P^n_{R/R_0} of principal parts of order n, considered as an R-module. It can be expressed as a rational function over the integers. We wish to compute this rational function in terms of other invariants of the local algebra or at least give estimates of it. We obtain formulas which generalize wellknown facts about the minimal number of generators of the module of Kähler differentials.     

How Tight Is the Bollobás-Komlós Conjecture?

The bipartite case of the Bollobás and Komlós conjecture states that for every j₀, %>0 there is an !=!(j₀, %) >0 such that the following statement holds: If G is any graph with minimum degree at least n$\displaystyle {n \over 2}+%n then G contains as subgraphs all n vertex bipartite graphs, H, satisfying¶H)hj₀ \quad {\rm and} \quad b(H)h!n.$j (H)hj₀ \quad {\rm and} \quad b(H)h!n.¶Here b(H), the bandwidth of H, is the smallest b such that the vertices of H can be ordered as v₁, …, v_n such that v_i~_Hv_j implies |imj|hb.¶ This conjecture has been proved in [1]. Answering a question of E. Szemerédi [6] we show that this conjecture is tight in the sense that as %̂ then !̂. More precisely, we show that for any 0 such that that !(j₀, %)Д %.     

Odd order groups with the rewriting property Q3

Let n be an integer greater than 1, and let G be a group. A subset {x₁, x₂, ..., x_n} of n elements of G is said to be rewritable if there are distinct permutations p \pi and s \sigma of {1, 2, ..., n} such that¶¶x_p(1)x_p(2) ?x_p(n) = x_s(1)x_s(2) ?x_s(n). x_{\pi(1)}x_{\pi(2)} \ldots x_{\pi(n)} = x_{\sigma(1)}x_{\sigma(2)} \ldots x_{\sigma(n)}. ¶¶A group is said to have the rewriting property Q_n if every subset of n elements of the group is rewritable. In this paper we prove that a finite group of odd order has the property Q₃ if and only if its derived subgroup has order not exceeding 5.     

(2, 3, k)-generated groups of large rank

For any fixed k 3 7k \geq 7 there exist integers n_k and a_k such that if the ring R is generated by a set of m elements t₁,...,t_m, where 2t₁-t₁²2t_1-t_1^2 is a unit of finite multiplicative order, and n 3 n_k+ma_kn \geq n_k+ma_k, then the group E_n(R) generated by elementary transvections is an epimorphic image of the triangle group D(2,3,k).\Delta (2,3,k).