All Questions
Tagged with finite-groups co.combinatorics
190 questions
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
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)...
- 151k
1
vote
1
answer
155
views
Max order for which connected Cayley Graphs are known to be Hamiltonian
There is a well-known conjecture that all connected Cayley graphs are Hamiltonian.
For how large a value of n has the conjecture been verified (i.e., for all groups whose order is at most n)?
- 349
37
votes
2
answers
2k
views
A group-theoretic perspective on Frankl's union closed problem
Here is a group theoretic phrasing of a special case of the union closed conjecture:
Question: Given a finite group $G$, is there an element of prime power order which is contained in at most half ...
- 85.6k
17
votes
1
answer
798
views
Are There Always Group Generators Which Give Unimodal Growth?
Suppose $G$ is a $k$-generated finite group. Is there always a set of $k$ elements which generate the group and have a unimodal counting function?
Background:
The counting function, $f(n)$, is a ...
- 2,143
18
votes
2
answers
2k
views
Number of isomorphism types of finite groups
Are there some good asymptotic estimations for the number $F(n)$ of non-isomorphic finite groups of size smaller than $n$?
- 1,281
4
votes
2
answers
1k
views
Automorphism group action leads to a "quotient graph"
Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:
$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.
Define a new ...
- 747
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
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 ...
17
votes
0
answers
512
views
Maximum automorphism group for a 3-connected cubic graph
The following arose as a side issue in a project on graph reconstruction.
Problem: Let $a(n)$ be the greatest order of the automorphism group of a 3-connected cubic graph with $n$ vertices. Find a ...
- 37.7k
12
votes
1
answer
290
views
Largest subset of $GL_n(p)$ in which pairwise subtraction is also in $GL_n(p)$
Suppose $X\subset \mathrm{GL}_n(p)$ is a set of invertible matrices such that for every $A,B\in X$ then also $A-B\in \mathrm{GL}_n(p)\cup \{0\}$. (If anyone knows a name for such sets I would be ...
- 407
0
votes
0
answers
39
views
Minimum number of solutions in a system of equalities and non-equalities
Let $k<N$ and $P_1, ..., P_{2k+1}, \lambda_1, ..., \lambda_k$ be elements of a finite group $G$ of size $N$.
Find the minimum number of solution of the system
$$P_{2i} + P_{2i+1} = \lambda_i, \...
- 43
10
votes
1
answer
906
views
Which finite groups are not the automorphism group of some rooted finite tree?
The question is as given in the title:
Which finite groups are not the automorphism group of some rooted finite tree?
A rephrasing could be: Is any finite group representable as the automorphism ...
- 1,306
18
votes
1
answer
1k
views
Lower bounds on the number of elements in Sylow subgroups
I posted this question on Math.SE (link), but it didn't get any answers so I'm going to ask here. This is an edited version of the question.
Let $p$ be a prime and $n \geq 1$ some integer. ...
- 2,217
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 $...
- 19.6k
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
3
votes
2
answers
361
views
The cycle structure of twisted wires, connected
Suppose you have $n$ (blue) wires linearly arrayed at junction box $A$,
connected to a remote junction box $B$, where the wires are now
arrayed
along a line in a randomly permuted order, i.e.,
each ...
- 151k
23
votes
5
answers
5k
views
Has any attempt been made to classify finite groupoids?
I recently stumbled upon the Mathieu groupoid and I found them fascinating.
It appears as a subset of $S_{13}$ which is not closed under multiplication, but it turns out to be a groupoid with 13 ...
- 2,040
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
1
vote
3
answers
1k
views
primes dividing binomial coefficients
Dear All,
I am considering maximal subgroups of odd index in Alternating and Symmetric groups, and this leeds me to some questions on binomial coefficients that I presently do not know and that I ...
- 195
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
4
votes
1
answer
426
views
From the chinese remainder theorem to products of transitive G-sets
Note: I am aware of the question Analog to the Chinese Remainder Theorem in groups other than Z_n.
For an abelian group $A$, every transitive $A$-set $M$ is of course isomorphic, as an $A$-set, to a ...
- 35.5k
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
50
votes
6
answers
11k
views
Generating finite simple groups with $2$ elements
Here is a very natural question:
Q: Is it always possible to generate a finite simple group with only $2$ elements?
In all the examples that I can think of the answer is yes.
If the answer is ...
- 7,609
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
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}$?
...
- 2,751
2
votes
1
answer
370
views
Large subgroups of the Hamming cube
Let's consider the abelian group $\mathbb{Z}^N_2$ equipped with the Hamming metric (the hypercube).
Suppose I have a subgroup of this hypercube (not necessarily a subcube) which is generated by a set ...
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
29
votes
3
answers
4k
views
Roots of permutations
Consider the equation $x^2=x_0$ in the symmetric group $S_n$, where $x_0\in S_n$ is fixed. Is it true that for each integer $n\geq 0$, the maximal number of solutions (the number of square roots of $...
- 109k
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
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
40
votes
1
answer
2k
views
Orders of products of permutations
Let $p$ be a prime, $n\gg p$ not divisible by $p$ (say, $n>2^{2^p}$). Are there two permutations $a, b$ of the set $\{1,...,n\}$ which together act transitively on $\{1,2,...,n\}$ and such that all ...
user6976
35
votes
3
answers
3k
views
Does the hypergraph structure of the set of subgroups of a finite group characterize isomorphism type?
Question
Suppose there is a bijection between the underlying sets of two finite groups $G, H$, such that every subgroup of $G$ corresponds to a subgroup of $H$, and that every subgroup of $H$ ...
- 483
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 ...
- 20.2k
2
votes
1
answer
337
views
Transitivity-related property of finite permutation groups
Let $\cal F$ denote the group of all finitely-supported permutations of $\mathbb N$.
Say that a finite subgroup $G$ of $\cal F$ is singular if $G$ acts transitively on
$\lbrace 1,2,3 \rbrace$ but ...
- 3,595
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
26
votes
2
answers
997
views
Is $\varphi(n)/n$ the maximal portion of $n$-cycles in a degree $n$ group?
Let $G$ be a degree $n$ group, i.e., a subgroup of the symmetric group $S_n$. Let $p(G)$ be the number of $n$-cycles in $G$ divided by the size of $G$.
Examples:
If $G$ is a cyclic transitive ...
- 3,362
10
votes
2
answers
2k
views
Number of faithful representations of a finite group
Is it known how many faithful linear representations a finite group G has on a complex vector space of given dimension? What if G is abelian?
I would even be interested in this special case: the ...
- 4,807
15
votes
3
answers
2k
views
Injective proof about sizes of conjugacy classes in S_n
It's not hard to count the number of permutations in a given conjugacy class of Sn. In particular, the number of permutations in Sn whose cycle decomposition has ci i-cycles is n!/(Πi=1n ci!ici). ...
- 1,975