All Questions
Tagged with finite-groups co.combinatorics
190 questions
2
votes
0
answers
164
views
Nonabelian groups where every element has small order
Let $G$ be a finite nonabelian group with the property that if $g \in G$, then
$$\DeclareMathOperator{\ord}{ord} \ord(g) \leqslant 10 \log_2 |G|, $$
where $\ord(g)$ is the order of the element $g$, ...
- 1,354
1
vote
1
answer
80
views
What are the efficient algorithms to compute Hamiltonian paths on Cayley graphs of finite groups ? Can GAP do it?
The famous Lovasz conjecture predicts existence of the Hamiltonian path on Cayley graphs. In general finding such a path is NP-complete problem, but there are many heuristic algorithms.
Question 1: ...
- 12.7k
9
votes
0
answers
292
views
Tilings in finite (not necessarily Abelian) groups
Let $G$ be a finite (not necessarily abelian) group. We call $A \subseteq G$ a right-tiling (for simplicity, a tiling) of $G$ if there exists a $B \subseteq G$ so that
$$ G = \bigsqcup_{b\in B} bA.$$
...
- 1,354
8
votes
1
answer
1k
views
GAP cannot solve Rubik's cube 4x4x4 and higher ? (Practical limits of Schreier–Sims algorithm)
According to our practical experiments and literature search - computer algebra system GAP cannot "solve" Rubik's cube 4x4x4 and higher. That means cannot decompose given random element of ...
- 5,654
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
21
votes
2
answers
1k
views
Generating random finite groups
I would like a method to efficiently generate a random finite group of a given order $n$.
If there are $g(n)$ non-isomorphic groups of order $n$,
ideally each group would occur with probability $1/g(n)...
- 4,713
0
votes
1
answer
155
views
Combinatorial problem in $G(54, \, 5)$ - Reprise
This post is a follow-up to my previous post MO479127. I am trying to concentrate on a subset of relations, hoping to find some structure on the set of solutions that explains why the whole set of ...
- 23.7k
3
votes
0
answers
359
views
Combinatorial problem in $G(54,\, 5)$
I have asked (probably) easier versions of this question in the past, see MO379272 and MO380292. At the moment, it is not clear to me how the beautiful answers to those questions can be helpful here.
...
- 66.3k
16
votes
1
answer
804
views
Existence of a faithful irreducible representation using Möbius function
Let $G$ be a finite group, $L(G)$ its subgroup lattice and $\mu$ the Möbius function.
Consider the Euler totient of $G$ defined as follows:
$$ \varphi(G) = \sum_{H \le G}\mu(H,G) |H| $$
Let $X=\{M_1, \...
- 4,219
3
votes
2
answers
1k
views
How many semidirect products are there?
This question was initially proposed to me by two friends. Given an integer $n$, how many isomorphism classes are there for semidirect products $\mathbb{Z}/n\mathbb{Z}\rtimes\mathbb{Z}/2\mathbb{Z}$?
...
- 63.9k
3
votes
0
answers
125
views
Short path problem on Cayley graphs as language translation task (from "Permutlandski" to "Cayleylandski"(s) :). Reference/suggestion request
Context: Algorithms to find short paths on Cayley graphs of (finite) groups are of some interest - see below.
There can be several approaches to that task. One of ideas coming to my mind - in some ...
- 24.9k
3
votes
0
answers
109
views
What Cayley graphs arise as nodes+edges from "nice" polytopes and when are these polytopes convex?
The Permutohedron is a remarkable convex polytope in $R^n$, such that its nodes are indexed by permutations and edges correspond to the Cayley graph of $S_n$ with respect to the standard generators, i....
- 3,065
4
votes
1
answer
251
views
Diameter of the "Masterball-puzzle" permutation groups by a kind of Cartier-Foata enumeration?
There is an wonderful blog post by Jordan S. Ellenberg SHOULD YOU BE SURPRISED BY THE DIAMETER OF THE NXNXN RUBIK’S GROUP?. Which explains how one can come to $N^2log(N)$ estimate of the diameter of ...
- 24.9k
2
votes
0
answers
98
views
Estimating the cardinality of the set of conjugacy classes of subgroups in a finite group of given order
1. Let $G$ be a finite group of order $n$. I need an estimate for the number $c$ of conjugacy classes of subgroups $D\subseteq G$.
Note that any subgroup of $G$ contains $1_G$, and so the set of all ...
- 14.2k
4
votes
0
answers
228
views
Polynomials of growth for finite Heisenberg groups
Take a standard finite Heisenberg group with two standard generators and let's consider its growth polynomial - the polynomial which coefficients are equal to the sphere sizes.
For example for $H_3(Z/...
2
votes
3
answers
888
views
The number of submodules of $\mathbb{Z}_q^n$
Observe $\mathbb{Z}_q^n = \mathbb{Z}_q \times \cdots \times\mathbb{Z}_q$ as a module over $\mathbb{Z}_q\equiv\mathbb{Z}/q\mathbb{Z}$, for general $q$.
I am interested in the following questions:
How ...
- 503
5
votes
1
answer
365
views
Number of $k$-tuples of elements generating a cyclic group
Let $k$, $m$ be natural numbers, and $C_m:=\mathbb{Z}/ m \mathbb{Z}$ be the cyclic group of order $m$.
Let $N_{k, \, m}$ be the cardinality of the following set: $$\{(a_1, \ldots, a_k) \in (C_m)^k \; ...
- 12.9k
20
votes
1
answer
993
views
Proof of CFSG assuming every simple group is two-generated
It is well-known that one of the corollaries of the classification of finite simple groups (CFSG) is that every finite simple group can be generated by two elements. In a comment on an answer to an ...
- 44.4k
2
votes
0
answers
71
views
Distance distribution for Cayley graphs of the fintie Heisenberg groups H3(Z/nZ) approaches Gaussian for large "n"?
I wonder several questions about Cayley graphs of finite Heisenberg groups H3(Z/nZ).
Question 1: do we know the diameter dependence on "n", at least for the standard choice of generators ? ...
- 24.9k
1
vote
0
answers
175
views
Random walk on N-Rubik cube group is going like sqrt(number of moves) or linear (number of moves) or? "commutative" vs. "free"(like) group pattern?
Consider higher (NxNxN) Rubik's cube group, with specific set of generators described below.
What is important - that there are huge COMMUTING subsets of generators.
Question: Consider a random walk ...
- 24.9k
31
votes
1
answer
2k
views
Navigating $\mathbb{Z}/p\mathbb{Z}$
$\newcommand{\Z}{\mathbb{Z}}$Let's consider a silly-looking question first. Consider $\Z/p\Z$. Say I am allowed the two operations $x\mapsto x+1$ and $x\mapsto 2x$. Then, starting from $0$, I can ...
- 63.9k
32
votes
3
answers
3k
views
Order of products of elements in symmetric groups
Let $n \in \mathbb{N}$. Is it true that for any $a, b, c \in \mathbb{N}$ satisfying
$1 < a, b, c \leq n-2$ the symmetric group ${\rm S}_n$ has elements of order $a$ and $b$
whose product has order $...
- 2,217
5
votes
0
answers
200
views
Subgroups of the symmetric group and binary relations
Motivation
The following came up in my work recently. (NB this is the motivation, not the question I'm asking. You can skip to the actual question below, which is self-contained, but not self-...
- 756
8
votes
1
answer
489
views
Elements living in the conjugacy class and in the centralizer of an $m$-cycle in $A_m$
Let $m>1$ be an odd natural number, $x$ a $m$-cycle in $A_m$, the alternating group in $m$ letters, $C$ the conjugacy class of $x$ in $A_m$.
Question: How can I describe the elements in the set $\{ ...
- 6,367
12
votes
1
answer
450
views
abelian quotients of permutation groups
Let $G$ be a subgroup of the permutation group $S_n$, and let $H$ be a normal subgroup of $G$ such that the quotient group $G/H$ is abelian. What is the best known upper estimate for the cardinality $...
- 63.9k
4
votes
0
answers
108
views
Doubly stochastic matrices that remain doubly stochastic after conjugating by the character table of a finite abelian group
I am curious if anything is known about the following.
Let $\Gamma$ be a finite abelian group, and let $\chi$ be its character table, normalized so that it is a unitary matrix. E.g., if $\Gamma$ is $\...
- 2,339
1
vote
1
answer
156
views
Sub-circle-free Christmas-gift-giving
Suppose there is a group of $n$ people giving gifts to one another. Everybody brings a gift but we want the gifts to be "well-distributed" in the group. By this I mean the following:
In how many ...
-1
votes
1
answer
215
views
Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques
Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...
CommunityBot
- 1
7
votes
1
answer
338
views
Lovasz's conjecture for dihedral Cayley graphs
Background:
A tantalizing conjecture of Lovasz is the following:
Let $G$ be a (finite) connected vertex-transitive graph. Then $G$ contains a Hamiltonian cycle or is one of $5$ counter-examples.
(...
- 673
11
votes
1
answer
550
views
Probability of words summing to $1$ in $S_n$ or $\mathrm{PGL}_2(n)$
$\DeclareMathOperator\PGL{PGL}\DeclareMathOperator\Conj{Conj}$Let $G$ be the symmetric group $S_n$ or the projective general linear group $\PGL_2(n)$.
Let $X$ be a cyclically reduced word in the ...
- 412
5
votes
1
answer
358
views
The number of polynomials on a finite group, II
This question is follow up of this MO-post.
First let us recall the necessary definitions.
A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\mathbb N$ and elements $a_0,...
- 121
2
votes
0
answers
85
views
G graph connections for finite groups G
In my research, I have seen G graph connections usually when G is a Lie group and the graph is the fatgraph of a (punctured) surface. This is usually in a physics context. However, I am curious to ...
- 495
54
votes
4
answers
5k
views
How many square roots can a non-identity element in a group have?
Let $G$ be a finite group. Let $r_2\colon G \to \mathbb{N}$ be the square-root counting function, assigning to each $g\in G$ the number of $x\in G$ with $x^2=g$. Perhaps surprisingly, $r_2$ does not ...
- 805
2
votes
0
answers
76
views
Anti-flag transitive projective planes
Let $\Gamma$ be an axiomatic projective plane, and suppose its automorphism group acts transitively on the anti-flags (the point-line pairs $(u,V)$ such that $u$ is not incident with $V$).
In the ...
- 4,547
3
votes
0
answers
100
views
Commuting probabilities for a conjugacy class of a finite simple group $G$ which generates $G$
Let $G$ be a nonabelian finite simple group. Let $C\subset G$ be a conjugacy class which generates $G$. Let $E\subset C\times C$ be the subset consisting of pairs $(c,d)$ with $cd =dc$. Define the ...
- 7,527
4
votes
1
answer
264
views
A question on a possible cyclic sieving phenomenon?
(This is an old MSE question from me, which did not get any answer, and when looking back seems interesting to post it here:)
Let $G$ be a finite group. Consider the set $X_G:=\cup_{H\le G} G/H$, ...
- 5,822
0
votes
1
answer
130
views
Number of reduced decompositions of the dihedral group $D_6$ [closed]
The Weyl group of $\frak{g}_2$ is the dihedral $D_6$. Let us denote its longest element by $w_0$. How many reduced decompositions does $w_0$ have?
- 24.2k
9
votes
2
answers
762
views
Solutions of $x^d=1$ in the symmetric group
L Moser and M Wyman, On solutions of $x^d = 1$ in symmetric groups, Canad. J. Math., 7 (1955), pages 159-168, explored asymptotic behavior of the cardinality of such permutations:
$$f_d(n):=\#\{\pi\in\...
- 105k
8
votes
2
answers
880
views
Moebius function of finite abelian groups
I am wondering if there is any literature on general formula of the Moebius function of subgroup lattices of any finite abelian group $G$? What I know is
When $G$ is cyclic, the Moebius function is ...
- 50.8k
31
votes
2
answers
1k
views
Does the symmetric group $S_{10}$ factor as a knit product of symmetric subgroups $S_6$ and $S_7$?
By knit product (alias: Zappa-Szép product), I mean a product $AB$ of subgroups for which $A\cap B=1$. In particular, note that neither subgroup is required to be normal, thus making this a ...
- 1,068
1
vote
0
answers
72
views
Scalars by which symmetrizations of cyclic permutations act on Specht modules
Let $S_n$ be the symmetric group. Pick $a \in 2,\ldots,n$ and denote by $c_a \in \mathbb{C}[S_n]$ the symmetrization of the element $(12\ldots a)$ i.e. $c_a$ is the sum of cycles of type $a$.
Let $\...
- 163
2
votes
0
answers
203
views
Can the relation between count of commuting pairs and conjugacy classes for finite groups be generalized to semigroups?
It is well-known that number of pairs of commuting elements in finite group G is equal to number of conjugacy classes multiplied by cardinality of G.
More generally here (MO275769) Qiaochu Yuan ...
- 24.9k
0
votes
0
answers
121
views
Another question concerning finite metacyclic groups
Given a non-split finite metacyclic group $H$, does there always exist a finite split metacyclic group $G$ with a normal cyclic subgroup $N$ of prime power order such that $H \cong G/N$?
Based on my ...
28
votes
6
answers
1k
views
Are there always more conjugacy classes in the kernel of a morphism to $Z_2$ than not?
Let $G$ be a finite group and let $\phi:G\to Z_2$ be a homomorphism to the group with two elements. Is it always the case that there are more conjugacy classes in the kernel of $\phi$ than conjugacy ...
- 44.4k
2
votes
2
answers
309
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 ...
- 3,571
3
votes
0
answers
210
views
How many conjugacy classes of elementary abelian subgroups of order $p^2$ does $\operatorname{GL}_{4}(\Bbb Z / p\Bbb Z)$ have?
$\DeclareMathOperator\Hom{Hom}\DeclareMathOperator\GL{GL}\DeclareMathOperator\Aut{Aut}$Let $f\in \Hom((\Bbb Z/p\Bbb Z)^2,\GL_{4}(\Bbb Z / p\Bbb Z))$ be an injective homomorphism. What is the number of ...
- 463
4
votes
0
answers
92
views
Possible cardinalities of spherical tiling
Suppose that we have a tiling of $n$-dimensional (I want to get answer for $n = 4$, but general result would be nice!) sphere by isometric tiles strictly contained inside the right-angled simplex. ...
- 13.6k
1
vote
0
answers
144
views
Simultaneous similarity classes of pairs in $\mathrm{GL}_{n}(\Bbb Z / p\Bbb Z)$?
$\DeclareMathOperator{\GL}{\operatorname{GL}}$Let $G$ be an elementary abelian $p$-group of rank $2$. Let $\alpha, \beta :G\rightarrow \GL_{n}(\Bbb Z / p\Bbb Z)$ be two injective homomorphisms. The ...
- 181
8
votes
0
answers
247
views
Computing the number of elementary abelian p-subgroups of rank 2 in $GL_{n}(\mathbb{F}_{p})$
Let $p$ be a prime number, and let $\mathbb{F}_{p}$ be a finite
field of order $p$. Let $GL_{n}(\mathbb{F}_{p})$ denote the general linear
group and $U_{n}$ denote the unitriangular group of $n\times ...
- 463
3
votes
0
answers
92
views
Symmetric group in terms of block permutations
For $i+j+k=N$, consider the permutation $\Pi_{i,j,k}\in S_N$, which keeps the numbers $0,\ldots,i-1$ fixed, and exchanges the numbers $i,\ldots,i+j-1$ with the numbers $i+j,\ldots,i+j+k-1$.
$$\Pi_{i,j,...
- 3,001