Discrete groups of slow subgroup growth

It is known that the subgroup growth of finitely generated linear groups is either polynomial or at least $n^{\frac{{\log n}}{{\log \log n}}} $ . In this paper we prove the existence of a finitely generated group whose subgroup growth is of type $n^{\frac{{\log n}}{{(\log \log n)^2 }}} $ . This is the slowest non-polynomial subgroup growth obtained so far for finitely generated groups. The subgroup growth typen ^logn is also realized. The proofs involve analysis of the subgroup structure of finite alternating groups and finite simple groups in general. For example, we show there is an absolute constantc such that, ifT is any finite simple group, thenT has at mostn ^{c logn} subgroups of indexn.     

Dense graphs and edge reconstruction

By a well-known result of Nash-Williams if a graphG is not edge reconstructible, then for all ,|A||E(G)| mod 2 we have a permutation ofV(G) such thatE(G)E(G)=A. Here we construct infinitely many graphsG having this curious property and more than edges.Research (partially) supported by Hungarian National Foundation for Scientific Research Grant No.T016389.     

Groups with super-exponential subgroup growth

We show that, if the subgroup growth of a finitely generated (abstract or profinite) groupG is super-exponential, then every finite group occurs as a quotient of a finite index subgroup ofG. The proof involves techniques from finite permutation groups, and depends on the Classification of Finite Simple Groups.The first author was partially supported by the Hungarian National Foundation for Scientific Research, Grant No. T7441. The second author was partially supported by the Israeli National Science Foundation.     

A Bound for the Diameter of Distance-Regular Graphs

n vertices has diameter at most 5 logn. This essentially settles a problem of Brouwer, Cohen and Neumaier. Received: October 2, 1998     

Regular subgraphs of dense graphs

Every graph onn vertices, with at leastc _k n logn edges contains ak-regular subgraph. This answers a question of Erdős and Sauer.     

Clique covering of graphs

Let cc(G) denote the least number of complete subgraphs necessary to cover the edges of a graphG. Erd?s conjectured that for a graphG onn vertices $$cc(G) + cc(\bar G) \leqq \frac{1}{4}n^2 + 2$$ ifn is sufficiently large. We prove this conjecture.     

A generalization of the diameter bound of Liebeck and Shalev for finite simple groups

Acta Mathematica Hungarica - Let $$G$$ be a non-abelian finite simple group. A famous result of Liebeck and Shalev is that there is an absolute constant $$c$$ such that whenever $$S$$ is a...     

Bounded Generation and Subgroup Growth

The author proves in this paper that every profinite group Gwith polynomial subgroup growth is boundedly generated; thatis, it is a product of finitely many procyclic subgroups. Thisanswers a question of P. Zalesskii. By contrast, if G is a boundedlygenerated group, then the subgroup growth of G is at most n^clogn.As a byproduct, a short, elementary proof demonstrates thatAut(F_r) (for r 2) and many other related groups are not boundedlygenerated. 2000 Mathematics Subject Classification 20E07 (primary),20E22 (secondary).     

The edge reconstruction of hamiltonian graphs

If a graph G on n vertices contains a Hamiltonian path, then G is reconstructible from its edge-deleted subgraphs for n sufficiently large.