Structure of a finite commutative inverse semigroup and a finite bundle for which the inverse monoid of local automorphisms is permutable

For a semigroup S, the set of all isomorphisms between the subsemigroups of the semigroup S with respect to composition is an inverse monoid denoted by PA(S) and called the monoid of local automorphisms of the semigroup S. The semigroup S is called permutable if, for any couple of congruences ρ and σ on S, we have ρ ∘ σ = σ ∘ ρ. We describe the structures of a finite commutative inverse semigroup and a finite bundle whose monoids of local automorphisms are permutable.     

On permutation properties in groups and semigroups

A semigroupS satisfiesPPn, thepermutation property of degree n (n≥2) if every product ofn elements inS remains invariant under some nontrivial permutation of its factors. It is shown that a semigroup satisfiesPP3 if and only if it contains at most one nontrivial commutator. Further a regular semigroup is a semilattice ofPP3 right or left groups, and a subdirect product ofPP3 semigroups of a simple type. A negative answer to a question posed by Restivo and Reutenauer is provided by a suitablePP3 group.     

A krasnosel'skii-type theorem in the plane involving polygonal n-paths

It is shown that thenth order kernel of a compact simply connected subsetS ofR ² is nonempty if and only if every three boundary points ofS are visible via polygonaln-paths from a common point inS.     

On the lattice property of the plane and some problems of Dirac,Motzkin and Erdős in combinatorial geometry

LetS be a set ofn non-collinear points in the Euclidean plane. It will be shown here that for some point ofS the number ofconnecting lines through it exceedsc · n. This gives a partial solution to an old problem of Dirac and Motzkin. We also prove the following conjecture of Erdős: If any straight line contains at mostn−x points ofS, then the number of connecting lines determined byS is greater thanc · x · n. Dedicated to Paul Erdős on his seventieth birthday     

ON STABLE LINE SEGMENTS IN ALL TRIANGULATIONS OF A PLANAR POINT SET

Abstract. Let S be a set of finite plauar points. A llne segment L(p, q) with p, q E Sis called a stable line segment of S, if there is no Line segment with two endpoints in S intersecting L(p, q). In this paper, some geometric properties of the set of all stable line segments     

New examples of Lagrangian rigidity

Letn=4 or 8. We prove that any Lagrangian embedding ofS ^{n − 1} ×S ¹ into ℂ ⁿ has a trivial linking class. We deduce that every embedding ofS ³ ×S ⁴ into ℂ⁴ is isotopic to a Lagrangian embedding. This is false ifn = 8.     

A note on the circle containment problem

We extend a result due to Bárányet al. and prove the following theorem: given any setS ofn points in the plane, there are pointsx andy inS, such that every circle that containsx andy contains at least [5/84(n – 2)] other points ofS.     

Theorem about the conjugacy representation ofS n

Every group has two natural representations on itself, the regular representation and the conjugacy representation. We know everything about the construction of the regular representation, but we know very little about the conjugacy representation (for uncommutative groups). In this paper we will see that every irreducible complex character ofS _n (n>2) is a constituent of conjugacy character ofS _n .     

Control of systems to sets and their interiors

For a closed target setS ⁿ and a control system (formulated as a differential inclusion and defined nearS), the present paper considers a sufficient condition for the property that every point nearS can be steered toS in finite time by some trajectory of the system. Estimates are obtained revealing how fast some such trajectory is nearing the target. A strong form of this condition is shown to imply that every trajectory of the system hits the target. With a further assumption on the target setS, we also consider conditions that guarantee that some trajectories enter the interior ofS.This work was supported by the Natural Sciences and Engineering Research Council of Canada and by FCAR, Québec, Canada.     

Comportement moyen du cardinal de certains ensembles de facteurs premiers

Letn be a positive integer andS _n a particular set of prime divisors ofn. We establish the average order off(n) wheref(n) stands for the cardinality ofS _n . Thek-ary,k-free, semi-k-ary prime factors ofn are some of the classes of prime divisors studied in this paper.

     

Covering abelian groups with cyclic subsets

Summary Letk andm be positive integers. An abelian groupG is said to have ann-cover if there is a subsetS ofG consisting ofn elements such that every non-zero element ofG can be expressed in the formig for some elementg inS and integeri, 1 i k. Lets _n (k) be the largest order of abelian groups that have ann-cover. We investigate the behavior ofs _n (k)/k ask andn is fixed.     

Illuminating high-dimensional convex sets

A setL of points in thed-spaceE ^d is said toilluminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d if for every setS _i inF and every pointx in the boundary ofS _i there is a pointv inL such thatv illuminatesx, i.e. the line segment joiningv tox intersects the union of the elements ofF in exactly {x}.The problem we treat is the size of a setS needed to illuminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d . We also treat the problem of putting these convex sets in mutually disjoint convex polytopes, each one having at most a certain number of facets.     

Automorphisms of linear semigroups over division rings

Given an-dimensional right vector spaceV over a division ring we denote byS the semigroup of the endomorphisms ofV and designate this semigroup as alinear semigroup. First we prove that every automorphism ofS can be written asT→fTf ⁻¹, wheref∶V→V is a semilinear homeomorphism. Furthermore, we show that every isomorphism between maximal compact subsemigroups ofS is also of this type.     

Homomorphisms of extensions of a semigroup within a variety

LetV be a semigroup variety containing all commutative semigroups such that the law of exponents (xy) ⁿ =xⁿyⁿ fails inV for everyn > 1. For every semigroupS V such that the reflection of the semigroup obtained fromS by an adding unity has only one idempotent there exists a semigroupT V extendingS without non-trivial endomorphisms. In more general, the full subcategory ofV formed by all extensions ofS withinV is universal.Presented by B. M. Schein.     

A Classification of Fully Residually Free Groups of Rank Three or Less

A groupGisfully residually freeprovided to every finite setS ⊂ G\{1} of non-trivial elements ofGthere is a free groupF_Sand an epimorphismh_S:G → F_Ssuch thath_S(g) ≠ 1 for allg ∈ S. Ifnis a positive integer, then a groupGisn-freeprovided every subgroup ofGgenerated bynor fewer distinct elements is free. Our main result shows that a fully residually free group of rank at most 3 is either abelian, free, or a free rank one extension of centralizers of a rank two free group. To prove this we prove that every 2-free, fully residually free group is actually 3-free. There are fully residually free groups which are not 2-free and there are 3-free, fully residually free groups which are not 4-free.     

Linear space data structures for two types of range search

This paper investigates the existence of linear space data structures for range searching. We examine thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently. We also look atdomination searching in three dimensions. In this problem,S is a set ofn points inE ³ and the question is to retrieve all points ofS that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and nearly optimal in the second.This research was conducted while the first author was with Brown University and the second author was with the Technical University of Graz, Austria. The first author was supported in part by NSF Grant MCS 83-03925.     

Semigroups of finite matrices

We derive, by elementary methods, some useful facts, some new, for matrix semigroups especially for compact non-negative matrix semigroups, generalizing some results of A. Gleason. These results may be applied to automata theory when input and output are sensed stochastically; we hope to write up these applications shortly. LetS be a (multiplicative) semigroup ofn×n matrices overC, compact as a subset ofC ⁿ². LetI be the two sided ideal inS of elements of minimal rank. (I is clearly closed since rank can be expressed by vanishing of minors). We will show, among other things, thatI is precisely the minimal ideal or core ofS, generalizing a result of Gleason [2].     

On Nearly S-Permutable Subgroups of Finite Groups

We say that a subgroup H of a finite group G is nearly S-permutable in G if for every prime p such that (p, |H|) = 1 and for every subgroup K of G containing H the normalizer N _K (H) contains some Sylow p-subgroup of K. We study the structure of G under the assumption that some subgroups of G are nearly S-permutable in G.     

AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem

The input to the asymmetricp-center problem consists of an integerpand ann × ndistance matrixDdefined on a vertex setVof sizen, whered_ijgives the distance fromitoj. The distances are assumed to obey the triangle inequality. For a subsetS Vthe radius ofSis the minimum distanceRsuch that every point inVis at a distance at mostRfrom some point inS. Thep-center problem consists of picking a setS Vof sizepto minimize the radius. This problem is known to be NP-complete.For the symmetric case, whend_ij = d_ji, approximation algorithms that deliver a solution to within 2 of the optimal are known. David Shmoys, in his article [[11]], mentions that nothing was known about the asymmetric case. We present an algorithm that achieves a ratio ofO(log*n).