All Questions
Tagged with co.combinatorics finite-groups
190 questions
2
votes
0
answers
163
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: ...
- 24.9k
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 ...
- 24.9k
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
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
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 ...
- 66.3k
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
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....
- 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.1k
4
votes
0
answers
227
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/...
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
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 \; ...
- 66.3k
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
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 ...
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
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
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 $...
- 1,294
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
7
votes
1
answer
337
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.
(...
- 3,499
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,...
- 41.8k
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
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
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?
- 327
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$, ...
- 3,054
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
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 ...
- 231
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 ...
- 513
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 ...
- 66.3k
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. ...
- 4,600
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
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
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
-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$. ...
- 2,089
7
votes
1
answer
399
views
Maximum size of $k$-Sidon set over $\mathbb{F}_2^n.$
Fix $k \in \mathbb{N}$, $k \ge 2.$
Does there exist a subset $A \subset \mathbb{F}_2^n$ such that $|A| \ge c 2^{n/k}$ with some absolutely positive constant $c,$ and satisfying
$$ a_1 + a_2 + \...
user148117
4
votes
2
answers
485
views
Transposition Cayley graphs are planar
Consider the Cayley graph $G$ with vertex set the elements of the symmetric group $S_n$ and generating set the set of minimal transposition generators of the group $S_n$, that is the set $S=\{(12),(13)...
- 2,089
1
vote
1
answer
218
views
Average size of iterated sumset modulo $p-1$,
Given a prime $p$, what is the average size of the iterated sumset, $|kA|$, modulo $p-1$, with $p$ a prime, and $k$ given, with $A$ chosen at random?
You can pick any type of prime you like for $p$, ...
- 221
8
votes
2
answers
4k
views
Order of product of group elements
Let $G$ be a finite non-commutative group of order $N$, and let $x, y \in G$. Let $a$ and $b$ be the orders of $x$ and $y$, respectively. Can we say anything non-trivial about the order of $xy$ in ...
- 1,703
7
votes
1
answer
145
views
How to prove the relationship between Stern's diatomic series and Lucas sequence $U_n(x,1)$ over the field GF(2)?
I found the bit count of Lucas sequence $U_n(x,1)$ over the field GF(2) is Stern's diatomic series, I want to know the reason?
https://oeis.org/A002487 : Stern's diatomic series
https://oeis.org/...
- 317
28
votes
1
answer
2k
views
Multiplying all the elements in a group
Let $G = \{ g_i | i = 1, ...,n \}$ be a finite group and denote by $G!$ the multiset consisting of all the products of all different elements of $G$ in any order, that is
$$ G! = [ \prod_i g_{\sigma(i)...
- 943
1
vote
1
answer
267
views
Adding $n$-tuples over groups
Consider a finite abelian group $\mathcal{G}$. Let $S_0$ be a $n$-tuple of elements of $\mathcal{G}$, and let $S_i$ be the cyclically shifted version of $S_0$ by $i$ indices to the right. So for ...
- 431
-1
votes
1
answer
325
views
Isomorphism classes of split extensions [closed]
Let $p$ be a prime number and $n$ an integer such that $p\geq n$. Let $P(n)$ denotes the number of partitions of $n$. Can we conclude from Theorem 1.1 and Theorem 1.3 in the reference FINITE_p-...
- 181
1
vote
0
answers
80
views
Packing almost-subgroups into a group
We consider a group finite $G$. We say a set $A\subset G$ injects a set $B$ if $|A+B| = |A||B|$, and let $I(B) = \max \{|A| :A\text{ injects } B\}$.
For a subgroup $H$, it is well-known that $I(H) = |...
- 3,499
1
vote
0
answers
247
views
Sidon sets in finite groups
Suppose $G$ is a group, $S \subset G$. Let’s call $S$ a Sidon subset iff $\forall$ quadruples $(a, b, c, d)$ of distinct elements of $S$ we have $ab \neq cd$ (named after Simon Sidon who studied such ...
- 2,618
16
votes
1
answer
395
views
Geometric interpretation of the exceptional isomorphism $PSp(4,3)=PSU(4,2^2)$
It is well-known that there is an isomorphism between $PSp(4,3)$ (the symplectic group of dimension $4$ over $\mathbb F_3$) and $PSU(4,2^2)$ (the unitary group defined by $4\times4$ unitary matrices ...
- 9,501