All Questions
Tagged with co.combinatorics gr.group-theory
471 questions
1
vote
1
answer
186
views
Existence of Finite Amicable Groups
I'm interested in exploring the concept of "amicable groups" as follows:
Definition. Two finite groups $G$ and $H$ are called amicable groups if:
$G$ is the direct sum of proper subgroups ...
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
0
votes
0
answers
95
views
Class multiplication coefficients of symmetric groups
My question is that I was working with some counting problems, and finally the answer should be
$$
\nu_{\mu_1,\mu_2,\mu_3}=\#\{(\sigma_1,\sigma_2,\sigma_3): \sigma_1\sigma_2\sigma_3=1, \sigma_1\in C_{\...
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
1
vote
0
answers
151
views
Decide if a group is abelian
Let $G = \langle X: R\rangle$ be a finitely presented group. The following problem seems very natural to me, yet I cannot find any reference for it: Decide if $G$ is abelian or not.
With a reduction ...
- 11
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
4
votes
1
answer
189
views
Equation in the conjugacy class of a free group
I will pose the question in the form in which it originally appeared to me:
Let $a,b,c,d$ be different letters in a finite alphabet $\mathcal{Z}$. Let $Q$ and $R$ be finite words with letters from $\...
- 111
1
vote
1
answer
207
views
A candidate for one-way functions
For every $n \geq 3$ consider a bipartite random $3$-regular graph $G_n$ with two parts $X=\{x_1, \dotsc, x_n\}$ and $Y=\{y_1, \dotsc, y_n\}$. For any $i \leq n$ assign either 0 or 1 to each vertex $...
- 11
2
votes
1
answer
219
views
Existence of a special ordering of the elements of a finite group (II)
Let $G$ be a finite non-abelian group of order $n$. Given $g\in G$ we denote its order by $\mathrm{ord}(g)$.
Consider the group algebra $\mathbb{F}[G]$ for some field $\mathbb{F}$.
Given an ordering $...
- 14.6k
8
votes
2
answers
367
views
Existence of a special ordering of the elements of a finite group
Let $G$ be a finite non-abelian group of order $n$. Given $g\in G$ we denote its order by $\mathrm{ord}(g)$.
Consider the group algebra $\mathbb{F}[G]$ for some field $\mathbb{F}$.
Given an ordering $...
- 14.6k
7
votes
1
answer
259
views
A name for the Weyl group of $\frak{so_{2n}}$
For the $A$-series the Weyl group is the symmetric group $S_n$. For the $B$ and $C$ series the Weyl group is the hyperoctahedral group $\mathbb Z_2 \wr S_n$.
A) Does the $D$-series Weyl group $S_n \...
- 419
1
vote
0
answers
48
views
Length of the product of two elements of the subregular two-sided cell in the affine Weyl group of type A
The affine Weyl group of type $A_n$ can be described as follows. It is the group of all permutations $\sigma: \mathbb Z \to \mathbb Z$ such that $\sigma(i+n)=\sigma(i)+n$ and $\sum_{i=1}^n (\sigma(i)-...
- 2,964
3
votes
2
answers
468
views
How fast does the number of "fixed" points grow compared to the size of the ball in the following group?
I have copied this question from Math.StackExchange, in the hope that some experts here can provide some relevant insight.
Let $M = \oplus_{i\in \mathbb Z} V^{(i)}$ where each $ V^{(i)} \cong \mathbb ...
- 823
7
votes
1
answer
224
views
Generating set of permutation group such that generators do not "contain" other group elements
Let $(G, X)$ be a permutation group with domain $X$. Let $O=\{o_1,\dots,o_m\}$ be the set of orbits of $G$. I am interested in generating sets $S$ with the following property:
Let $g\in S$ be a ...
- 5,822
7
votes
1
answer
445
views
What is known/expected on the co-growth series of the braid group?
The co-growth series of finitely generated group with respect to generating set $S$ is generating function for the number of words of length $n$ which are equal to 1 in the group.
Its studies ...
- 24.9k
1
vote
0
answers
189
views
The existence of solutions to linear systems of equations over the integer ring $\mathbb{Z}$
There are already detailed results on the solutions of linear equations over fields, but I'd like to inquire about any good conclusions regarding the solutions of linear equations over the integer ...
- 173
2
votes
1
answer
423
views
Conjecture about semigroups
Let $G$ be a finite semigroup with order $n$ odd. Let $S_i \in G, i=1,\ldots,\binom{n}{(n+1)/2}$ be all the subsets of $G$ of size $(n+1)/2$.
Let $E(S_i)$ be the set obtained "expanding" $...
- 990
0
votes
0
answers
154
views
Up to what order have finite groups been classified? [duplicate]
All finite simple groups have been classified, and the classification of finite groups is thought to be wild. So, up to what order have finite groups been classified? Wikipedia tells us that it is ...
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
10
votes
1
answer
355
views
Is the group of translations of an affine plane always commutative?
$\DeclareMathOperator\Dil{Dil}\DeclareMathOperator\Trans{Trans}\DeclareMathOperator\Col{Col}$An affine plane is a set of points $X$ endowed with a family $\mathcal L$ of subsets of $X$, called lines, ...
- 41.8k
3
votes
0
answers
126
views
Finite approximability of graphs with finitely many automorphisms
In this question, all graphs are understood to be simple and undirected, and have countably many vertices and edges, but not necessarily finite.
Let $G = (V, E)$ be a graph. It is clear that any ...
- 2,830
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/...
3
votes
2
answers
220
views
Factorizations of an $n$-cycle in $S_n$ into a product $xy$ where $|x| = 2, |y| = 3$
Let $S_n$ be the symmetric group on $n$ letters. When (and how) can an $n$-cycle in $S_n$ be factored into a product $xy$, where $x,y$ have orders 2,3 respectively?
More precisely, I'd like to ...
- 7,527
1
vote
1
answer
206
views
Reflections on subspaces of $\text{codim} > 1$
Let $V$ be a real finite-dimensional vector space with inner product $\langle \cdot , \cdot \rangle$.
Let $x,y \in V$ be linearly independent. I was wondering how a reflection $s_{x,y}$ through the $\...
- 1,813
9
votes
1
answer
526
views
Shortest almost trivial element of free group [duplicate]
Let $F_n$ be the free group with $n$ generators $\gamma_1,\dots,\gamma_n$.
Consider the homomorphisms $h_i\colon F_n\to F_{n-1}$ defined by adding the relation $\gamma_i=1$ in $F_n$.
What is the ...
- 45k
1
vote
0
answers
167
views
Are these sequences, associated to integer partitions, always log-concave?
Let $\mathrm{CO}(m)$ be the set of all compositions of the
positive integer $m$. By a composition of $m$, I mean a finite
sequence $(m_1,\ldots,m_k)$ of positive integers with sum $\sum
m_i=m$.
...
- 481
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
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
1
vote
0
answers
55
views
Possible variant of Lovász: Graphs without 3 vertex-disjoint cycles
Is there a classification, or perhaps some exhaustive description, of graphs without 3 vertex-disjoint cycles,
and/or do you maybe know about some reference for such?
The case of graphs without 2 ...
- 11
1
vote
0
answers
130
views
Relationship between the symmetric group representation (Specht module) of a Young diagram and the Young diagram obtained by deleting one row
Suppose $\lambda$ is a Young diagram, and $\lambda'$ is obtained by deleting one particular row of $\lambda$. Is there any relationship between the symmetric group representation (Specht module) ...
- 25
3
votes
2
answers
205
views
Descending chain in $\mathbb{Z}$ with certain confining property, but not strongly
Call a sequence $A_1 \supseteq A_2 \supseteq \cdots$ of subsets of $\mathbb{Z}$ confining if for all $i$ we have $A_i \supseteq A_{i+1}+A_{i+1}$. (Let us insist that the $A_i$ are symmetric and ...
- 3,730
4
votes
1
answer
211
views
Nonempty intersection of cosets of finite-index subgroups
$\DeclareMathOperator\lcm{lcm}$This question is crossposted from MSE.
Let $H_1,\dots,H_{n+2}$ be cosets of finite-index subgroups of $\mathbb{Z}^n$ and suppose for all $i=1,\dots,n+2$, $\bigcap_{j\neq ...
- 10.6k
1
vote
0
answers
71
views
Bias of $a^k / q$ modulo $q$?
Let $q$ be a prime. Let $0< a < q$ be an integer so that it is primitive modulo $q$. Let $k$ be a random integer up to $q-1$. Consider
$$a^k = b_k + q * c_k$$
as $k$ varies modulo $q^2$. So $b_k$...
- 591
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
1
vote
1
answer
594
views
Some necessary condition for $\gcd(m,n) $ be a proper divisor of $\gcd(mk_2 +nk_1,mn) $ [closed]
Let $m,n,k_1,k_2 $ be natural numbers such that $(k_1,m)=(k_2,n)=1 $.
Statement 1: $\gcd(m,n) $ is a proper divisor of $\gcd(mk_2 +nk_1,mn) $, for every $k_1,k_2$ having the above property.
Statement ...
- 923
0
votes
0
answers
116
views
Multivariate polynomial representations of the infinite dihedral group
The presentation given in Wikipedia for the infinite dihedral group is
$$\langle r,s\mid s^2 =1, srs = r^{-1}\rangle.$$
Let $[R]$ denote the infinite set of reciprocal partition polynomials $R_n(u_1,...
- 10.5k
-2
votes
2
answers
217
views
Must an isomorphism preserving graph transformation preserve the order of the automorphism group?
Let $F$ be some function graph to graph which preserve graph isomorphism.
Example of such $F$ are the line graph, the $k$-subdivision of $G$
and many others.
$F$ need not preserve the order, the ...
- 25.4k
3
votes
0
answers
121
views
Twisted permutations
We consider a set $E$ with an involution (having perhaps fixed points).
We denote orbits by $\lbrace x,\overline{x}\rbrace$ (with $\overline{x}=x$ in
the case of a fixed point).
We consider sequences $...
- 17.9k
2
votes
0
answers
184
views
The canonical automorphism of the symmetric group
Let $S_n$ be the symmetric group of order $n$. Denoting simple transpositions by $\sigma_i$ the collection $\sigma_1, \dots, \sigma_{n-1}$ generates $S_n$ subject to the following relations:
$$
\sigma ...
- 1,144
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
1
vote
0
answers
69
views
Convolutions of (m)-associahedra and (m)-noncrossing partition polynomials--combinatorial proofs?
I'm looking for combinatorial proofs of the convolutional identity COP below and its specializations I) and II).
(Edit 6/2/2023: A combinatorial proof is sketched in a blog post by Mike Spivey of a ...
- 10.5k
2
votes
2
answers
234
views
Decompose complete directed graph with n vertices into n edge-disjoint cycles with length n−1
I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in Bermond and Faber - Decomposition of the ...
- 21
8
votes
1
answer
304
views
The growth rate of a commutator set in a non-elementary group
Let $G$ be a non-elementary group generated by a finite set $S$. Here, a group is called non-elementary if it is not virtually abelian. Denote $S^{\le n}:=\{g\in G: |g|_S\le n\}$ for any $n\in \mathbb ...
- 145
15
votes
0
answers
347
views
Poset defined on pairs of subgroups
Let $G$ be a group. Consider the set $P(G)$ of all pairs $(H,N)$ of subgroups of $G$ such that $N$ is a normal subgroup of $H$. Consider the relation $\leq_G$ on $P(G)$ defined as follows: $(H,N)\...
- 1,462
6
votes
1
answer
290
views
Does the Shalen-Wagreich lemma holds for non-symmetric generating sets?
Let $G$ be a group and $H$ a subgroup with finite index $d$. Then for any finite generating set $S$ of $G$, does $S^{\le k}$ contain a generating set of $H$ where $k$ is a constant depending only on $...
- 145
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