Quasi-isometries between graphs and trees

Criteria for quasi-isometry between trees and general graphs as well as for quasi-isometries between metrically almost transitive graphs and trees are found. Thereby we use different concepts of thickness for graphs, ends and end spaces. A metrically almost transitive graph is quasi-isometric to a tree if and only if it has only thin metric ends (in the sense of Definition 3.6). If a graph is quasi-isometric to a tree then there is a one-to-one correspondence between the metric ends and those d-fibers which contain a quasi-geodesic. The graphs considered in this paper are not necessarily locally finite.     

The action of nilpotent groups on infinite graphs

First we prove a result about the action of nilpotent groups on the set of ends of locally finite graphs. This theorem has immediate consequences for the structure of graphs which allow a transitive action of those groups. Further we investigate the cycle-structure of automorphisms of a transitive nilpotent group and the existence of abelian groups acting on sets of imprimitivity of graphs whose automorphism groups have transitive nilpotent subgroups.     

超立方体Q_n的传递剖分

一个图的传递剖分是它的边集的一个划分,且满足图的一个自同构群在其划分后的各个部分组成的集合上作用是传递的.决定了超立方体Q_n的所有G-传递剖分,其中G为Q_n的全自同构群.     

A note on bounded automorphisms of infinite graphs

LetX be a connected locally finite graph with vertex-transitive automorphism group. IfX has polynomial growth then the set of all bounded automorphisms of finite order is a locally finite, periodic normal subgroup ofAUT(X) and the action ofAUT(X) onV(X) is imprimitive ifX is not finite. IfX has infinitely many ends, the group of bounded automorphisms itself is locally finite and periodic.     

Factor group of the automorphism group of a matroid basis graph with respect to the automorphism group of the matroid

Any automorphism of a matroid induces an automorphism of its basis graph. We try to determine what can be said concerning the automorphisms of the basis graph which are not induced by matroids' automorphisms. In particular, we determine the structure of the factor group of the automorphism group of the basis graph with respect to the automorphism group of the matroid, in the event that this factor group exists.     

A design and a geometry for the group Fi 22

The Fischer group Fi ₂₂ acts as a rank 3 group of automorphisms of a symmetric 2-(14080,1444,148) design. This design does not have a doubly transitive automorphism group, since there is a partial linear space with lines of size 4 defined combinatorially from the design and preserved by its automorphism group. We investigate this geometry and determine the structure of various subspaces of it.      

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.     

Rank 3 Transitive Decompositions of Complete Multipartite Graphs

A transitive decomposition of a graph is a partition of the edge or arc set giving a set of subgraphs which are preserved and permuted transitively by a group of automorphisms of the graph. This paper deals with transitive decompositions of complete multipartite graphs preserved by an imprimitive rank 3 permutation group. We obtain a near-complete classification of these when the group in question has an almost simple component.     

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

Hadamard matrices of order 28 with automorphisms of order 7

The only primes which can divide the order of the automorphism group of a Hadamard matrix of order 28 are 13, 7, 3, and 2, and there are precisely four inequivalent matrices with automorphisms of order 13 (Tonchev, J. Combin. Theory Ser. A35 (1983), 43–57). In this paper we show that there are exactly twelve inequivalent Hadamard matrices of order 28 with automorphisms of order 7. In particular, there are precisely seven matrices with transitive automorphism groups.     

An Interlacing Technique for Spectra of Random Walks and Its Application to Finite Percolation Clusters

A comparison technique for random walks on finite graphs is introduced, using the well-known interlacing method. It yields improved return probability bounds. A key feature is the incorporation of parts of the spectrum of the transition matrix other than just the principal eigenvalue. As an application, an upper bound of the expected return probability of a random walk with symmetric transition probabilities is found. In this case, the state space is a random partial graph of a regular graph of bounded geometry and transitive automorphism group. The law of the random edge-set is assumed to be invariant with respect to some transitive subgroup of the automorphism group (‘invariant percolation’). Given that this subgroup is unimodular, it is shown that this invariance strengthens the upper bound of the expected return probability, compared with standard bounds such as those derived from the Cheeger inequality. The improvement is monotone in the degree of the underlying transitive graph.     

Vertex Cuts

Given a connected graph, in many cases it is possible to construct a structure tree that provides information about the ends of the graph or its connectivity. For example Stallings' theorem on the structure of groups with more than one end can be proved by analyzing the action of the group on a structure tree and Tutte used a structure tree to investigate finite 2‐connected graphs, that are not 3‐connected. Most of these structure tree theories have been based on edge cuts, which are components of the graph obtained by removing finitely many edges. A new axiomatic theory is described here using vertex cuts, components of the graph obtained by removing finitely many vertices. This generalizes Tutte's decomposition of 2‐connected graphs to k‐connected graphs for any k, in finite and infinite graphs. The theory can be applied to nonlocally finite graphs with more than one vertex end, i.e. ends that can be separated by removing a finite number of vertices. This gives a decomposition for a group acting on such a graph, generalizing Stallings' theorem. Further applications include the classification of distance transitive graphs and k‐CS‐transitive graphs.     

非拟本原（PSU3（P），2）-弧传递图的外自同构

证明由GF（p^2）的域自同构可以产生一类非拟本原（PSU3（P），2）-弧传递图的白同构，并研究了这样的自同构与图的传递自同构群中心化予的关系。     

Invariant gauge automorphisms of homogeneous principal bundles

The inner and outer automorphism groups of a Lie group are generalized by considering automorphisms in the category of homogeneous principal bundles. These automorphisms are then used to produce certain invariant gauge transformations of such bundles. Some aspects of the resulting action on the space of invariant connections are also described.     

The automorphism space Σ(G) of a domain without punctiform prime ends

Let G ⊆ ℂ be a simply connected domain and let Σ (G) be its group of conformal automorphisms with the topology of uniform chordal convergence on G. In 1984 Gaier raised the question whether the connectedness of the space Σ (G) implies that the domain G has only punctiform prime ends. As a contribution to answering this question in this paper the authors use suitable spike Junctions to construct a bounded domain without any punctiform prime end such that its automorphism space Σ (G) is not discrete, but totally disconnected.     

On a Roelcke-precompact Polish group that cannot act transitively on a complete metric space

We study when a continuous isometric action of a Polish group on a complete metric space is, or can be, transitive. Our main results consist of showing that for certain Polish groups, namely Aut* (μ) and Homeo+ [0, 1], such an action can never be transitive (unless the space acted upon is a singleton).We also point out that in all known examples, this pathology coincides with the pathology of Polish groups that are not closed permutation groups and yet have discrete uniform distance, asking whether there is a relation. We conclude with a general characterisation/classification of transitive continuous isometric actions of a Roelcke-precompact Polish group on a complete metric space. In particular, the morphism from a Roelcke-precompact Polish group to its Bohr compactification is surjective.     

Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration

A graph is called a semi-regular graph if its automorphism group action on its ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficient condition for an automorphism of the graph F to be an automorphism of a map with the underlying graph F is obtained. Using this result, all orientation-preserving automorphisms of maps on surfaces (orientable and non-orientable) or just orientable surfaces with a given underlying semi-regular graph F are determined. Formulas for the numbers of non-equivalent embeddings of this kind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, the non-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable and general surfaces are enumerated.     

Even signings,signed switching classes,and (−1, 1)-matrices

In this paper, algebraic and combinatorial techniques are used to establish results concerning even signings of graphs, switching classes of signed graphs, and (?1, 1)-matrices. These results primarily deal with enumeration of isomorphism types, and determining whether there are fixed elements under the action of automorphisms. A formula is given for the number of isomorphism types of even signings of any fixed simple graph. This is shown to be equal to the number of isomorphism types of switching classes of signings of the graph. A necessary and sufficient criterion is found for all switching classes fixed by a given graph automorphism to contain signings fixed by that automorphism. It is determined whether this criterion is met for all automorphisms of various graphs, including complete graphs, which yields a known result of Mallows and Sloane. As an application, a formula is developed for the number of H-equivalence classes of (?1, 1)-matrices of fixed size. Independently, using Molien's theorem and following a suggestion of Cameron's, generating series for these numbers are given. As a final application, a necessary and sufficient condition that a square (?1, 1)-matrix be switching equivalent to a symmetric matrix is given.