Graphs of small dimensions

LetG=(V, E) be a graph withn vertices. The direct product dimension pdim (G) (c.f. [10], [12]) is the minimum numbert such thatG can be embedded into a product oft copies of complete graphsK _n.In [10], Lovász, Neetil and Pultr determined the direct product dimension of matchings and paths and gave sharp bounds for the product dimension of cycles, all logarithmic in the number of vertices.     

Small idempotent clones I

G. Grätzer and A. Kisielewicz devoted one section of their survey paper concerning p _n-sequences and free spectra of algebras to the topic Small idempotent clones (see Section 6 of [18]). Many authors, e.g., [8], [14, 15], [22], [25] and [29, 30] were interested in p _n-sequences of idempotent algebras with small rates of growth. In this paper we continue this topic and characterize all idempotent groupoids (G, ·) with p ₂(G, ·) 2 (see Section 7). Such groupoids appear in many papers see, e.g. [1], [4], [21], [26, 27], [25], [28, 30, 31, 32] and [34].     

Foliation-Preserving Maps Between Solvmanifolds

For i=1,2, let _i be a lattice in a simply connected, solvable Lie group G _i , and let X _i be a connected Lie subgroup of G _i . The double cosets _i g X _i provide a foliation _i of the homogeneous space _i \G _i . Let f be a continuous map from ₁\G ₁ to ₂\G ₂ whose restriction to each leaf of ₁ is a covering map onto a leaf of ₂. If we assume that ₁ has a dense leaf, and make certain technical assumptions on the lattices ₁ and ₂, then we show that f must be a composition of maps of two basic types: a homeomorphism of ₁\G ₁ that takes each leaf of ₁ to itself, and a map that results from twisting an affine map by a homomorphism into a compact group. We also prove a similar result for many cases where G ₁ and G ₂ are neither solvable nor semisimple.     

Orthocomplemented lattices in ordered groups

On a partially ordered set G the orthogonality relation is defined by incomparability and is a complete orthocomplemented lattice of double orthoclosed sets. We will prove that the atom space of the lattice has the same order structure as G. Thus if G is a partially ordered set (an ordered group, or an ordered vector space), then is a canonically partially ordered set (an ordered quotient group, or an ordered quotient vector space, respectively). We will also prove: if G is an ordered group with a positive cone P, then the lattice has the covering property iff , where g is an element of G and M is the intersection of all maximal subgroups contained in . Received August 1, 2006; accepted in final form May 29, 2007.     

An asymptotic definition of K-groups of automorphisms and a non-Bernoullian counter-example

Summary Let GZⁿ be a group of measure preserving transformations of a Lebesgue space. J. P. Conze [1] has developed an entropy theory for such groups and described a class of groups obeying a form of the Kolmogorov zero-one law called K-groups. A Bernoulli group is a group isomorphic to the group of translates (shifts) of elements of the space with product measure where X _g =X is a probability space. Bernoulli groups are also K-groups. Katznelson and Weiss [3] have shown entropy is a complete invariant for isomorphism classes of Bernoulli groups. We give an asymptotic definition of K-groups in terms of finite -algebras and justify this definition in terms of entropy and Conze's formulation. This definition s used to help us construct a K-group GZ ⁿ that is completely non-Bernoulli, that is one that contains no Bernoulli subgroup.     

Partially ordered permutation groups

In this note we discuss permutation groups (G, ) in which the set admits aG-invariant order. By aG-invariant partial order (G-partial order) we mean a partial order < of such that < implies g<g, for all and in andg inG. If the set admits aG-partial order which is a total order, then (G, ) is an O-permutation group (orderable permutation group).The main concern of this paper is the development of a foundation for partially ordered permutation groups analogous to the existing one for partially ordered groups, as found in Fuchs [2].     

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.     

Non removable edges in 3-connected cubic graphs

LetG be a cyclicallyk-edge-connected cubic graph withk 3. Lete be an edge ofG. LetG be the cubic graph obtained fromG by deletinge and its end vertices. The edgee is said to bek-removable ifG is also cyclicallyk-edge-connected. Let us denote by S _k (G) the graph induced by thek-removable edges and by N _k (G) the graph induced by the non 3-removable edges ofG. In a previous paper [7], we have proved that N ₃(G) is empty if and only ifG is cyclically 4-edge connected and that if N ₃(G) is not empty then it is a forest containing at least three trees. Andersen, Fleischner and Jackson [1] and, independently, McCuaig [11] studied N ₄(G). Here, we study the structure of N _k (G) fork 5 and we give some constructions of graphs such thatN _k (G) = E(G). We note that the main result of this paper (Theorem 5) has been announced independently by McCuaig [11].

---

Résumé SoitG un graphe cubique cyliquementk-arête-connexe, aveck 3. Soite une arête deG et soitG le graphe cubique obtenu à partir deG en supprimante et ses extrémités. L'arêtee est ditek-suppressible siG est aussi cycliquementk-arête-connexe. Désignons par S _k (G) le graphe induit par les arêtesk-suppressibles et par N _k (G) celui induit par les arêtes nonk-suppressibles. Dans un précédent article [7], nous avons montré que N ₃(G) est vide si et seulement siG est cycliquement 4-arête-connexe et que si N ₃(G) n'est pas vide alors c'est une forêt possédant au moins trois arbres. Andersen, Fleischner and Jackson [1] et, indépendemment, McCuaig [11] ont étudié N ₄(G). Ici, nous étudions la structure de N _k (G) pourk 5 et nous donnons des constructions de graphes pour lesquelsN _k (G) = E(G). Nous signalons que le résultat principal de cet article (Théorème 5) a été annoncé indépendamment par McCuaig [11].

     

Saturation on locally compact abelian groups: An extended theorem

Let G be a locally compact abelian group. The concern of the present note is to extend (for exponents p>2) the saturation theorem on G stated as Theorem 4 in [5]. The extension will be established for approximation processes (I_t)_t>0 acting on the submodule C^P(G), p]1,+[, of the convolutionM ¹(G)-module L^P(G) which consists of all functions fL^P(G) admitting as their Fourier transformsF _Gf (in the sense of the theory of quasimeasures) complex Radon measures not necessarily absolutely continuous with respect to any Haar measure on the dual group . Moreover, the relationship of the complex vector spaces C^P(G) to some other function spaces, in particular to the vector spaces B^P(G) introduced in [5], will be investigated.     

Incomplete orthogonal arrays and idempotent orthogonal arrays

First, we shall define idempotent orthogonal arrays and notice that idempotent orthogonal array of strength two are idempotent mutually orthogonal quasi-groups. Then, we shall state some properties of idempotent orthogonal arrays.Next, we shall prove that, starting from an incomplete orthogonal arrayT _EF based onE andF E, from an orthogonal arrayT _G based onG = E – F and from an idempotent orthogonal arrayT _H based onH, we are able to construct an incomplete orthogonal arrayT _(F(G×H))F based onF(G × H) andF. Finally, we shall show the relationship between the construction which lead us to this result and the singular direct product of mutually orthogonal quasi-groups given by Sade [5].     

On the Location of Roots of Independence Polynomials

The independence polynomial of a graph G is the function i(G, x) = _k0 i _k x ^k, where i _k is the number of independent sets of vertices in G of cardinality k. We prove that real roots of independence polynomials are dense in (–, 0], while complex roots are dense in , even when restricting to well covered or comparability graphs. Throughout, we exploit the fact that independence polynomials are essentially closed under graph composition.     

On the weighted Kneser-Poulsen conjecture

Suppose that p = (p1, p2, …, pN) and q = (q1, q2, …, qN) are two configurations in , which are centers of balls B ^d (p _i , r _i ) and B ^d (q _i , r _i ) of radius r _i , for i = 1, …, N. In [9] it was conjectured that if the pairwise distances between ball centers p are contracted in going to the centers q, then the volume of the union of the balls does not increase. For d = 2 this was proved in [1], and for the case when the centers are contracted continuously for all d in [2]. One extension of the Kneser-Poulsen conjecture, suggested in [6], was to consider various Boolean expressions in the unions and intersections of the balls, called flowers, where appropriate pairs of centers are only permitted to increase, and others are only permitted to decrease. Again under these distance constraints, the volume of the flower was conjectured to change in a monotone way. Here we show that these generalized Kneser-Poulsen flower conjectures are equivalent to an inequality between certain integrals of functions (called flower weight functions) over , where the functions in question are constructed from maximum and minimum operations applied to functions each being radially symmetric monotone decreasing and integrable. Research supported in part by NSF Grant No. DMS-0209595.     

The Domination Parameters of Cubic Graphs

Let ir(G), (G), i(G), ₀(G), (G) and IR(G) be the irredundance number, the domination number, the independent domination number, the independence number, the upper domination number and the upper irredundance number of a graph G, respectively. In this paper we show that for any nonnegative integers k₁, k₂, k₃, k₄, k₅ there exists a cubic graph G satisfying the following conditions: (G) – ir(G) k₁, i(G) – (G) k₂, ₀(G) – i(G) > k₃, (G) – ₀(G) – k₄, and IR(G) – (G) – k₅. This result settles a problem posed in [9].Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093).Supported by RUTCOR.     

Periods of residual representations of <Emphasis Type="Italic">SO</Emphasis>(2<Emphasis Type="Italic">l</Emphasis>)

In this paper, we extend the results on G₂-period of residual representations of SO₈ in [Jng98a], [Jng98b] to a generalized G₂-period of residual representations of SO_2l (l4). The period is expected to detect the nonvanishing of the relevant tensor product L-function at the center of the symmetry, which is a special case of the Gross- Prasad conjecture. More general cases will be considered in our forth-coming work [GJRa], [GJRb].The second named author is partially supported by NSF grant DMS-0098003 and the Sloan Research Fellowship.     

Zusammenhängende Untergruppen von pro-Lieschen Gruppen

In this paper we consider the lattice G of all closed connected subgroups of pro-Lie groups G, which seems to have in some sense a more geometric nature than the full lattice of all closed subgroups. We determine those pro-Lie groups whose lattice shares one of the elementary geometric lattice properties, such as the existence of complements and relative complements, semi-modularity and its dual, the chain condition, self-duality and related ones. Apart from these results dealing with subgroup lattices we also get two structure theorems, one saying that maximal closed analytic subgroups of Lie groups actually are maximal among all analytic subgroups, the other that each connected abelian pro-Lie group is a direct product of a compact group with copies of the reals.     

The Baer-invariant of a semidirect product

In 1972 K.I. Tahara [7,2, Theorem 2.2.5], using cohomological methods, showed that if a finite group is the semidirect product of a normal subgroup N and a subgroup T, then M(T) is a direct factor of M(G), where M(G) is the Schur-multiplicator of G and in the finite case, is the second cohomology group of G. In 1977 W. Haebich [1, Theorem 1.7] gave another proof using a different method for an arbitrary group G.In this paper we generalize the above theorem. We will show that scN_cM(T) is a direct factor of _cM(G), where _c[3, p. 102] is the variety of nilpotent groups of class at most c ≥ 1 and _cM(G) is the Baer-invariant of the group G with respect to the variety _c [3, p. 107].     

On a relative uniform completion of an archimedean lattice ordered group

The notion of a relatively uniform convergence (ru-convergence) has been used first in vector lattices and then in Archimedean lattice ordered groups. Let G be an Archimedean lattice ordered group. In the present paper, a relative uniform completion (ru-completion) of G is dealt with. It is known that exists and it is uniquely determined up to isomorphisms over G. The ru-completion of a finite direct product and of a completely subdirect product are established. We examine also whether certain properties of G remain valid in . Finally, we are interested in the existence of a greatest convex l-subgroup of G, which is complete with respect to ru-convergence. This work was supported by Science and Technology Assistance Agency under the contract No. APVT-20-004104. Supported by Grant VEGA 1/3003/06.     

Distinguished extensions of a lattice-ordered group

Any lattice-ordered group (l-group for short) is essentially extended by its lexicographic product with a totally ordered group. That is, anl-homomorphism (i.e., a group and lattice homomorphism) on the extension which is injective on thel-group must be injective on the extension as well. Thus nol-group has a maximal essential extension in the categoryIGp ofl-groups withl-homomorphisms. However, anl-group is a distributive lattice, and so has a maximal essential extension in the categoryD of distributive lattices with lattice homomorphisms. Adistinguished extension of onel-group by another is one which is essential inD. We characterize such extensions, and show that everyl-groupG has a maximal distinguished extensionE(G) which is unique up to anl-isomorphism overG.E(G) contains most other known completions in whichG is order dense, and has mostl-group completeness properties as a result. Finally, we show that ifG is projectable then E(G) is the -completion of the projectable hull ofG.Presented by M. Henriksen.     

Hjelmslevgruppen mit Nachbarhomomorphismus

Hjelmslev groups have been introduced by F. Bachmann ([1], [2]) in order to study plane metric geometries in a general sense: For example two points may have none or two lines joining them. Let (G,S) and (-G,¯ S) be Hjelmslev groups and let be a Hjelmslev homomorphism from (G,S) onto (¯G, ¯S). It is shown that — under certain assumptions — the group plane of (G, S) can be embedded into the projective Hjelmslev plane over a local ringR and thatG is isomorphic to a subgroup of an orthogonal group O ₃ ⁺ (V,f). The result may be considered as a generalization of the main theorem in Bachmann [1].     

Rotation numbers for complete tripartite graphs

Arooted graph is a pair (G, x), whereG is a simple undirected graph andx V(G). IfG is rooted atx, then itsrotation number h(G, x) is the minimum number of edges in a graphF of the same order asG such that for allv V(F), we can find a copy ofG inF with the rootx atv. Rotation numbers for all complete bipartite graphs are now known (see [2], [4], [7]). In this paper we calculate rotation numbers for complete tripartite graphs with rootx in the largest vertex class.Funded by the Science and Engineering Research Council.