The tree lattice existence theoremsLes théorèmes d'existence de réseaux associés aux arbres

Let X be a locally finite tree, and let G=Aut(X). Then G is a locally compact group. In analogy with Lie groups, Bass and Lubotzky conjectured that G contains lattices, that is, discrete subgroups whose quotient carries a finite invariant measure. Bass and Kulkarni showed that G contains uniform lattices if and only if G is unimodular and G?X is finite. We describe the necessary and sufficient conditions for G to contain lattices, both uniform and non-uniform, answering the Bass–Lubotzky conjectures in full. To cite this article: L. Carbone, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 223–228.     

On the Bergman Property for the Automorphism Groups of Relatively Free Groups

A group G is said to have the Bergman property (the propertyof uniformity of finite width) if given any generating X withX = X^–1 of G, we have that G = X^k for some natural k,that is, every element of G is a product of at most k elementsof X. We prove that the automorphism group Aut(N) of any infinitelygenerated free nilpotent group N has the Bergman property. Also,we obtain a partial answer to a question posed by Bergman byestablishing that the automorphism group of a free group ofcountably infinite rank is a group of uniformly finite width.     

On tree‐decompositions of one‐ended graphs

A graph is one‐ended if it contains a ray (a one way infinite path) and whenever we remove a finite number of vertices from the graph then what remains has only one component which contains rays. A vertex v dominates a ray in the end if there are infinitely many paths connecting v to the ray such that any two of these paths have only the vertex v in common. We prove that if a one‐ended graph contains no ray which is dominated by a vertex and no infinite family of pairwise disjoint rays, then it has a tree‐decomposition such that the decomposition tree is one‐ended and the tree‐decomposition is invariant under the group of automorphisms. This can be applied to prove a conjecture of Halin from 2000 that the automorphism group of such a graph cannot be countably infinite and solves a recent problem of Boutin and Imrich. Furthermore, it implies that every transitive one‐ended graph contains an infinite family of pairwise disjoint rays.     

Bass-Tits minimization of automata, quotients of trees and diameters

Let X be a tree and let G=Aut(X), Bass and Tits have given an algorithm to construct the ‘ultimate quotient’ of X by G starting with any quotient of X, an ‘edge-indexed’ graph. Using a sequence of integers that we compute at consecutive steps of the Bass-Tits (BT) algorithm, we give a lower bound on the diameter of the ultimate quotient of a tree by its automorphism group. For a tree X with finite quotient, this gives a lower bound on the minimum number of generators of a uniform X-lattice whose quotient graph coincides with G?X. This also gives a criterion to determine if the ultimate quotient of a tree is infinite. We construct an edge-indexed graph (A,i) for a deterministic finite state automaton and show that the BT algorithm for computing the ultimate quotient of (A,i) coincides with state minimizing algorithm for finite state automata. We obtain a lower bound on the minimum number of states of the minimized automaton. This gives a new proof that language for the word problem in a finitely generated group is regular if and only if the group is finite, and a new proof that the language of the membership problem for a subgroup is regular if and only if the subgroup has finite index.     

On end degrees and infinite cycles in locally finite graphs

We introduce a natural extension of the vertex degree to ends. For the cycle space C(G) as proposed by Diestel and Kühn [4, 5], which allows for infinite cycles, we prove that the edge set of a locally finite graph G lies in C(G) if and only if every vertex and every end has even degree. In the same way we generalise to locally finite graphs the characterisation of the cycles in a finite graph as its 2-regular connected subgraphs.     

Biplanes with flag-transitive automorphism groups of almost simple type,with exceptional socle of Lie type

In this paper we prove that there is no biplane admitting a flag-transitive automorphism group of almost simple type, with exceptional socle of Lie type. A biplane is a (v,k,2)-symmetric design, and a flag is an incident point-block pair. A group G is almost simple with socle X if X is the product of all the minimal normal subgroups of G, and X⊴G≤Aut (G). Throughout this work we use the classification of finite simple groups, as well as results from P.B. Kleidman’s Ph.D. thesis which have not been published elsewhere.     

On automorphisms of infinite graphs with forbidden subgraphs

LexX be anm-connected infinite graph without subgraphs homeomorphic toKm, n, for somen, and let α be an automorphism ofX with at least one cycle of infinite length. We characterize the structure of α and use this characterization to extend a known result about orientation-preserving automorphisms of finite plane graphs to infinite plane graphs. In the last section we investigate the action of α on the ends ofX and show that α fixes at most two ends (Theorem 3.2).     

On a Problem of Cameron’s on Inexhaustible Graphs

A graph G is inexhaustible if whenever a vertex of G is deleted the remaining graph is isomorphic to G. We address a question of Cameron [6], who asked which countable graphs are inexhaustible. In particular, we prove that there are continuum many countable inexhaustible graphs with properties in common with the infinite random graph, including adjacency properties and universality. Locally finite inexhaustible graphs and forests are investigated, as is a semigroup structure on the class of inexhaustible graphs. We extend a result of [7] on homogeneous inexhaustible graphs to pseudo-homogeneous inexhaustible graphs.The authors gratefully acknowledge support from the Natural Science and Engineering Research Council of Canada (NSERC).     

On products of graphs and regular groups

A graphX is called a graphical regular representation (GRR) of a groupG if the automorphism group ofX is regular and isomorphic toG. Watkins and Nowitz have shown that the direct productG×H of two finite groupsG andH has aGRR if both factors have aGRR and if at least one factor is different from the cyclic group of order two. We give a new proof of this result, thereby removing the restriction to finite groups. We further show that the complementX′ of a finite or infinite graphX is prime with respect to cartesian multiplication ifX is composite and not one of six exceptional graphs.     

On the reconstruction of locally finite trees

We prove a theorem saying, when taken together with previous results of Bondy, Hemminger, and Thomassen, that every locally finite, infinite tree not containing a subdivision of the dyadic tree (i. e., the regular tree of degree 3) is uniquely determined, up to isomorphism, from its collection of vertex-deleted subgraphs. Furthermore, as another partial result concerning the reconstruction of locally finite trees, we show that the same is true for locally finite trees whose set of vertices of degree s is nonempty and finite (for some positive integer s).     

Countable structures with a fixed group of automorphisms

We prove that, given a countable groupG, the set of countable structures (for a suitable languageL)U _G whose automorphism group is isomorphic toG is a complete coanalytic set and ifG ≄H thenU _G is Borel inseparable fromU _H . We give also a model theoretic interpretation of this result. We prove, in contrast, that the set of countable structures forL whose automorphism group is isomorphic to ℤ _p ^ℕ ,p a prime number, is Π ₁ ¹ &σ ₁ ¹ -complete.     

Extension of locally pseudocompact group actions

It is shown that: (1) any action of a Moscow group G on a first countable, Dieudonné complete (in particular, on a metrizable) space X can uniquely be extended to an action of the Dieudonné completion γG on X, (2) any action of a locally pseudocompact topological group G on a b _f -space (in particular, on a first countable space) X can uniquely be extended to an action of the Weil completion on the Dieudonné completion γX of X. As a consequence, we obtain that, for each locally pseudocompact topological group G, every G-space with the b _f -property admits an equivariant embedding into a compact Hausdorff G-space. Furthermore, for each pseudocompact group G, every metrizable G-space has a G-invariant metric compatible with its topology. We also give a direct construction of such an invariant metric. Received: June 22, 2000; in final form: May 22, 2001?Published online: June 11, 2002     

Oligomorphic clones

A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its set of permutations forms an oligomorphic permutation group. There is a close relationship to ω-categorical structures, i.e., countably infinite structures with a first-order theory that has only one countable model, up to isomorphism. Every locally closed oligomorphic permutation group is the automorphism group of an ω-categorical structure, and conversely, the canonical structure of an oligomorphic permutation group is an ω-categorical structure that contains all first-order definable relations. There is a similar Galois connection between locally closed oligomorphic clones and ω-categorical structures containing all primitive positive definable relations. In this article we generalise some fundamental theorems of universal algebra from clones over a finite domain to oligomorphic clones. First, we define minimal oligomorphic clones, and present equivalent characterisations of minimality, and then generalise Rosenberg’s five types classification to minimal oligomorphic clones. We also present a generalisation of the theorem of Baker and Pixley to oligomorphic clones. Presented by A. Szendrei. Received July 12, 2005; accepted in final form August 29, 2006.     

Metrical characterization of super-reflexivity and linear type of Banach spaces

We prove that a Banach space X is not super-reflexive if and only if the hyperbolic infinite tree embeds metrically into X. We improve one implication of J.Bourgain’s result who gave a metrical characterization of super-reflexivity in Banach spaces in terms of uniform embeddings of the finite trees. A characterization of the linear type for Banach spaces is given using the embedding of the infinite tree equipped with the metrics d _p induced by the ℓ _p norms. Received: 2 August 2006, Revised: 10 April 2007     

Twisted Conjugacy Classes for Polyfree Groups

Let G be a finitely generated polyfree group. If G has nonzero Euler characteristic then we show that Aut(G) has a finite index subgroup in which every automorphism has infinite Reidemeister number. For certain G of length 2, we show that the number of Reidemeister classes of every automorphism is infinite.     

Nonamenable products are not treeable

LetX andY be infinite graphs such that the automorphism group ofX is nonamenable and the automorphism group ofY has an infinite orbit. We prove that there is no automorphism-invariant measure on the set of spanning trees in the direct productX×Y. This implies that the minimal spanning forest corresponding to i.i.d. edge-weights in such a product has infinitely many connected components almost surely. Research partially supported by NSF grant DMS-9803597.     

On Infinite Camina Groups

A group G is called a Camina group if G′ ≠ G and each element x ∈ G?G′ satisfies the equation x ^G  = xG′, where x ^G denotes the conjugacy class of x in G. Finite Camina groups were introduced by Alan Camina in 1978, and they had been studied since then by many authors. In this article, we start the study of infinite Camina groups. In particular, we characterize infinite Camina groups with a finite G′ (see Theorem 3.1) and we show that infinite non-abelian finitely generated Camina groups must be nonsolvable (see Theorem 4.3). We also describe locally finite Camina groups, residually finite Camina groups (see Section 3) and some periodic solvable Camina groups (see Section 5).     

Groupes Moyennables, Dimension Topologique Moyenne et sous-décalages

Let G be an infinite countable residually finite amenable group. In this paper we construct a continuous action of G on a compact metrisable space X such that the dynamical system (X, G) cannot be embedded in the G-shift on [0,1] ^G . This result generalizes a construction due to E. Lindenstrauss and B. Weiss (Mean topological dimension, Israel J. Math. 115 (2000), 1–24) for .