Search

In this paper we derive a generating series for the number of cellular complexes known as pavings or three-dimensional maps, on n darts, thus solving an analogue of Tutte's problem in dimension three. The generating series we derive also counts free subgroups of index n in Δ + = Z 2 ∗ Z 2 ∗ Z 2 via a simple bijection between pavings and finite index subgroups which can be deduced from the action of Δ + on the cosets of a given subgroup. We then show that this generating series is non-holonomic. Furthermore, we provide and study the generating series for isomorphism classes of pavings, which correspond to conjugacy classes of free subgroups of finite index in Δ + . Computational experiments performed with software designed by the authors provide some statistics about the topology and combinatorics of pavings on n ≤ 16 darts. [ABSTRACT FROM AUTHOR]

We show that the full set of solutions to systems of equations and inequations in a hyperbolic group, as shortlex geodesic words (or any regular set of quasigeodesic normal forms), is an EDT0L language whose specification can be computed in NSPACE(n2 log n) for the torsion-free case and NSPACE(n4 log n) in the torsion case. Furthermore, in the presence of effective quasi-isometrically embeddable rational constraints, we show that the full set of solutions to systems of equations in a hyperbolic group remains EDT0L. Our work combines the geometric results of Rips, Sela, Dahmani and Guirardel on the decidability of the existential theory of hyperbolic groups with the work of computer scientists including Plandowski, Jeż, Diekert and others on PSPACE algorithms to solve equations in free monoids and groups using compression, and involves an intricate language-theoretic analysis. [ABSTRACT FROM AUTHOR]

In this paper, we exhibit two infinite families of trees $$\{T^1_n\}_{n \ge 17}$$ and $$\{T^2_n\}_{n \ge 17}$$ on n vertices, such that $$T^1_n$$ and $$T^2_n$$ are non-isomorphic, co-spectral, with co-spectral complements, and the right-angled Coxeter groups (RACGs) based on $$T^1_n$$ and $$T^2_n$$ have the same geodesic growth with respect to the standard generating set. We then show that the spectrum of a tree is not sufficient to determine the geodesic growth of the RACG based on that tree, by providing two infinite families of trees $$\{S^1_n\}_{n \ge 11}$$ and $$\{S^2_n\}_{n \ge 11}$$ , on n vertices, such that $$S^1_n$$ and $$S^2_n$$ are non-isomorphic, co-spectral, with co-spectral complements, and the RACGs based on $$S^1_n$$ and $$S^2_n$$ have distinct geodesic growth. Asymptotically, as $$n\rightarrow \infty $$ , each set $$T^i_n$$ , or $$S^i_n$$ , $$i=1,2$$ , has the cardinality of the set of all trees on n vertices. Our proofs are constructive and use two families of trees previously studied by B. McKay and C. Godsil. [ABSTRACT FROM AUTHOR]

We study the regularity of several languages derived from conjugacy classes in a finitely generated group G for a variety of examples including word hyperbolic, virtually abelian, Artin, and Garside groups. We also determine the rationality of the growth series of the shortlex conjugacy language in virtually cyclic groups, proving one direction of a conjecture of Rivin. [ABSTRACT FROM AUTHOR]

Let F be a free group of finite rank. We say that the monomorphism problem in F is decidable if there is an algorithm such that, for any two elements u and v in F, it determines whether there exists a monomorphism of F that sends u to v. In this paper we show that the monomorphism problem is decidable and we provide an effective algorithm that solves the problem. [ABSTRACT FROM AUTHOR]