All Questions
Tagged with co.combinatorics finite-groups
190 questions
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
9
votes
0
answers
297
views
An abstract zero-sum problem
I would like to know whether the problem described below has appeared in the literature and/or whether similar questions have been studied. I would be very happy to find some references or, if none ...
- 1,169
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
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
8
votes
2
answers
576
views
Two statistics on the permutation group
Let $\mathfrak{S}_n$ be the permutation group on an $n$-element set. For each fixed $k\in\mathbb{N}$, consider the two sets
$$A_n(k)=\{\sigma\in\mathfrak{S}_n\vert\,\, \text{$\exists i,\,\, 1\leq i\...
- 43.2k
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
8
votes
2
answers
617
views
sum-sets in a finite field
Let $\mathbb{F}_p$ be a finite field, $A=\{a_1,\dots,a_k\}\subset\mathbb{F}_p^*$ a $k$-element set, for $k<p$. $\mathfrak{S}_k=$permutation gp.
Question. Is it true there is always a $\pi\in\...
- 43.2k
8
votes
2
answers
586
views
How hard is it to compute the diameter and the growth function of a finite permutation group of small degree?
Let $G \leq {\rm S}_n$ be a finite permutation group, and let
$S = \{g_1, \dots, g_k\}$ be a generating set for $G$ which is closed
under inversion and which does not contain the identity.
The growth ...
- 19.6k
8
votes
2
answers
1k
views
Are vertex and edge-transitive graphs determined by their spectrum?
A graph is called vertex and edge transitive if the automorphism group is transitive on both vertices and edges.
The spectrum of a graph is the collection (with multiplicities) of eigenvalues of the ...
- 16k
8
votes
1
answer
898
views
When Cayley graphs of the symmetric group wrt generating sets of transpositions are isomorphic?
Dear All,
I thought the following question might be well-known, but couldn't find anywhere, so decided to ask here:
Let $A$ and $B$ be two generating sets for $S_n$, consisting of transpositions.
...
- 1,437
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 $\{ ...
- 81
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
8
votes
0
answers
88
views
Is recognizing if a Latin square is isotopic to its transpose more efficient than computing its symmetry group?
Ihrig and Ihrig (2007) described a mathematical method for determining if a Latin square is isotopic to its transpose (where isotopic Latin squares vary by permuting the rows, columns and symbols). ...
- 1,327
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 ...
8
votes
0
answers
304
views
A strong sum-product "for translates" in finite fields
In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting?
Proposition There exists an absolute constant $c$ such ...
- 11.2k
7
votes
1
answer
517
views
Paths in groups
Given a finite group $G$, write $K(G)$ for the complete digraph on the elements of $G$. Label the edge from $g$ to $h$ by element $g^{-1}h$.
Question: For what groups does there exist a Hamiltonian ...
- 17.6k
7
votes
1
answer
332
views
Conjectured combinatorial non-equality
Let $n,k,\ell$ be integers for which $0\leq k<\ell \leq n-6$. For a fixed $n$, think of $k,\ell$ as being allowed to vary. I believe the values
$$(n-k-5)(k+1)(k+2)\binom n{k+3}~~~\text{and}~~~(n-...
- 1,068
7
votes
1
answer
313
views
Subgroup ranks of the symmetric group
It's well known that every subgroup $G$ of $S_n$ has a generating set of size at most $n-1$ and that this generating set can be found algorithmically (by Jerrum's filter)
I have heard many times a ...
- 539
7
votes
2
answers
751
views
Looking for deterministic criteria to generate the symmetric group?
So let $S_N$ be the symmetric group of degree $N$. We think of it as a permutation group via its
natural action on the set $T=\{1,2,\ldots,N\}$.
Say that $H\leq S_N$ is a subgroup which acts ...
- 7,609
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
7
votes
1
answer
1k
views
Burnside's Lemma and Geometry
I think one of the most interesting results in Elementary Group Theory is the so-called "Burnside's Lemma", counting the numbers of orbits of a (finite) group action.
I wonder if there is any (...
- 1,317
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
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
7
votes
1
answer
582
views
Wreath product $S_k\wr S_n$ inside $S_{kn}$
I want to understand wreath products a little better.
Currently, my intuition about them is as follows. Take $nk$ disks, pile them in order forming $n$ piles of $k$ disks (one pile contains disks {1,...
- 1,549
7
votes
1
answer
146
views
Covering a set with images of a transversal
Let $G$ be a permutation group on a finite set $\Omega$ with orbits $\Omega_1,\ldots,\Omega_k$.
By a transversal we mean a set $\lbrace\omega_1,\ldots,\omega_k\rbrace$ with $\omega_j\in\Omega_j$ for ...
- 37.7k
7
votes
2
answers
620
views
Automorphisms of subgroup of hamming cube under distance constraint
Let $S$ be a subset of $\{0,1\}^n$ such that any two elements of $S$ are at least (Hamming) distance 5 apart. I'm looking for an upper bound on the size of the automorphism group of $S$.
There's a ...
- 71
7
votes
0
answers
558
views
When is Hom(G, H) the same size as Hom(H, G)?
Let $G$ and $H$ be finite groups. Consider the ratio
$$r_{G, H} \equiv {|Hom(G, H)| \over{|Hom(H,G)|}}$$
My question is
When is $r_{G, H} = 1$? Can we characterize the pairs of groups $(G, H)$ ...
- 71
6
votes
2
answers
493
views
Finite lattice representation problem checking
[Grätzer and Schmidt 1963] proves that every algebraic lattice is isomorphic to the congruence lattice of a universal algebra. A finite lattice is algebraic. The finite lattice representation problem ...
6
votes
1
answer
629
views
Positivity of the alternating sum of indices for boolean interval of finite groups
Let $G$ be a finite group and $H$ a subgroup such that the interval $[H,G]$ is a boolean lattice.
Let $L_1, \dots , L_n$ be the maximal subgroups of $G$ containing $H$.
Let the alternative sum ...
6
votes
1
answer
332
views
Zero-sum sets in union-closed families
The Davenport constant $D(G)$ of a finite abelian group $G$ is the minimum integer $n$ such that whenever $a_1, \ldots, a_n \in G$ (not necessarily distinct), there is a non-empty $I \subseteq [n]$ ...
- 1,169
6
votes
1
answer
251
views
Subsets of a group with special property
Let $G$ be a finite group. We say a subset $A$ of $G$, $|A|=m$, is $(m,i)$-good, $m\geq 1$ and $0\leq i\leq m$, if there exist $g_A\in G$ such that we have $|gA\cap A|=m-i$.
I need some groups such ...
- 4,784
6
votes
1
answer
341
views
Sum of Young symmetrisers of a given shape
Preliminaries and notation:
Let $n\in \mathbb{Z}_{>0}$ and $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_s)\vdash n$ be a partition. Given a Young diagram of shape $\lambda$, we can associate it ...
- 87
6
votes
0
answers
1k
views
Frobenius formula
I know two formulas by the name of Frobenius.
The first one computes the number
$$\mathcal{N}(G;C_1,\dotsc,C_k):=|\{(c_1,\dotsc,c_k)\in C_1 \times \cdots \times C_k\:|\:c_1\cdots c_k=1\}|,$$
where $...
- 711
6
votes
0
answers
88
views
Numbers where there is a unique group with integral character table
Call a number $n$ special in case there is a unique group of order n whose character table consists of only integers. This should be equivalent to the condition that the number of conjugacy classes ...
- 26.5k
6
votes
0
answers
240
views
Factorization of permutations into two factors with fixed number of cycles, plus a placement condition
In my recent work I have been led to consider the following type of permutation factorizations.
Let $\pi_1$ and $\pi_2$ be two fixed permutations, with disjoint support, i.e. $\pi_1$ acts on $\{1,......
- 2,552
5
votes
2
answers
1k
views
Cardinality of certain subsets in vector spaces over finite fields
Assume that you have an $n$-dimensional vector space over a finite field (therefore the number of elements in the vector space is finite) and $F$ is a subset of this vector space which contains $m$ ...
- 228
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
5
votes
1
answer
503
views
does this set of permutations form a group? And more
Consider the group of $mn\times mn$ permutation matrices $\mathfrak{S}_{mn}$ and partition each such matrix $P$ into $n^2$ blocks of $m\times m$ matrices $Q_{i,j}$. Now, transpose each $Q_{i,j}$ (...
- 43.2k
5
votes
2
answers
567
views
Orbits of independent sets of the hypercube
How does one enumerate the distinct orbit classes of independent sets of the hypercube modulo symmetries of the hypercubes?
The counting of the number of independent sets in an $n$-dimensional ...
- 171
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
5
votes
1
answer
204
views
A decomposition of $w_0$ which is similar to the reduced decomposition
Some basic definitions about reduced decomposition:
In the symmetric group $S_n$, let $s_i$ denote the adjacent transposition $(i,i+1),i\in \{1,2,\cdots,n-1\}.$ Since $S_n$ is generated by adjacent ...
- 1,997
5
votes
2
answers
723
views
Orthogonal orthomorphisms of order 2
EDIT: There is an additional requirement that the composition of the orthomorphisms will also be order 2 (see my answer below).
A full proof is not needed, I will be happy with any argument which ...
5
votes
2
answers
245
views
Counting transitive generators according to coset type
Let $\sigma=(1\;2)(3\;4)\cdots (n-1\; n)$ be a fixed-point-free involution in $S_{2n}$. I want to count permutations $\pi$ such that the group $\langle \pi,\sigma\rangle$ generated by $\pi$ and $\...
- 1,549
5
votes
1
answer
275
views
Diameter of Cayley graphs of finite simple groups
Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).
THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...
- 237
5
votes
1
answer
316
views
Connected permutation groups and wreath product
Let $G$ and $H$ be subgroups of the symmetric groups $\mathfrak S_m$ and $\mathfrak S_n$. Assume that $n>1$ and that $H$ is a 'connected' permutation group, that is, there is no non-trivial $H$-...
- 5,822
5
votes
1
answer
764
views
Conjugacy classes in $GL_{n}(Z / pZ)$
Let $p$ be a prime number and $G=GL_n ( \mathbb{Z} / p \mathbb{Z}
)$. Consider the set $U$ of upper-triangular matrices of $G$
having entries of $1$ on the diagonal. The cardinality of $U$ is $p^{\...
- 463
5
votes
2
answers
330
views
sum of squares of Schur polynomials indexed over partition valued functions on a set
Fix a finite set $X$ and two natural numbers $d$ and $n$.
For a partition $\lambda$ and a number $d$ denote by $s_\lambda^d(x_1,\dots,x_d)$ the Schur polynomial in $d$-many variables $x_1,\dots,x_d$. ...
- 725
5
votes
1
answer
264
views
Group not leaving subset invariant
Let $Y,X$ be two sets of size n,m. Let $Y\subset X$.
What is the maximal group(in size) $G< Sym(X)$ such that gY=Y imply that $g=1$?
Here I mean that the only permutation which permutes elements of ...
- 2,179
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
5
votes
0
answers
196
views
Are finite groups of exponent $d$ rare for $d \neq 4$?
Is there a way to prove, that $\lim_{n \to \infty} \frac{\text{the number of all groups of exponent }d \text{ and order less than }n}{\text{the number of all groups of order less than } n} = 0$ for $d ...
- 2,618