Questions tagged [combinatorial-group-theory]

Filter by
Sorted by
Tagged with
5 votes
1 answer
271 views

Is this semi-direct product residually finite?

I've copied over this question from what I asked on Mathematics Stack Exchange, in the hope that some experts here can help me find a way to check the residual finiteness of this group. Consider the ...
user avatar
  • 233
5 votes
0 answers
107 views

Can we define partial group actions on (finite) sets via generators and relators?

Let $G = \langle Y | R \rangle$ be a finitely presented group. A partial group action on a set $X$ is a premorphism into the inverse semigroup $$ \mathcal I (X) = \{ f: A \to B : A, B \subseteq X, f\...
user avatar
3 votes
0 answers
176 views

Permuting subgroups with the same finite index

Suppose that we have a finitely generated residually finite group $G = \langle g_1,\ldots,g_r \rangle$ with polynomial growth. Let $H$ be a subgroup of $G$ with finite index $m$. Let $\phi$ be an ...
user avatar
  • 233
1 vote
1 answer
174 views

Which properties can be read off the balls of a Cayley graph?

For which properties (P) [of groups] does the following hold: given a group $G$ which has a finite presentation with at most $n$ relations of length at most $\ell$, there is a $R(n,\ell)$ so that, if ...
user avatar
  • 4,214
8 votes
1 answer
235 views

When are biautomatic groups hyperbolic?

This list of open problems from http://grouptheory.info/ includes the question: "Is every biautomatic group which does not contain any $\mathbb{Z} \times \mathbb{Z}$ subgroups, hyperbolic?" ...
user avatar
9 votes
1 answer
267 views

Finite presentability of semi-direct product of free group and its commutator subgroup

Let $F_n$ be a free group of rank $n \geq 2$. The group $F_n$ acts on its commutator subgroup $[F_n,\, F_n]$ by conjugation. Let $G = [F_n,\, F_n] \rtimes F_n$. It's not hard to see that $G$ is ...
user avatar
  • 93
7 votes
0 answers
157 views

Completeness of automorphism groups of free metabelian groups

I am not very familiar with free metabelian groups, so I apologise in advance if this is trivial. A group $G$ is said to be complete if every automorphism of $G$ is inner. In this case, $\operatorname{...
user avatar
4 votes
0 answers
112 views

Uniform word problem in finitely presented simple groups

The following question arose in the comments on this question, and it seems like a reasonable question to ask in its own right. I've added some additional details. The word problem in any fixed ...
user avatar
9 votes
3 answers
333 views

Subgroups of RAAGs vs. subgroups of RACGs

Is a (finitely generated) torsion-free subgroup of a right-angled Coxeter group isomorphic to a subgroup of a right-angled Artin group? It is well-known from the theory of special cube complexes that ...
user avatar
  • 6,053
12 votes
1 answer
323 views

Commutator problem vs conjugacy/word problem

For a finitely presented group $G$, generated by a finite set $A$, the commutator problem is the decision problem: given a word $w$ over the alphabet $A \cup A^{-1}$, can one decide if $w$ is a ...
user avatar
9 votes
1 answer
243 views

Largest Hopfian quotient

Let $\Gamma$ be a group, say finitely generated if it helps. Does $\Gamma$ admit a largest Hopfian quotient? That is, does there exist a Hopfian quotient $H$ of $\Gamma$, such that every surjective ...
user avatar
  • 435
7 votes
1 answer
160 views

Howson property of automorphism group of $F_2$ and of $F_3$

Is the intersection of any two finitely generated subgroups of $\operatorname{Aut}(F_2)$ (resp. $\operatorname{Aut}(F_3)$) again finitely generated? That is, does $\operatorname{Aut}(F_2)$ (resp. $\...
user avatar
7 votes
0 answers
82 views

The conjugacy problem for two-relator groups

Is the conjugacy problem for two-relator groups known to be undecidable? The word problem for two-relator groups is a famous open problem (appearing e.g. as Question 9.29 in the Kourovka notebook), ...
user avatar
0 votes
1 answer
114 views

Examples of infinitely presented non-LEF groups

A group is LEF (locally embeddable in the class of finite groups) if it embeds into an ultraproduct of finite groups. Residually finite groups are LEF and finitely presented LEF groups are residually ...
user avatar
  • 435
5 votes
0 answers
134 views

Tools for computing from group presentations

What are some tools -- either theoretical/by hand or algorithmic/by computer -- that are useful for doing computations in finitely presented groups? In my particular case, I'm working with a finitely ...
user avatar
2 votes
2 answers
256 views

Combinatorial problem in $G(32, \, 6)$

The following problem arose when studying the same type of questions in Algebraic Geometry that led me to my previous question MO379272. Let us consider the group $G$ of order $32$ whose label in GAP4 ...
user avatar
4 votes
1 answer
115 views

Can one reduce to 'reversing' the right multiplier finite-state automata of an automatic group to obtain a biautomatic structure?

Let $\left( G, A, W, \left\{ R_{a} \right\}_{a \in A \cup \{ 1 \}} \right)$ be a group equipped with an automatic structure, where $G$ is the group, $A$ is a finite set of generators of $G$, $W$ is ...
user avatar
2 votes
1 answer
592 views

Combinatorial problem in $\mathsf{S}_4$

I am working on a problem in Combinatorial Group Theory related to a construction in Algebraic Geometry, and I would like to have a conceptual proof of the fact described below. I am looking for ...
user avatar
2 votes
1 answer
197 views

Proving an inequality regarding number of transitive subgroups of the symmetric group

I defined the sequence $t$ where where $t(n)$ is the number of transitive subgroups of $S_n$ where we regard conjugate subgroups as distinct, i.e. the labeled version of A002106 at the OEIS. Then I ...
user avatar
17 votes
1 answer
480 views

Is Thompson's group $T$ co-Hopfian?

A group $G$ is co-Hopfian if every injective homomorphism $G\to G$ is bijective, i.e., if $G$ contains no proper subgroups isomorphic to $G$. My question is whether Thompson's group $T$ is co-Hopfian. ...
user avatar
4 votes
2 answers
182 views

CCT groups of order $\leq 32$

A finite, non-abelian group $G$ is said to be a center commutative-transitive group $($or a CCT-group, for short$)$ if commutativity is a transitive relation on the set on non-central elements. In ...
user avatar
7 votes
0 answers
391 views

Are these two kernels isomorphic groups?

We have a finitely presented, infinite group $\mathsf{B}$, coming from a geometric topology problem (it is the quotient of a braid group for a genus 2 surface). It is generated by elements \begin{...
user avatar
3 votes
1 answer
194 views

Geometric content of area of a word in geometric group theory?

Where does the idea of 'area' come from in Geometric Group Theory? The wikipedia article states that this definition was 'inspired' from Riemannian geometry: Gromov's proof was in large part informed ...
user avatar
0 votes
0 answers
70 views

Intersection of subgroup of a free group with the lower central series

If I have a subgroup $S$ of a free group $\mathcal{F}_m$, what can I say about the behaviour of the descending sequence of subgroups $\left< S, \Gamma_c(\mathcal{F}_m) \right>$ (where $\Gamma_c(\...
user avatar
9 votes
2 answers
336 views

Reference request: Recent progress on the conjugacy problem for torsion-free one-relator groups?

I am aware that the Spelling Theorem of B. B. Newman implies that one-relator groups with torsion are hyperbolic, and thus have a solvable conjugacy problem. My understanding is that for one-relator ...
user avatar
3 votes
1 answer
116 views

Bounding the size of the conjugating elements given the Dehn function

I am learning a little bit about Dehn functions of group presentations and I came across a question that is probably pretty basic but that I was giving me trouble. I'll set some notation but ...
user avatar
  • 5,201
2 votes
0 answers
111 views

Time complexity of randomized algorithm: right-multiplying by random elements $z_i$ from a group $H$ to achieve $H$-invariance

Note: This question was inspired by a related question about the Quantum Merlin Arthur (QMA) complexity class on Quantum Computing Stack Exchange. I was deliberating whether to ask this on CS Theory ...
user avatar
5 votes
0 answers
155 views

Description of quasimorphisms of the free group

Let $F$ be a free group of finite rank with a fixed basis and corresponding word metric. Let $Q = Q^0_h(F, \mathbb{R})$ be the space of real homogenous quasimorphisms that vanish on the basis of $F$. ...
user avatar
  • 435
12 votes
1 answer
704 views

Minimum number of relations that must be added to make a group abelian

Let $G$ be a finitely generated group and let $c(G)$ denote the minimal number of relations that we must add to a presentation fro $G$ in order to make $G$ abelian. I would like to find examples of ...
user avatar
  • 5,201
4 votes
1 answer
154 views

Complementing the red and blue boolean cube?

Given a boolean $0/1$ cube in $n$ dimensions with $2^{n-1}$ red and $2^{n-1}$ blue points can we complement the cube (blue becomes red and vice versa) in $\operatorname{poly}(n)$ transformations? ...
user avatar
  • 12.8k
1 vote
0 answers
20 views

Do small subsets of $S_n$ subgroups cover almost all permutation configurations of $S_n$?

Given integer $m\in[1,n]$ fix a set $\mathcal T$ of permutations in $S_n$. Then there are subgroups $G_1,\dots,G_m$ of $S_n$ so that $\mathcal T$ is covered by cosets of $G_1,\dots,G_m$. For ...
user avatar
  • 12.8k
1 vote
0 answers
91 views

Are almost all permutation configurations from $S_n$ covered by small subsets subgroups of $S_n$?

Given integer $m\in[1,n]$ fix a set $\mathcal T$ of permutations in $S_n$. Then there are subgroups $G_1,\dots,G_m$ of $S_n$ so that $\mathcal T$ is covered by cosets of $G_1,\dots,G_m$. Do we have ...
user avatar
  • 12.8k
15 votes
2 answers
805 views

Is an HNN extension of a virtually torsion-free group virtually torsion-free?

This is a cross post from Math.StackExchange after 2 weeks without an answer and a bounty being placed on the question. Let $G=\langle X\ |\ R\rangle$ be a (finitely presented) virtually torsion-free ...
user avatar
8 votes
1 answer
204 views

Number of words of length N that reduce to the identity in a specific Coxeter group

Suppose we have a Coxeter group whose diagram is given by a simplex. In other words, $G=\langle g_1,\ldots ,g_k\mid(g_i)^2=e,\,(g_ig_j)^3=e \rangle$. How many words of length $N$ simplify to the ...
user avatar
  • 433
6 votes
0 answers
423 views

Minimum Simple Burger-Mozes Type Group

Burger and Mozes constructed (Burger and Mozes - Lattices in products of trees) infinite, finitely presented, torsion-free simple groups which split as amalgams of two finitely generated free groups ...
user avatar
8 votes
0 answers
254 views

Breuer-Guralnick-Kantor conjecture and infinite 3/2-generated groups

A group $G$ is called $\frac{3}{2}$-generated if every non-trivial element is contained in a generating pair, i.e. $$\forall g \in G \setminus \{e \}, \ \exists g' \in G \text{ such that } \langle g,g'...
user avatar
6 votes
0 answers
463 views

Darkness in the lamplighter group

Consider paths through the lamplighter group $\mathbb{Z}_n\wr\mathbb{Z}$ with steps consisting of moving left, moving right, and toggling the lamp at the current position. How many paths of length $m$ ...
user avatar
  • 1,577
4 votes
3 answers
210 views

Conjugacy in right-angled Artin groups

I am looking for a reference containing the following result: Let $a$ and $b$ be two elements of a right-angled Artin group $A$. Assume that $a$ and $b$ have minimal length (with respect to the ...
user avatar
  • 6,053
13 votes
1 answer
920 views

Is there a name of semidirect product of a group with its automorphism group?

Consider the construction $G \rtimes \text{Aut}(G)$. Here $ G$ is a group, $\text{Aut}(G)$ is the automorphism group and the semidirect product is over the most obvious action. 1) Is there any name ...
user avatar
3 votes
1 answer
295 views

When is the semidirect product of $(Z/pZ)^n$ and $(Z/qZ)^2$ generated by two elements?

I asked a very similar question here and got a wonderful answer. But now I need to change the question slightly (this is the last question like this, I promise). I would like to characterize when $(\...
user avatar
  • 2,590
9 votes
1 answer
657 views

When is the semidirect product of an elementary abelian group and a cyclic group generated by two elements?

I am trying to characterize when a semi-direct product of the form $(Z/pZ)^n \rtimes (Z/qZ)$ is isomorphic to a group generated by two elements. Here $p$ and $q$ are distinct odd primes. I would be ...
user avatar
  • 2,590
11 votes
0 answers
334 views

Amalgamated product of automatic groups

In Gersten's "Problems on Automatic Groups", Problem 14, he asks the following question: Let $G=A\ast_{C}B$ where $A$ and $B$ are automatic and $C$ is infinite cyclic. Is $G$ automatic? Is this ...
user avatar
  • 515
2 votes
1 answer
318 views

Quotient groups of the lower central series of a surface group

In the answer to MO question 132247, it is possible to find a nice computation of the quotient groups of the lower central series of a finitely generated free group. Q. What are the quotient ...
user avatar
21 votes
1 answer
686 views

Can a hyperbolic, one ended, one relator group, have a shorter trivial word?

Let $G= \langle S \mid r \rangle$ be a one-relator presentation for a one-ended hyperbolic group, with $r$ cyclically reduced. Question: Can there be a nontrivial word $w(S)$ which is trivial in the ...
user avatar
6 votes
1 answer
415 views

Minimum number of operations necessary to arrive at any configuration

Let $k \geq 2$ and $N_1, N_2, ..., N_k$ be positive integers. Let $S=\{(a_1,a_2,...,a_k) \in \mathbb{Z}^k:1 \leq a_i \leq N_i\}$ and $A=\{1,2,...,\prod_{i=1}^{k} N_{i}\}$. Given a bijective map $f:...
user avatar
  • 2,767
10 votes
1 answer
148 views

Minimal length presentations of cyclic groups

By the length of a finite presentation I mean the sum of the lengths of the relators. I am interested in knowing what the minimal length of a presentation of $\mathbb{Z}/n\mathbb{Z}$. I'm even more ...
user avatar
  • 5,201
6 votes
1 answer
372 views

An algorithm determining whether two subgroups of a finitely generated free group are automorphic

In the book Lyndon, Schupp, Combinatorial Group Theory, P.30 in the edition from 2000 They mention an unpublished work by Waldhausen that is said to give an algorithm to determine whether two ...
user avatar
10 votes
0 answers
180 views

2-generator subgroups of an Artin group of small type

Suppose I have an Artin group $G$ of small-type, meaning that the generators either commute or braid. E.g a braid group. Take two generators $g, h$ and arbitrary conjugates of these generators $xgx^{-...
user avatar
12 votes
1 answer
353 views

"Bisecting" a free subgroup with respect to word length

My broad question is regarding the lengths of (reduced) words in a subgroup of a free group. As motivation, consider the free group $Gp(S)$ where $|S|=n$, that is, a free group of rank $n$. Let $S=\{...
user avatar
  • 877
3 votes
1 answer
114 views

Maximal power in a sequence of iterated commutators in the rank two free group

I have the following problem: in the free group $F_2=\langle a,b\rangle$, we define the sequence $\begin{cases} w_0=a, \\ w_1=b, \\ w_{n+2}=[w_{n+1},w_{n}] & \text{for }n\ge 0. \end{cases}$ So $...
user avatar