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).     

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).     

Tannakian formalism for fiber functors over tensor categories

It is well known that the pseudovariety \(\mathbf {J}\) of all \(\mathscr {J}\)-trivial monoids is not local, which means that the pseudovariety \(g\mathbf {J}\) of categories generated by \(\mathbf {J}\) is a proper subpseudovariety of the pseudovariety \(\ell \mathbf {J}\) of categories all of whose local monoids belong to \(\mathbf {J}\). In this paper, it is proved that the pseudovariety \(\mathbf {J}\) enjoys the following weaker property. For every prime number p, the pseudovariety \(\ell \mathbf {J}\) is a subpseudovariety of the pseudovariety \(g(\mathbf {J}*\mathbf {Ab}_p)\), where \(\mathbf {Ab}_p\) is the pseudovariety of all elementary abelian p-groups and \(\mathbf {J}*\mathbf {Ab}_p\) is the pseudovariety of monoids generated by the class of all semidirect products of monoids from \(\mathbf {J}\) by groups from \(\mathbf {Ab}_p\). As an application, a new proof of the celebrated equality of pseudovarieties \(\mathbf {PG}=\mathbf {BG}\) is obtained, where \(\mathbf {PG}\) is the pseudovariety of monoids generated by the class of all power monoids of groups and \(\mathbf {BG}\) is the pseudovariety of all block groups.     

Group Connectivity of 3-Edge-Connected Chordal Graphs

Let A be a finite abelian group and G be a digraph. The boundary of a function f: E(G)ZA is a function ‘f: V(G)ZA given by ‘f(v)=~_{e leaving v}f(e)m~_{e entering v}f(e). The graph G is A-connected if for every b: V(G)ZA with ~_{v] V(G)} b(v)=0, there is a function f: E(G)ZA{0} such that ‘f=b. In [J. Combinatorial Theory, Ser. B 56 (1992) 165-182], Jaeger et al showed that every 3-edge-connected graph is A-connected, for every abelian group A with |A|̈́. It is conjectured that every 3-edge-connected graph is A-connected, for every abelian group A with |A|̓ and that every 5-edge-connected graph is A-connected, for every abelian group A with |A|́.¶ In this note, we investigate the group connectivity of 3-edge-connected chordal graphs and characterize 3-edge-connected chordal graphs that are A-connected for every finite abelian group A with |A|́.     

On chief factors of parabolic maximal subgroups of the group <Superscript>2</Superscript><Emphasis Type="Italic">E</Emphasis><Subscript>6</Subscript>(<Emphasis Type="Italic">q</Emphasis><Superscript>2</Superscript>)

We consider the pseudovariety generated by all finite monoids on which Green’s relations R and H coincide. We find a new algorithm that determines if a given finite monoid belongs to this pseudovariety.     

The structure of finite monoids satisfying the relation ℛ = ℋ

It is shown that any finite monoid S on which Green’s relations R and H coincide divides the monoid of all upper triangular row-monomial matrices over a finite group. The proof is constructive; given the monoid S, the corresponding group and the order of matrices can be effectively found. The obtained result is used to identify the pseudovariety generated by all finite monoids satisfying R = H with the semidirect product of the pseudovariety of all finite groups and the pseudovariety of all finite R-trivial monoids.     

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.     

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.     

(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).     

On free spectra of finite monoids from the pseudovariety DA

The pseudovariety DA consists of all aperiodic finite monoids all of whose regular -classes are subsemigroups (that is, rectangular subbands); this pseudovariety appears quite frequently in various contexts in finite semigroup theory. In this note we prove that all its members have a log-polynomial free spectrum, thereby making a new step towards proving the Seif conjecture on the dichotomy of free spectra of finite monoids.     

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).     

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₀, %)Д %.     

Fundamental groups,inverse schützenberger automata,and monoid presentations

This paper gives decidable conditions for when a finitely generated subgroup of a free group is the fundamental group of a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Also, generalizations are given to specific types of inverse monoids as well as to monoids which are "nearly inverse." This result has applications to computing membership for inverse monoids in a Mal'cev product of the pseudovariety of semilattices with a pseudovariety of groups.

This paper also shows that there is a bijection between strongly connected inverse automata and subgroups of a free group, generated by positive words. Hence, we also obtain that it is decidable whether a finite strongly connected inverse automaton is a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Again, we have generalizations to other types of inverse monoids and to "nearly inverse" monoids. We show that it is undecidable whether a finite strongly connected inverse automaton is a Schützenberger automaton of a monoid presentation of anE-unitary inverse monoid.     

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.     

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.     

On the relative solvability of certain inverse monoids

The notion of kernel of a finite monoid relative to a pseudovariety of groups can be used to define relative solvability of monoids in a similar way to the manner in which the notion of derived subgroup can be used to define solvable group. In this paper we study the solvability of certain inverse monoids relative to pseudovarieties of abelian groups.     

Every Invariant Measure Semigroup Contains an Ideal which is Embeddable in a Group

We show that every invariant measure semigroup S with associated invariant measure mu contains an ideal S₀ which is embeddable as an open subsemigroup in a locally compact abelian group G in such a way that the restriction to S₀ of mu coincides with the restriction to S₀ of a Haar measure on G. This is a positive answer to a question posed by J.H Williamson. As a consequence the generalization of Pontryagin's duality theorem for S is obtained.