1
vote
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
3answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
2answers
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
2answers
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
2answers
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
4answers
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
3answers
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
1answer
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
1answer
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
3answers
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
0answers
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
2answers
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
2answers
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
0answers
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
1answer
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
2answers
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
2answers
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
0answers
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
1answer
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
3answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
3answers
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
0answers
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
2answers
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
3answers
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
0answers
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
0answers
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
0answers
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
3answers
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$?