All Questions
Tagged with co.combinatorics gr.group-theory
134 questions with no upvoted or accepted answers
27
votes
0
answers
940
views
A question on simultaneous conjugation of permutations
Given $a,b\in S_n$ such that their commutator has at least $n-4$ fixed points, is there an element $z\in S_n$ such that $a^z=a^{-1}$, and $b^z=b^{-1}$? Here $a^z:=z^{-1}az$.
Magma says that the ...
- 271
23
votes
0
answers
1k
views
Do all possible trees arise as orbit trees of some permutation groups?
I.Motivation from descriptive set theory
(Contains some quotes from Maciej Malicki's paper.)
The classical theorem of Birkhoff-Kakutani implies that every metrizable topological group G admits a ...
- 181
20
votes
0
answers
451
views
Row of the character table of symmetric group with most negative entries
The row of the character table of $S_n$ corresponding to the trivial representation has all entries positive, and by orthogonality clearly it is the only one like this.
Is it true that for $n\gg 0$, ...
- 24.2k
17
votes
0
answers
536
views
Question about combinatorics on words
Let $\{a_1,a_2,...,a_n\}$ be an alphabet and let $\{u_1,...,u_n\}$ be words in this alphabet, and $a_i\mapsto u_i$ be a substitution $\phi$.
Question: Is there an algorithm to check if for some $m,k$...
user6976
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, ...
- 11.2k
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
17
votes
0
answers
449
views
Splay trees and Thompson's group $F$
( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...
- 992
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
12
votes
0
answers
513
views
Converse of Frobenius
Enumerate the elements of a finite group $G$ as follows: $g_1,g_2,\dots,g_n$. Introduce $n$ variables indexed by the elements of $G$: $x_{g_1},\dots,x_{g_n}$.
Consider the matrix $X_G$ with entries $...
- 43.2k
12
votes
0
answers
558
views
Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers
Definition / Question
Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where
$0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$...
- 19.6k
12
votes
0
answers
529
views
A commutative monoid associated with a finite abelian group
Let $M$ be a finite abelian group, and denote by $e_m$, for $m \in M$, the canonical basis of $\mathbb{Z}^M$. For $m, n \in M$ define elements $v_{m,n} \in \mathbb{Z}^M/\langle e_0\rangle$ as
$$
v_{m,...
- 181
11
votes
0
answers
357
views
Recognizing reflection subgroups of Coxeter groups
Given a Coxeter system $(W,S)$ with reflections $T$, and any subset $A \subseteq T$, it is known that the reflection subgroup $W_A$ generated by $A$ has a canonical choice $S_A$ of generators so that $...
- 2,753
11
votes
0
answers
186
views
Iterated automorphism groups of finite groups
Let $\mathcal{G}$ be the set of isomorphism classes of finite groups.
There is an operation $\mathrm{Aut} : \mathcal{G} \rightarrow \mathcal{G}$ which gives the automorphism group of a given group, ...
- 12.4k
11
votes
0
answers
253
views
When is a group Fibonacci sequence contained in a single conjugacy class?
First a definition: a Fibonacci sequence in a group is a sequence in which the first two elements may be arbitrary, and from there on each element is a product (using the group operation) of the ...
- 211
10
votes
0
answers
205
views
How to describe the power operation on Lie groups?
Let $\mathfrak{g}$ be a semisimple Lie algebra over $\mathbb{C}$, or its compact form over $\mathbb{R}$. Recall that the automorphism group $\operatorname{Aut}(\mathfrak{g})$ is of the form $G^{\...
- 54.6k
10
votes
0
answers
436
views
Commuting matrix variety $[A,B]=0$ - can one geometrically explain divisibility of $F_ q$ point count by high powers of $q$?
$\DeclareMathOperator\Comm{Comm}\DeclareMathOperator\Id{Id}$Consider the variety $\Comm$ of commuting matrices $[A,B]=0$ over some field $K$. It is much studied, and interesting for various reasons.
...
- 24.9k
10
votes
0
answers
194
views
Permutation groups with diameter $O(n \log n)$
I suspect that many permutation puzzles can be solved in $O(n \log n)$ moves, which has led me to the following question/conjecture:
Suppose that
1. $P_i$ for $i<k=O(1)$ are permutations on an $n$ ...
- 7,545
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
534
views
Generating $S_n$ with a fundamental transposition and a big cycle
I apologize in advance if this is too amateur, this is not really my area, but I'm very curious.
We have a permutation $\pi \in S_n$ and we want to represent it as a product of $\sigma = (1\;2)$ and $...
- 231
9
votes
0
answers
275
views
pattern-avoiding permutations vs multi-core partitions
Let $\mathfrak{S}_n$ be the permutation group on $[n]$. Given the pattern $\sigma=k(k-1)\cdots321$, let $I_n(\sigma)$ be the number of involutions in $\mathfrak{S}_n$ that avoid the pattern $\sigma$. ...
- 43.2k
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
106
views
Number of occurrences of certain generators in expressions in Coxeter groups
Let $W$ be a Coxeter group (finite or infinite) with (finite) set $S$ of Coxeter generators, and let $I \subseteq S$ be some subset. If $w\in W$ then I call $m_I(w)$ the minimum total number of ...
- 32.5k
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
8
votes
0
answers
242
views
What are the known algorithms for computing the inverse of a group automorphism?
Given a finitely presented group $<x_1,x_2,...,x_n|R_1,R_2,...,R_n>$, one specifies an automorphism $\phi$ by its action on the generators, i.e. $\phi(x_i)=w_i$ for some (reduced) words $w_i$ in ...
8
votes
0
answers
622
views
Counting and understanging commuting functions.
Fix a positive integer $n$, and consider the functions from a set of size $n$
to itself. Let $cp(n)$ denote the number of ordered pairs $\langle f,g
\rangle$ of these functions which commute, i.e., ...
- 553
7
votes
0
answers
325
views
Groups of non-orientable genus 1 and 2
The non-orientable genus (aka crosscap-number) $\overline{\gamma}(G)$ of a finite group $G$ is the minimum non-orientable genus among all its connected Cayley graphs (and $0$ if $G$ has a planar ...
- 185
7
votes
0
answers
239
views
Combinatorial Avatar of Irrep Dimensions Dividing the Order of the Group
Suppose $G$ is a finite group and $V$ a complex irreducible representation. Let $v\in V$ be a sufficiently generic vector, and consider its orbit, $O(v)=\{gv|g\in G\}$. As a naive attempt to ...
- 85.6k
7
votes
0
answers
1k
views
Example of a group with unsolvable word problem
Today I noticed that the last relator in the 27-relator presentation
of a group with unsolvable word problem given in
Donald J. Collins: A simple presentation of a group with unsolvable word problem.
...
- 19.6k
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
0
answers
190
views
The highest degree of a polynomial on a finite group
This question is motivated by the comments and the answer to this MO-question.
First let us recall some definitions.
A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\...
- 41.8k
6
votes
0
answers
479
views
Darkness in the lamplighter group
Consider paths through the lamplighter group $\mathbb{Z}_n\wr\mathbb{Z}$ with steps consisting of moving left, moving right, and toggling the lamp at the current position. How many paths of length $m$ ...
- 2,203
6
votes
0
answers
226
views
A challenging problem on disjoint cosets
Motivated by my negative solutions (see this paper published in Chinese Ann. Math. 13A(1992)) to two open problems on disjoint residue calsses posed by A. P. Huhn and L. Megyesi [Discrete Math. 41(...
- 15.6k
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
5
votes
0
answers
79
views
A Spatial-Orientation Counting Problem
Suppose I have 36 black blocks of dimensions 1x2x3. I can stack them 2 across, 3 deep and 6 high to make a nice looking cube of dimensions 6x6x6. I then proceed to paint the surface of this cube red. ...
- 333
5
votes
0
answers
241
views
Counting the number of orbits finite groups of "diagonal type"
Let $n$, $k$, $r_1, \dots, r_k$ be positive integers.
For each $i \in [k]:=\{1,\dots,k\}$, suppose we are given $n$ permutations of the the set $[r_i]$, that is $f_1^{(i)}, \dots, f_n^{(i)}$ in $\...
- 2,479
5
votes
0
answers
163
views
Graphs quasi-isometric to a plane
Suppose that a planar graph $\Gamma$ is quasi-isometric to the Euclidean plane. Is it true that the growth function $g(r)$ of $\Gamma$ with respect to any vertex $o$ (that is $g(r)$ is the number of ...
user6976
5
votes
0
answers
241
views
A problem on automatic groups and geodesic paths on the Cayley graph
Let $\Gamma = \langle S \mid R \rangle$ be a finitely generated group, with the neutral element $e \not \in S= S^{-1}$.
Let $\ell : \Gamma \to \mathbb{N}$ be the world length related to $S$.
For ...
5
votes
0
answers
478
views
What is God's number for the WrapSlide puzzle?
WrapSlide is a slide-puzzle (reminding of Rubik's Cube) consisting of a 6x6 grid of coloured tiles which are separated into four quadrants of 3x3 tiles. When it is unmixed all the tiles in a quadrant ...
5
votes
0
answers
267
views
(Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples
Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...
- 3,612
5
votes
0
answers
241
views
Find a lower bound for a pre-invariant $Fol(L(F_m), X_m)$
In the paper of Bannon and Ravichandran, A Folner invariant for type $\rm{II}_1$ factors, they defined an invariant $Fol(M)$ for a separable type $\rm{II}_1$ factor $M$, especially for the free group ...
- 1,528
5
votes
0
answers
268
views
Unicity of branched covering of sphere, and Hurwitz numbers
Hurwitz's encoding counts the number of branched self-coverings of a sphere, with prescribed ramification degrees at the critical points, as numbers of factorizations of the identity in a symmetric ...
- 2,519
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
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
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
4
votes
0
answers
164
views
Scaling limits for groups
Is there a scaling-limit theory for groups the way there is for graphs ("graphons") and permutations ("permutons")?
E.g., if we map the uniform measure on the cyclic group $\mathbf{...
- 19.7k
4
votes
0
answers
134
views
Is a group determined by the number of ways its elements multiply to the identity under some ordering?
Let $G$ be a group, and for each ordered $n$ tuple $(g_1,...g_n)$ of elements of $G$, consider the function $f_n$ that outputs the number of permutations $\sigma\in S_n$ for which $g_{\sigma(1)}g_{\...
- 1,949
4
votes
0
answers
248
views
Generalization of a theorem of Øystein Ore in group theory: the infinite case
This post is the infinite version of this one, and is motivated by an exchange with Carmela Musella and Maria De Falco. We are interested in relative versions of the following Ore's theorem and ...