# Tagged Questions

**1**

vote

**2**answers

152 views

### Cubic Cayley (undirected) graphs

The generators of a cubic Cayley graph always include at least one involution, since 3 is odd. There are then two possibilties for the other two generators: either (A) they are also (distinct) ...

**6**

votes

**1**answer

159 views

### Duration and critical groups order in sandpile models and chip firing games

The famous chip firing game (which is closely related to sandpile models) goes like this:
Place chips at the vertices of a graph. REPEATEDLY: If a vertex $v$ of
degree $d_{v}$ has at least ...

**2**

votes

**0**answers

47 views

### When polynomial GI implies polynomial (edge) colored GI?

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge ...

**13**

votes

**0**answers

463 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, ...

**3**

votes

**1**answer

153 views

### Switching representatives of right coset in a paper on fundamental domain of tree of GL(2)

I have a question concerning the following paper: "The fundamental domain of the tree of GL(2) over the function field of an elliptic curve" by Shuzo Takahashi. (1993, Duke Math. J., Vol. 72, No. 1). ...

**18**

votes

**3**answers

608 views

### Number of primitive $n$th roots with positive versus negative real parts

Does anyone know a reference to the following results, which I can prove, but I suspect may be known. Let $R(n)$ denote the number of primitive $n$th roots of unity with positive real part, and $L(n)$ ...

**5**

votes

**1**answer

404 views

### A generalized Burnside's lemma

Let $G$ be a finite group acting on a set $X$, and let $S\subseteq G$ be a union of conjugacy classes. Then I believe I can prove:
$$ \sum_{[x]\in X/G} \frac{|G_x \cap S|}{|G_x|} = \sum_{g\in S} ...

**7**

votes

**0**answers

178 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 ...

**6**

votes

**1**answer

351 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 ...

**1**

vote

**0**answers

44 views

### On generating Euler Square of index q, q-1 (where q is any prime power)

Can somebody help me in generating Euler Square of index q, q-1 (where q is any prime power). Also, kidly tell me if there is any code availeble for generating the stated Euler Square. The details of ...

**3**

votes

**1**answer

188 views

### Product of cycles of length $n$

Let $n = 2k$ and suppose that $\sigma$ is a permutation in $S_n$ which is equal to a product of k disjoint cycles of length $2$. In how many ways one can write $\sigma$ as a product of two cycles of ...

**25**

votes

**2**answers

881 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 ...

**1**

vote

**1**answer

193 views

### Groups with no small generating set

Is there a classification of groups having the property that any set of $d$ elements (say including the identity) is contained in a proper subgroup?
It is appealing to call the maximum such integer ...

**14**

votes

**1**answer

550 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 ...

**6**

votes

**2**answers

464 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$?

**6**

votes

**1**answer

194 views

### The line graphs of complete graphs and Cayley graphs

Let $n>3$ be an odd integer and let $K_n$ denote the complete graph on $n$ vertices.
For which integers $n$ the line graph $L(K_n)$ is a Cayley graph?
For even $n$, it follows from a result of ...

**0**

votes

**0**answers

48 views

### Finding stable ideals of F_3[[X,S]] by group action.

Let k > 1 be a positive integer and define the action σ_k on F_3[[X,S]] by
σ_k: X ---> X + S + X^k
σ_k: S ---> S + S^3.
Then,
Conjecture: There exists a principal ideal (a) other than (S) such ...

**4**

votes

**2**answers

268 views

### Concatenation of strings [closed]

We have two strings (i. e., finite tuples) $A$ and $B$.
We have to find if for some positive integers $n$ and $m$, the string $A$ concatenated $n$ times equals the string $B$ concatenated $m$ times or ...

**5**

votes

**2**answers

397 views

### Subgroups of S_n consisting of elements having each less than 2 fixed points

I would like to know what is already known in literature about the following problem:
For what $n>0$ is it possible to find subgroup $H$ of $S_n$ having exactly $n(n-1)$ elements
with the property ...

**6**

votes

**2**answers

460 views

### Word length in the symmetric group

Let $n \geq 1$ and let $H_n$ be a 2-Sylow subgroup of the symmetric group $\mathrm{Sym}(2^n)$. Let also consider the cycle $\gamma_n = (1, \ldots, 2^n)$ of order $2^n$.
If we assume moreover that ...

**9**

votes

**4**answers

852 views

### Number of Permutations?

Edit: This is a modest rephrasing of the question as originally stated below the fold: for $n \geq 3$, let $\sigma \in S_n$ be a fixed-point-free permutation. How many fixed-point-free permutations ...

**24**

votes

**3**answers

602 views

### What is the probability two random maps on n symbols commute?

It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...

**2**

votes

**1**answer

65 views

### Commensurability of 2-colorings of finite 4-valent graphs

It is quite easy to show that given two finite 4-valent graphs $X,X'$ (I will take the convention that there is at most one edge between two vertices, but allow loops) there is a third such graph ...

**2**

votes

**1**answer

142 views

### Lattice automorphisms of finite order

Are there any known examples of lattice automorphisms of finite order in indefinite lattices being classified up to conjugacy?

**10**

votes

**3**answers

907 views

### A problem on a specific integer partition

Let $n$ be a positive integer, we consider partitions of the following form :
$$n = d^{2}_{1} + d^{2}_{2} + ... + d^{2}_{r}$$ such that :
$d_{i}\vert n$
$1=d_{1}<d_{2} \le d_{3} \le ... \le ...

**1**

vote

**0**answers

74 views

### Group actions on polytopes in indefinite integer lattices

Is anything at all known about polytopes in indefinite integer lattices? I'm interested in lattice automorphisms which preserve certain polytopes of "high regularity" (e.g. cones). As a first step, ...

**6**

votes

**2**answers

271 views

### Embedding of a “quotient graph”

Consider the simple undirected graph $G$ with natural equivalence relation $\sim$ on $V(G)$:
$u\sim v$ iff they are similar, i.e. iff there exists $\phi\in Aut(G)$ with $\phi(u)=v$.
Define a ...

**2**

votes

**2**answers

329 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 ...

**4**

votes

**0**answers

160 views

### Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...

**5**

votes

**1**answer

166 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 ...

**5**

votes

**2**answers

602 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 ...

**3**

votes

**2**answers

588 views

### A problem about Determinant of sum of permutation matrices

Let $w_1$ and $w_2$ be two permutations of $\{1, \cdots , k\}$ such that for all $1\leq i \leq k$, $w_1(i)\neq w_2(i)$. Let $m$ and $n$ be two relatively prime integers. Then is there exist two ...

**14**

votes

**0**answers

241 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 ...

**2**

votes

**1**answer

281 views

### Automorphism groups of indefinite non-unimodular integer lattices

Does anyone know of any papers in which structural aspects of the orthogonal group of some indefinite non-unimodular integral lattice are calculated? The exact lattice isn't so important and they ...

**4**

votes

**3**answers

249 views

### multiply transitive groups

It seems to be well-known that the six-transitive finite groups are the symmetric and alternating groups, and the only other four-transitive finite groups are the Mathieu groups (the statement can be ...

**4**

votes

**1**answer

177 views

### Density/Thickness of rank 3 spherical buildings

I am trying to study (finite) spherical buildings from a very combinatorial point of view : Every rank 3 spherical building is a finite simplicial complex of dimension 3, so one can define its density ...

**1**

vote

**1**answer

178 views

### Group with 2 orbits on the nonnegative integers — description of the orbits

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 ...

**5**

votes

**0**answers

346 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 ...

**11**

votes

**0**answers

301 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 ...

**11**

votes

**0**answers

396 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
...

**2**

votes

**0**answers

154 views

### Enumerating certain solutions to the equation XAX=B in the Symmetric Group

I'm interested in understanding how to enumerate a certain subset of the solutions to the equation $XAX=B$ in the symmetric group $\Sigma_{n}$. This is related to a topological problem- counting a ...

**2**

votes

**0**answers

139 views

### Summing Characters of the Symmetric Group over Derangements (Enumerative Combinatorics: Vol. II Ex. 7.63)

The following exercise is out of Stanley's Enumerative Combinatorics: Vol. II (Ex. 7.63):
For $\lambda \vdash n$ define $d_\lambda = \sum_{w \in D_n} \chi^\lambda(w)$ where $D_n$ is the set of all ...

**12**

votes

**3**answers

534 views

### Minimal size of subsets $A,B$ in a finite group $G$ such that $AB=G$

Given a finite group $G$ with $N$ elements what are the "smallest" possible subsets
$A,B$ of $G$ such that $G=AB$ (ie. every element of $G$ is a product of an element in $A$
and an element in $B$)?
...

**5**

votes

**0**answers

213 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 ...

**11**

votes

**2**answers

350 views

### Finite vertex-transitive graphs that look like infinite vertex-transitive graphs

For a vertex-transitive graph $G$ and a positive integer $d$, and let $G(d)$ be the subgraph induced by all vertices of $G$ within distance $d$ of some given vertex $v$ (since $G$ is ...

**4**

votes

**3**answers

348 views

### automorphisms of graphs and finite permutation groups

I am interested in automorphisms of graphs and in using tools from permutation groups (especially such as in Wielandt's text on finite permutation groups, which I have been studying). What are some ...

**8**

votes

**0**answers

148 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 ...

**0**

votes

**0**answers

62 views

### Number of subgroups of finite abelian p-groups with a certain cotype.

Given a finite abelian $p$-group $G$ of rank $r$ I'm looking for the number of elements in a group $H$ with $\mathrm{rk}(H)=r$, such that $H/\langle y\rangle\cong G$.

**0**

votes

**0**answers

28 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, ...

**19**

votes

**3**answers

736 views

### Primes occurring as orders of elements of a finitely presented group

Is it true that given a finitely presented group $G$, either all primes
or only finitely many of them occur as orders of elements of $G$?