All Questions
Tagged with co.combinatorics computational-group-theory
7 questions with no upvoted or accepted answers
12
votes
0
answers
558
views
Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers
Definition / Question
Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where
$0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$...
- 19.6k
10
votes
0
answers
194
views
Permutation groups with diameter $O(n \log n)$
I suspect that many permutation puzzles can be solved in $O(n \log n)$ moves, which has led me to the following question/conjecture:
Suppose that
1. $P_i$ for $i<k=O(1)$ are permutations on an $n$ ...
- 7,545
8
votes
0
answers
435
views
A relation between intersection and product on Boolean interval of finite groups
Let $[H,G]$ be a Boolean interval of finite groups (i.e. the lattice of intermediate subgroups $H \subseteq K \subseteq G$, is Boolean). For any element $K \in [H,G]$, let $K^{\complement}$ be its ...
7
votes
0
answers
1k
views
Example of a group with unsolvable word problem
Today I noticed that the last relator in the 27-relator presentation
of a group with unsolvable word problem given in
Donald J. Collins: A simple presentation of a group with unsolvable word problem.
...
- 19.6k
4
votes
0
answers
115
views
Complexity to find "short" (e.g. polynomial in diameter) decomposition of the permutation into the product of generators?
Question 1: Consider the symmetric group $S_n$ and some set of permutations $p_i$. Given permutation $g$ - what is known about the algorithmic complexity to decompose $g$ into product of $p_i$ ...
- 24.9k
2
votes
0
answers
154
views
Nonvanishing of the dual Euler totient on boolean intervals of finite groups
The rank $n$ boolean lattice $B_n$, is the subset lattice of $\{1,2, \dotsm n \}$.
Let $[H,G]$ be a boolean interval of finite groups. Its Euler totient is defined by $$\varphi(H,G):=\sum_{K \in ...
1
vote
0
answers
81
views
An optimal lower bound related to generators in a boolean interval of finite groups
Let $[H,G]$ be a rank $n$ boolean interval of finite groups (i.e. $[H,G] \simeq B_n$ as lattice).
Let the set $E = \{ g \in G \ | \ \langle H,g \rangle = G \}$
Remark: If $g \in E$ then $Hg \...