Abelian networks III: The critical group

The critical group of an abelian network is a finite abelian group that governs the behavior of the network on large inputs. It generalizes the sandpile group of a graph. We show that the critical group of an irreducible abelian network acts freely and transitively on recurrent states of the network. We exhibit the critical group as a quotient of a free abelian group by a subgroup containing the image of the Laplacian, with equality in the case that the network is rectangular. We generalize Dhar’s burning algorithm to abelian networks and estimate the running time of an abelian network on an arbitrary input up to a constant additive error.     

Acylindrical accessibility for groups

We define the notion of acylindrical graph of groups of a group. We bound the combinatorics of these graphs of groups for f.g. freely indecomposable groups. Our arguments imply the finiteness of acylindrical surfaces in closed 3-manifolds [Ha], finiteness of isomorphism classes of small splittings of (torsion-free) freely indecomposable hyperbolic groups as well as finiteness results for small splittings of f.g. Kleinian and semisimple discrete groups acting on non-positively curved simply connected manifolds. In order to get our accessibility for f.g. groups we generalize parts of Rips' analysis of stable actions of f.p. groups on real trees to f.g. groups. The concepts we present play an essential role in constructing the canonical JSJ decomposition ([Se1],[Ri-Se2]), in obtaining the Hopf property for hyperbolic groups [Se2], and in our study of sets of solutions to equations in a free group [Se3]. Oblatum 30-IV-1992 & 1-X 1996     

Symmetries of directed graphs and the Chinese remainder theorem

It is shown that a permutation group on a finite set is the automorphism group of some directed graph if and only if a generalized Chinese remainder theorem holds for the family of stabilizers. This result can be applied to examine some special permutation groups, including the general linear groups of finite vector spaces.     

On bipartite divisor graphs for group conjugacy class sizes

In this paper we study various properties of a bipartite graph related to the sizes of the conjugacy classes of a finite group. It is proved that some invariants of the graph are rather strongly connected to the group structure. In particular we prove that the diameter is at most 6, and classify those groups for which the graphs have diameter 6. Moreover, if the graph is acyclic then the diameter is shown to be at most 5, and groups for which the graph is a path of length 5 are characterised.     

Pseudogroups of isometries of ℝ and Rips’ theorem on free actions on ℝ-trees

We give a proof of Rips’ theorem that a finitely generated group acting freely on an ℝ-tree is a free product of free abelian groups and surface groups, using methods of dynamical systems and measured foliations.     

A non-Abelian analogue of Whitney’s 2-isomorphism theorem

We give a non-Abelian analogue of Whitney’s 2-isomorphism theorem for graphs. Whitney’s theorem states that the cycle space determines a graph up to 2-isomorphism. Instead of considering the cycle space of a graph which is an Abelian object, we consider a mildly non-Abelian object, the 2-truncation of the group algebra of the fundamental group of the graph considered as a subalgebra of the 2-truncation of the group algebra of the free group on the edges. The analogue of Whitney’s theorem is that this is a complete invariant of 2-edge connected graphs: let G, G′ be 2-edge connected finite graphs; if there is a bijective correspondence between the edges of G and G′ that induces equality on the 2-truncations of the group algebras of the fundamental groups, then G and G′ are isomorphic.     

Roundness Properties of Groups

Roundness of metric spaces was introduced by Per Enflo as a tool to study uniform structures of linear topological spaces. The present paper investigates geometric and topological properties detected by the roundness of general metric spaces. In particular, we show that geodesic spaces of roundness 2 are contractible, and that a compact Riemannian manifold with roundness >1 must be simply connected. We then focus our investigation on Cayley graphs of finitely generated groups. One of our main results is that every Cayley graph of a free Abelian group on ⩾ 2 generators has roundness =1. We show that if a group has no Cayley graph of roundness =1, then it must be a torsion group with every element of order 2,3,5, or 7 Partially supported by a Canisius College Summer Research Grant     

Prographes sylvestres et groupes profinis presque libres

In this article we want to give an analogous in the profinite case to the following theorem: an abstract group is free if and only if it acts freely on a tree. In a first time we define a combinatory object, the protrees, which are particular inductive systems extracted from projective systems of graphs. Then we define a notion of profinite action. These objects allow us to give the following analogous: a profinite group contains a dense abstract free subgroup if and only if it acts profreely on a protree.     

The normalized cyclomatic quotient associated with presentations of finitely generated groups

Given a presentation of ann-generated group, we define the normalized cyclomatic quotient (NCQ) of it, which gives a number between 1−n and 1. It is computed through an investigation of the asymptotic behavior of a kind of an “average rank”, or more precisely the quotient of the rank of the fundamental group of a finite subgraph of the corresponding Cayley graph by the size of the subgraph. In many ways (but not always) the NCQ behaves similarly to the behavior of the spectral radius of a symmetric random walk on the graph. In particular, it characterizes amenable groups. For some types of groups, like finite, amenable or free groups, its value equals that of the Euler characteristic of the group. We give bounds for the value of the NCQ for factor groups and subgroups, and formulas for its value on direct and free products. Some other asymptotic invariants are also discussed.     

Strong Connectivity of Polyhedral Complexes

A classical theorem of Robbins states that the edges of a graph may be oriented, in such a way that an oriented path exists between any source and destination, if and only if the graph is both connected and two-connected (it cannot be disconnected by the removal of an edge). In this paper, an algebraic version of Robbins' result becomes a lemma on Hilbert bases for free abelian groups, which is then applied to generalize his theorem to higher dimensional complexes. An application to cycle bases for graphs is given, and various examples are presented.     

二面体群D_(2n)的4度正规Cayley图

设G是有限群,S是G的不包含单位元1的非空子集．定义群G关于S的 Cayley(有向)图X=Cay(G,S)如下:V(x)=G,E(X)={(g,sg)|g∈G,s∈S}． Cayley图X=Cay(G,S)称为正规的如果R(G)在它的全自同构群中正规．图X称为1-正则的如果它的全自同构群在它的弧集上正则作用．本文对二面体群D2n以Z22 为点稳定子的4度正规Cayley图进行了分类．     

Fitting Height and Diameter of Character Degree Graphs

Let a graph Γ have bounded Fitting height (i.e., there is a bound on the Fitting heights of those groups whose character degree graph is Γ) and G be any solvable group with character degree graph Γ and Fitting height h(G). We improve Moretò's bound by proving that if no vertex in Γ is adjacent to every other one, then h(G) ≤4, else h(G) ≤6. As a consequence, if a solvable group G has character degree graph with diameter 3, then h(G) ≤4. Moreover, G has at most one non-abelian normal Sylow subgroup in this case.     

Planar subgroup lattices

In this paper we determine all finite groups with planar subgroup lattices. For this, by Kuratowski’s theorem, we have to study subdivisions of the Kuratowski graphs K_3,3 and K₅ in the covering graph of the subgroup lattice of a finite group. It turns out that such a graph is planar if and only if it contains no subdivision of K_3,3. Received April 28, 2005; accepted in final form August 28, 2005.     

Hamiltonian cycles in cayley color graphs

A group Γ is said to possess a hamiltonian generating set if there exists a minimal generating set Δ for Γ such that the Cayley color graph D_Δ(Γ) is hamiltonian. It is shown that every finite abelian group has a hamiltonian generating set. Certain classes of nonabelian groups are also investigated.     

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is n‐HC‐extendable if it contains a path of length n and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is weakly n‐HP‐extendable if it contains a path of length n and if every such path is contained in some Hamilton path of Γ. Moreover, Γ is strongly n‐HP‐extendable if it contains a path of length n and if for every such path P there is a Hamilton path of Γ starting with P. These concepts are then studied for the class of connected Cayley graphs on abelian groups. It is proved that every connected Cayley graph on an abelian group of order at least three is 2‐HC‐extendable and a complete classification of 3‐HC‐extendable connected Cayley graphs of abelian groups is obtained. Moreover, it is proved that every connected Cayley graph on an abelian group of order at least five is weakly 4‐HP‐extendable. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

The colorings of homeomorphisms on connected graphs

In this paper, we decide the exact value of the color number of a fixed point free homeomorphism on a connected locally finite graph. We prove that for every fixed-point free homeomorphism from a connected locally finite graph into itself, the greatest common divisor of all period for its map is equal to one or three if and only if its color number is 4.     

Tetravalent one-regular graphs of order 2<Emphasis Type="Italic">pq</Emphasis>

A graph is one-regular if its automorphism group acts regularly on the set of its arcs. In this article a complete classification of tetravalent one-regular graphs of order twice a product of two primes is given. It follows from this classification that with the exception of four graphs of orders 12 and 30, all such graphs are Cayley graphs on Abelian, dihedral, or generalized dihedral groups.     

The power graph of a finite group

The power graph of a group is the graph whose vertex set is the group, two elements being adjacent if one is a power of the other. We observe that non-isomorphic finite groups may have isomorphic power graphs, but that finite abelian groups with isomorphic power graphs must be isomorphic. We conjecture that two finite groups with isomorphic power graphs have the same number of elements of each order. We also show that the only finite group whose automorphism group is the same as that of its power graph is the Klein group of order 4.     

Coût des relations d’équivalence et des groupes

We study a new dynamical invariant for dicrete groups: the cost. It is a real number in {1−1/n}∪[1,∞], bounded by the number of generators of the group, and it is well behaved with respect to finite index subgroups. Namely, the quantities 1 minus the cost are related by multiplying by the index. The cost of every infinite amenable group equals 1. We compute it in some other situations, including free products, free products with amalgamation and HNN-extensions over amenable groups and for direct product situations. For instance, the cost of the free group on n generators equals n. We prove that each possible finite value of the cost is achieved by a finitely generated group. It is dynamical because it relies on measure preserving free actions on probability Borel spaces. In most cases, groups have fixed price, which implies that two freely acting groups which define the same orbit partition must have the same cost. It enables us to distinguish the orbit partitions of probability-preserving free actions of free groups of different ranks. At the end of the paper, we give a mercuriale, i.e. a list of costs of different groups. The cost is in fact an invariant of ergodic measure-preserving equivalence relations and is defined using graphings. A treeing is a measurable way to provide every equivalence class (=orbit) with the structure of a simplicial tree, this an example of graphing. Not every relation admits a treeing: we prove that every free action of a cost 1 non-amenable group is not treeable, but we prove that subrelations of treeable relations are treeable. We give examples of relations which cannot be produced by an action of any finitely generated group. The cost of a relation which can be decomposed as a direct product is shown to be 1. We define the notion for a relation to be a free product or an HNN-extension and compute the cost for the resulting relation from the costs of the building blocks. The cost is also an invariant of the pairs von Neumann algebra/Cartan subalgebra. Oblatum 27-I-1999 & 4-IV-1999 / Published online: 22 September 1999     

Heptavalent Symmetric Graphs with Certain Conditions

A graph Γ is said to be symmetric if its automorphism group Aut(Γ)acts transitively on the arc set of Γ.We show that if Γ is a finite connected heptavalent symmetric graph with solvable stabilizer admitting a vertex-transitive non-abelian simple group G of automorphisms,then either G is normal in Aut(Γ),or Aut(Γ)contains a non-abelian simple normal subgroup T such that G≤T and(G,T)is explicitly given as one of 11 possible exceptional pairs of non-abelian simple groups.If G is arc-transitive,then G is always normal in Aut(r),and if G is regular on the vertices of Γ,then the number of possible exceptional pairs(G,T)is reduced to 5.