Questions tagged [combinatorial-group-theory]
The combinatorial-group-theory tag has no usage guidance.
130
questions
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 ...
- 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\...
- 415
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 ...
- 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 ...
- 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?"
...
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 ...
- 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{...
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 ...
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 ...
- 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 ...
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 ...
- 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. $\...
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), ...
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 ...
- 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 ...
- 629
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 ...
- 61.8k
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 ...
- 41
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 ...
- 61.8k
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 ...
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.
...
- 2,277
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 ...
- 61.8k
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{...
- 61.8k
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 ...
- 1,131
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(\...
- 31
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 ...
- 415
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 ...
- 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 ...
- 229
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$. ...
- 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 ...
- 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?
...
- 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 ...
- 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 ...
- 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 ...
- 785
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 ...
- 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 ...
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'...
- 22.9k
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$ ...
- 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 ...
- 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 ...
- 601
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 $(\...
- 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 ...
- 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 ...
- 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 ...
- 61.8k
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 ...
user35370
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:...
- 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 ...
- 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 ...
- 183
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^{-...
- 605
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=\{...
- 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 $...
- 1,196