Normal subgroups and elementary theories of lattice-ordered groups

We show that any lattice-ordered group (l-group) G can be l-embedded into continuously many l-groups H _i which are pairwise elementarily inequivalent both as groups and as lattices with constant e. Our groups H _i can be distinguished by group-theoretical first-order properties which are induced by lattice-theoretically nice properties of their normal subgroup lattices. Moreover, they can be taken to be 2-transitive automorphism groups A(S _i ) of infinite linearly ordered sets (S _i , ) such that each group A(S _i ) has only inner automorphisms. We also show that any countable l-group G can be l-embedded into a countable l-group H whose normal subgroup lattice is isomorphic to the lattice of all ideals of the countable dense Boolean algebra B.     

Varieties of lattice ordered groups that contain no non-abelian o-groups are solvable

It is shown that the variety _n of lattice ordered groups defined by the identity x ⁿ y ⁿ =y ⁿ x ⁿ , where n is the product of k (not necessarily distinct primes) is contained in the (k+1)st power A ^k+1 of the variety A of all Abelian lattice ordered groups. This implies, in particular, that _n is solvable class k + 1. It is further established that any variety V of lattice ordered groups which contains no non-Abelian totally ordered groups is necessarily contained in _n , for some positive integer n.This work was supported in part, by NSERC Grant A4044.     

Automorphism groups of comparability and covering graphs

Let G be a group and H a subgroup of G. It is shown that there exists a partially ordered set (X, ) such that G is isomorphic to the group of all automorphisms of the comparability graph of (X, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (X, ). There also exists a partially ordered set (Y, ) such that G is isomorphic to the group of all automorphisms of the covering graph of (Y, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (Y, ). In this representation X and Y can be taken to be finite if G is finite and of the same cardinality as G if G is infinite.     

On the dimensions of ordered sets of bounded degree

Let P be a partially ordered set. Define k = k (P) = max _p |{x P : p < x or p = x}|, i.e., every element is comparable with at most k others. Here it is proven that there exists a constant c (c < 50) such that dim P < ck(log k)². This improves an earlier result of Rödl and Trotter (dim P 2 k ²+2). Our proof is nonconstructive, depending in part on Lovász' local lemma.Supported in part by NSF under Grant No. MCS83-01867 and by a Sloan Research Fellowship.     

Extended iterative methods for the solution of operator equations

Summary Given an iterative methodM ₀, characterized byx ^(k+1=G ₀(x( ^k )) (k0) (x(⁰) prescribed) for the solution of the operator equationF(x)=0, whereF:XX is a given operator andX is a Banach space, it is shown how to obtain a family of methodsM _p characterized byx ^(k+1=G _p (x( ^k )) (k0) (x(⁰) prescribed) with order of convergence higher than that ofM _o. The infinite dimensional multipoint methods of Bosarge and Falb [2] are a special case, in whichM ₀ is Newton's method.Analogues of Theorems 2.3 and 2.36 of [2] are proved for the methodsM _p, which are referred to as extensions ofM ₀. A number of methods with order of convergence greater than two are discussed and existence-convergence theorems for some of them are proved.Finally some computational results are presented which illustrate the behaviour of the methods and their extensions when used to solve systems of nonlinear algebraic equations, and some applications currently being investigated are mentioned.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

Ordered sets with no chains of ideals of a given type

We study the possible order types of chains of ideals in an ordered set. Our main result is this. Given an indecomposable countable order type , there is a finite listA ₁ , ...,A _n of ordered sets such that for every ordered setP the setJ(P) of ideals ofP, ordered by inclusion, contains a chain of type if and only ifP contains a subset isomorphic to one of theA ₁ ^#x03B1; , ...,A _n . The finiteness of the list relies on the notion of better quasi-ordering introduced by Nash-Williams and the properties of scattered chains obtained by Laver.The results presented. here constitute the second chapter of the third cycle thesis presented by the second author before the Claude Bernard University, Lyon (July 1983).     

Torsion and Abelianization in Equivariant Cohomology

Let X be a topological space upon which a compact connected Lie group G acts. It is well known that the equivariant cohomology H ^* _G (X; Q) is isomorphic to the subalgebra of Weyl group invariants of the equivariant cohomology H ^* _T (X; Q), where T is a maximal torus of G. This relationship breaks down for coefficient rings k other than Q. Instead, we prove that under a mild condition on k the algebra H ^* _G (X; k) is isomorphic to the subalgebra of H ^* _T (X; k) annihilated by the divided difference operators.     

Cohomologie galoisienne des groupes quasi-déployés sur des corps de dimension cohomologique ≤2; Galois cohomology of quasi-split groups over fields of cohomological dimension ≤ 2

Let k be a perfect field with cohomological dimension 2. Serre's conjecture II claims that the Galois cohomology set H ¹(k,G) is trivial for any simply connected semi-simple algebraic G/k and this conjecture is known for groups of type ¹ A _n after Merkurjev–Suslin and for classical groups and groups of type F ₄ and G ₂ after Bayer–Parimala. For any maximal torus T of G/k, we study the map H ¹(k, T) H ¹(k, G) using an induction process on the type of the groups, and it yields conjecture II for all quasi-split simply connected absolutely almost k-simple groups with type distinct from E ₈. We also have partial results for E ₈ and for some twisted forms of simply connected quasi-split groups. In particular, this method gives a new proof of Hasse principle for quasi-split groups over number fields including the E ₈-case, which is based on the Galois cohomology of maximal tori of such groups.     

First order theory of cyclically ordered groups

By a result known as Rieger's theorem (1956), there is a one-to-one correspondence, assigning to each cyclically ordered group H a pair $(G,z)$ where G is a totally ordered group and z is an element in the center of G, generating a cofinal subgroup $〈z〉$ of G, and such that the cyclically ordered quotient group $G/〈z〉$ is isomorphic to H. We first establish that, in this correspondence, the first-order theory of the cyclically ordered group H is uniquely determined by the first-order theory of the pair $(G,z)$. Then we prove that the class of cyclically orderable groups is an elementary class and give an axiom system for it. Finally we show that, in contrast to the fact that all theories of totally ordered Abelian groups have the same universal part, there are uncountably many universal theories of Abelian cyclically ordered groups.     

Lawless order

R. Baer asked whether the group operation of every (totally) ordered group can be redefined, keeping the same ordered set, so that the resulting structure is an Abelian ordered group. The answer is no. We construct an ordered set (G, ) which carries an ordered group (G, , ) but which islawless in the following sense. If (G, *, ) is an ordered group on the same carrier (G, ), then the group (G, *) satisfies no nontrivial equational law.Research partially supported by NSERC of Canada Grants #A4044 and A3040.Research partially supported by NSERC of Canada Grant #U0075.Research partially supported by a grant from the BSF.     

Greene-Kleitman's theorem for infinite posets

It is proved that if (P) is a poset with no infinite chain and k is a positive integer, then there exist a partition of P into disjoint chains C _i and disjoint antichains A ₁, A ₂, ..., A _k, such that each chain C _i meets min (k, |C _i|) antichains A _j. We make a dual conjecture, for which the case k=1 is: if (P) is a poset with no infinite antichain, then there exist a partition of P into antichains A _i and a chain C meeting all A _i. This conjecture is proved when the maximal size of an antichain in P is 2.     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

Random graphs and covering graphs of posets

For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n ^-1+(n) ,where (n) is bounded away from 0, then there is a constant k ₀>0 such that, for a.e. G _p , c(G _p )k ₀ n ¹⁺⁽ⁿ⁾ .In other words, to make G _p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n ^-1+(n) , where (n)0, thenc(G _p )=o(n ¹⁺⁽ⁿ⁾ ), almost surely.Partially supported by MCS Grant 8104854.     

Automorphism group and dimension of ordered sets

It is shown that a finite groupG is isomorphic to the automorphism group of a two-dimensional ordered set if and only if it is a generalized wreath product of symmetric groups over an ordered index set that is a dual tree. Furthermore, every finite abelian group is isomorphic to the full automorphism group of a three-dimensional ordered set. Also every finite group is isomorphic to the automorphism group of an ordered set that does not contain an induced crown with more than four elements.     

Contractions of infrainvariant systems of subgroups

We create a method which allows an arbitrary group G with an infrainvariant system ℒ(G) of subgroups to be embedded in a group G* with an infrainvariant system ℒ(G*) of subgroups, so that G _α^* ∩G ∈ ℒ(G) for every subgroup G _α^* ∩G ∈ ℒ(G*) and each factor B/A of a jump of subgroups in ℒ(G*) is isomorphic to a factor of a jump in ℒ(G), or to any specified group H. Using this method, we state new results on right-ordered groups. In particular, it is proved that every Conrad right-ordered group is embedded with preservation of order in a Conrad right-ordered group of Hahn type (i.e., a right-ordered group whose factors of jumps of convex subgroups are order isomorphic to the additive group ℝ); every right-ordered Smirnov group is embedded in a right-ordered Smirnov group of Hahn type; a new proof is given for the Holland–McCleary theorem on embedding every linearly ordered group in a linearly ordered group of Hahn type.     

On graph equivalences preserved under extensions

Let G be the set of finite graphs whose vertices belong to some fixed countable set, and let ≡ be an equivalence relation on G. By the strengthening of ≡ we mean an equivalence relation ≡_s such that G≡_sH, where G,H∈G, if for every F∈G, G∪F≡H∪F. The most important case that we study in this paper concerns equivalence relations defined by graph properties. We write G≡^ΦH, where Φ is a graph property and G,H∈G, if either both G and H have the property Φ, or both do not have it. We characterize the strengthening of the relations ≡^Φ for several graph properties Φ. For example, if Φ is the property of being a k-connected graph, we find a polynomially verifiable (for k fixed) condition that characterizes the pairs of graphs equivalent with respect to . We obtain similar results when Φ is the property of being k-colorable, edge 2-colorable, Hamiltonian, or planar, and when Φ is the property of containing a subgraph isomorphic to a fixed graph H. We also prove several general theorems that provide conditions for ≡_s to be of some specific form. For example, we find a necessary and sufficient condition for the relation ≡_s to be the identity. Finally, we make a few observations on the strengthening in a more general case when G is the set of finite subsets of some countable set.     

Recognizing Groups G 23 n ) by Their Element Orders

It is proved that a finite group that is isomorphic to a simple non-Abelian group G=G ₂(3 ⁿ ) is, up to isomorphism, recognized by a set (G) of its element orders, that is, H G if (H)=(G) for some finite group H.     

Reconstructing graphs as subsumed graphs of hypergraphs,and some self-complementary triple systems

LetV be a set ofn elements. The set of allk-subsets ofV is denoted . Ak-hypergraph G consists of avertex-set V(G) and anedgeset , wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG _v . The graphs {G _v νvεV(G)} aresubsumed byG. Each subsumed graphG _v is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG _v ≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG ^*, all of whose subsumed graphs are isomorphic toH, whereG andG ^* are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way. This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.     

Lattices isomorphic with their free powers

For any N3 there exists a lattice L isomorphic with NL (the free product of its own N copies) but not isomorphic with kL for any k–2,...,N-1.