# Questions tagged [combinatorial-group-theory]

The tag has no usage guidance.

121 questions
Filter by
Sorted by
Tagged with
270 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 ...
225 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 ...
128 views

316 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 ...
105 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 ...
99 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 ...
143 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$. ...
624 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 ...
152 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? ...
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 ...
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 ...
703 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 ...
187 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 ...
328 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 ...
239 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'...
453 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$ ...
186 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 ...
746 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 ...
252 views

145 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 ...
358 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 ...