MathOverflow

Questions tagged [combinatorial-group-theory]

Ask Question

The tag has no usage guidance.

108 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
0
votes
0answers
36 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(\...
7
votes
2answers
252 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 ...
3
votes
1answer
93 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 ...
2
votes
0answers
84 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 ...
5
votes
0answers
132 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$. ...
11
votes
1answer
557 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 ...
4
votes
1answer
144 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? ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
15
votes
2answers
600 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 ...
8
votes
1answer
167 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 ...
3
votes
0answers
240 views

Simple One-relator Groups [closed]

One-relator groups, that is, groups which admit a finite presentation $\langle A \: | \: w=1 \rangle$ for some $w \in A^\ast$, are well studied objects in combinatorial group theory. Many abstract ...
6
votes
0answers
216 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
0answers
213 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'...
5
votes
0answers
446 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$ ...
5
votes
3answers
167 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 ...
11
votes
1answer
559 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 ...
3
votes
1answer
215 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 $(\...
9
votes
1answer
439 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 ...
10
votes
0answers
306 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 ...
2
votes
1answer
243 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 ...
20
votes
1answer
558 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 ...
6
votes
1answer
396 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:...
10
votes
1answer
143 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 ...
6
votes
1answer
345 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 ...
10
votes
0answers
150 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^{-...
12
votes
1answer
276 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=\{...
3
votes
1answer
103 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 $...
2
votes
0answers
126 views

Concentration of Reduced words

This might be a rather broad question, and I'll be satisfied with some intuition and pointers to relevant literature. However, I'll certainly fill in more context and details based on any feedback. ...
2
votes
2answers
367 views

Subgroup of a free group that is characteristic but not totally characteristic

Looking for a counter example (if it exists) and a reference for further reading. Can there be a subgroup of finite index in a finitely generated free group that is characteristic but not totally ...
2
votes
0answers
89 views

Change of generators and shortest product in groups

Let $G$ be a finitely generated group. For a set of generators $B$ of $G$, $\ell_B(x)$ is the length of the smallest sequence of elements(and inverse of the elements) in $B$, such that the product ...
3
votes
2answers
227 views

Free subgroup of a quotient

Let $F$ be a free group on $x,y,z$. Fix $n>1$ (I am ready to assume that $n$ is large enough). Let $\mathcal{W}$ be the set of cyclically reduced words $w$ in $F$ where the letter $z$ appears at ...
4
votes
0answers
107 views

Order problem in nilpotent groups

Let $G$ be a f.g. nilpotent group. I wanted to know if the order problem (given $g \in G$, deciding if there exists $n$ s.t. $g^n=e$) is decidable in $G$? In such a group, the word problem is ...
8
votes
1answer
236 views

Need a good name for an algorithmic problem in groups that generalizes the conjugacy problem

I am looking for a good name for the following problem: Given elements $g_1,\dotsc,g_n$ in a (finitely generated) group $G$, determine if the product of their conjugacy classes $g_1^G\dotsb g_n^G$ ...
2
votes
0answers
189 views

When can we establish an isomorphism between two not-finitely presented groups?

Assume that finitely generated groups $G$ and $H$, are not finitely presented. Fix a generating set $\mathfrak g:=\{g_1,\dotsc,g_n\}$ of $G$. Let $\mathfrak R:=\{R_1,R_2,\dots\}$ be the set of all ...
2
votes
1answer
152 views

Could the number of defining relators of a finitely presented group increase

Do there exist finitely generated groups $G$ and $H$ with following properies: $G=\langle g_1,\dotsc,g_n\rangle$ is not finitely presented, Let $R:=\{r_1,r_2,\dots\}$ be the set of its defining ...
4
votes
2answers
406 views

A question about generating set of groups and epimorphism

Do there exist non-isomorphic finitely generated groups, $G$ and $H$, along with epimorphisms $\phi:G\rightarrow H$ and $\psi:H\rightarrow G$, such that every generating set of these groups is an ...
8
votes
1answer
224 views

Does every generating set of the first homology group of a Cayley graph give rise to a presentation of its group?

Let $G$ be a group, and fix a symmetric generating set $S$. Let $X$ be the corresponding Cayley graph. Let $R$ be a set of words in $S$, each corresponding to the identity of $G$, such that the set ...
21
votes
1answer
984 views

Covering of a surface of a cube $n\times n \times n$ by pieces of paper $1\times 6$

When I was too young one of my problems was in the list of problems of All-Russian Olympiad. The problem is the following: Problem. We have a surface of a cube $n\times n \times n$ such that each ...
4
votes
1answer
122 views

Computations with conetypes of hyperbolic groups

I'd like to know if there exists (and, in this case, where I can find it) some computer program/programming language/any kind of software that can find explicitly the conetypes of a hyperbolic group ...
4
votes
1answer
295 views

Is there a one relator group with property (T)?

Is there an $n > 2$, and some $x \in F_n$ (the free group on $n$ generators) such that the quotient of $F_n$ by the normal subgroup generated by $x$ has Kazhdan's property $\mathrm{(T)}$ ?
0
votes
1answer
105 views

Rank of a generall linear group over a finite field [closed]

What is the rank (minimal number of group generators) of the group $GL(n,F)$, when $F$ is a finite field of odd order? I found that $SL(n,F)$ is $2$, but I can't find this information.
1
vote
4answers
300 views

Are the orders of the generators of a group and the product of pairs of thereof enough for this group to be isomorphic to a Coxeter group?

Let's say we have $n$ generators $x_1, x_2, \cdots, x_n$ along with the following facts concerning their orders: \begin{eqnarray*} ord(x_i) &=& 2 \text{ for } i = 1, 2, \cdots, n \\ ord(x_i ...
3
votes
3answers
123 views

Are there references for the properties of words formed in finite groups using L-systems? (In particular, the algae L-system.)

Let $G$ be a (finite) group, and $a, b \in G$ be any two elements. Consider the sequence defined by \begin{eqnarray*} s_0 &=& a, \\ s_1 &=& b, \text{and} \\ s_{n+2} &=& s_{n+1} ...
13
votes
1answer
579 views

Avoiding countable subgroups of a group homeomorphic to the Cantor space

Update: Further work with Adam (who answers below) and Piotr led to a rather satisfactory result about the problem that motivated the problem below, see our recent paper The Haar Measure Problem. In ...
8
votes
2answers
671 views

Avoiding countable subgroups of general uncountable groups

The following problem is a general form of another problem (motivation is available there). Initially, the problems were posted together, but the first one is solved below, a solution that does not ...
5
votes
1answer
357 views

K-fellow traveler property and automatic structure

I have been reading several articles about automatic groups and metric spaces of negative curvature. However it is not clear for me the relationship between automatic groups, hyperbolcity and the k-...
2
votes
3answers
538 views

Rank of a special linear group over a finite field

What is the rank (minimal number of group generators) of $SL(n,\mathbb{F})$ in the situation when $SL(n,\mathbb{F})$ is not perfect (i.e. when $SL(n,\mathbb{F})$ is different from $SL(2,\mathbb{F}_2)$ ...
1
vote
0answers
119 views

Intuitive meaning of benign subgroup

Disclaimer! This is a copy of a question I posted on M.SE! I still think the question belongs there but I'm not getting any answers so I'm dublicating with slight changes: I've been studying a proof ...
13
votes
2answers
568 views

Why is “The Higman Rope Trick” thus named?

I'm studiyng Higman's Embedding Theorem, and a fundamental part of the proof is the following lemma: If R is a benign normal subgroup of finitely generated group F, then F/R can be embedded in a ...

1
2 3