All Questions
Tagged with finite-groups co.combinatorics
190 questions
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 ...
- 2,446
1
vote
1
answer
116
views
Can the reversed lattice of a subgroups interval be represented?
Let $G$ be a finite group and $H$ a subgroup. The interval $[H,G]$ is the lattice of overgroups of $H$.
It is an open problem to know if every finite lattice can be represented by such an interval (...
- 53.3k
12
votes
1
answer
682
views
A sum over characters of the symmetric group
Let $C_\mu$ be the size of the conjugacy class in $S_n$ of permutations whose cycletype is the partition $\mu\vdash n$. Let $\chi$ be the characters of the irreducible representations of $S_n$.
Let $\...
- 50.8k
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
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
3
votes
0
answers
186
views
Which Dihedral Groups are $\text{CI}$-Groups?
Let $D_{n}$ denotes the dihedral group of order $2n$. Firstly, for self-referencing of the question, I give some definitions which are standard.
Let $G$ be a finite group. A subset $S$ of group $G$ ...
- 4,784
4
votes
1
answer
491
views
What is the permutation group generated by those three given morphisms of the affine space $\mathbb{F}_q^3$?
Let $\mathbb{A}^3 = \mathbb{F}_q^3$. Consider the following three functions $\mathbb{A}^3\to\mathbb{A}^3$:
\begin{eqnarray*}
h: (x, y, z) &\mapsto& (x, y, xy - z) \\
u: (x, y, z) &\mapsto&...
- 22.5k
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 ...
- 6,357
1
vote
1
answer
178
views
Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have minimum feedback vertex set of size $\Omega(n)$?
Feedback vertex set is a set of vertices whose removal leaves an acyclic graph.
It is known that every vertex transitive graph on $n$ vertices has minimum vertex cover of size $\Omega(n)$. It is also ...
- 56
3
votes
0
answers
215
views
scalar multiple of Young symmetrizer
The following is a lemma from Fulton and Harris' book -Representation theory,a first course (page 53):
Lemma: For all $x\in \mathbb{C}\mathfrak{S}_r$, $c_{\lambda}\cdot x\cdot c_{\lambda}= scalar \;...
- 181
9
votes
2
answers
403
views
Certain signed sum over $S_n$
The following question appeared in my research:
Let $G_1,G_2,G_3$ all be subgroups of $S_n$, and consider the sum
$$
\sum_{g_i \in G_i, g_1g_2g_3 = id} \epsilon(g_1)
$$
that is, we only consider ...
- 37.4k
4
votes
0
answers
95
views
Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?
What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?
- 197
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 ...
CommunityBot
- 1
14
votes
1
answer
865
views
Enumeration of $0-1$ matrices with determinant $1$
Has the number $f(n)$ of $n \times n$, $0{-}1$ matrices whose determinant is $+1$
been enumerated?
E.g., for $n{=}2$, there are $f(2)=3$ such matrices:
$$
\left(
\begin{array}{cc}
1 & 0 \\
0 &...
- 151k
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 ...
- 6,210
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$?
- 11.2k
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 ...
CommunityBot
- 1
17
votes
0
answers
824
views
What's the big deal about $M_{13}$?
$M_{13}$ is the Mathieu groupoid defined by Conway in
Conway, J. H. $M_{13}$. Surveys in combinatorics, 1997 (London), 1–11,
London Math. Soc. Lecture Note Ser., 241, Cambridge Univ. Press, ...
CommunityBot
- 1
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 ...
- 23k
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)?
- 3,291
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 ...
- 407
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 ...
CommunityBot
- 1
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 ...
- 18.6k
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
17
votes
0
answers
513
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 ...
- 22.5k
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. ...
CommunityBot
- 1
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
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 ...
- 5,781
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.
...
- 3,291
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 ...
CommunityBot
- 1
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 ...
- 44.4k
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 ...
- 36
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 ...
- 6,342
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)$ ...
- 13k
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 (...
- 14.4k
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
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 ...
CommunityBot
- 1
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). ...
CommunityBot
- 1