Questions related to permutations, bijections from a finite (or sometimes infinite) set to itself.

**0**

votes

**0**answers

20 views

### Algorithm for Longest Common Subtour

For a new kind of heuristic for the TSP I need to calculate the longest subtour, that is common to a set $T_1,\ ...,\ T_m$ of tours, that are "good" approximations of the optimal tour $T_{opt}$.
By a ...

**0**

votes

**0**answers

88 views

### Sum of unit vectors always has a binary span after constrained permutations

Conjecture:
Let $e_1 = (1,0,\ldots,0), \ldots , e_{m_1+m_2} = (0,\ldots,0,1)$ be the unit vectors of the standard basis $E$ of $\mathbb{R}^{m_1+m_2}$.
An enumeration $ E \cup -E = \{f_1, \ldots, ...

**4**

votes

**1**answer

103 views

### Betweenness in permutations

Let us consider permutations $\pi$ on $\{1,\dots,n\}$ as sequences $\pi(1),\pi(2),\dots,\pi(n)$. For a permutation $\pi$ let $R(\pi)$ be the ternary relation with $(x,y,z)\in R(\pi)$ whenever element $...

**3**

votes

**2**answers

267 views

### Determining whether or not a subset of $S_n$ generates $S_n$

I have a certain family of subsets of $S_n$, and I'd like to know which subsets in this family generate $S_n$. What techniques exist for solving this type of problem?
Are there any known results on ...

**6**

votes

**1**answer

126 views

### Number of linear orderings of a set to have balanced frequencies of triple orders

Let $S$ be a set of $n$ elements and let $Q = (s_1, s_2, \ldots, s_n)$ be a linear ordering of $S$. We write $s_i <_Q s_j$ when $s_i$ appears before $s_j$ in $Q$.
I want to construct a set (or ...

**0**

votes

**0**answers

21 views

### Number of Asymmetric, Balanced Permutation Matrices

let $\mathcal{ABP}$, the set of "asymmetric, balanced permutation matrices", be defined as the set of permutation matrices, that aren't equal their transpose but, for which the number $1$s below the ...

**3**

votes

**0**answers

67 views

### Is the chromatic number of the graph of the permutahedron known?

The permutahedron $\Pi_n$ is the polytope that is the convex hull of all permutations of the vector $(1,2,...,n)$. There are many results on its structure, but I couldn't find a result on the ...

**7**

votes

**2**answers

105 views

### Is there a subset of $\Sigma_n$ s.t. each pair of elements is once in each pair of positions?

Is there a subset $A \subset \Sigma_n$ such that for each pair $(x, y)$ and each pair $(i, j)$, there is exactly one permutation $\sigma \in A$ such that $\sigma(i) = x$ and $\sigma(j) = y$? Remark ...

**-3**

votes

**2**answers

169 views

### What is the number of self-inverse permutations on a set of cardinality $N$?

Given a function (aka 'permutation') $f:A \rightarrow A$, where $A$ is a finite set such that $|A| = N$, we call it a self-inverse if $f(f(x)) = x$. The sequence of how many such functions exist for ...

**6**

votes

**2**answers

484 views

### A question about (unicity of certain cycles in a Cayley graph of a) symmetric group

Let $S=\{(1,2),(1,2,3,\ldots,n),(1,2,3,\ldots,n)^{-1}=(1,n\ldots,2)\}$ be a subset of the symmetric group $S_n$. We know that $(1,2,\ldots,n)(1,2)=(2,3,\ldots,n)$, and thus $$[(1,2,\ldots,n)(1,2)]^{n-...

**1**

vote

**2**answers

54 views

### Practical permutation search problems resilient to backtrack techniques

I asked a similar question here: Permutation search problems with no known $o(n!)$ algorithms; to which one-way functions over a space of permutations gives a problem with no $o(n!)$ solution (...

**0**

votes

**0**answers

40 views

### Gramian of a permutation group orbit

let $W\in R^{d\times k},d>k$. Suppose that the associated gramian has the following structure:
$$
W^TW=(P_{1}t,\cdots,P_{k}t)
$$
with the set $\{P_{i},i=1,\cdots,k\}$ forming a group of ...

**5**

votes

**1**answer

342 views

### On the symmetric group of 2^n elements

Consider the set $ X_1^n=\{1,2,...,2^n\} $. Then define $ X_2^n $ to be the set of two element subsets of $ X_1^n $. I will construct $ X_i $ by induction on $ i $. $ X_i^n $ is the set of two element ...

**12**

votes

**2**answers

212 views

### Permutation search problems with no known $o(n!)$ algorithms

I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...

**3**

votes

**1**answer

75 views

### Density of permutation of syndetic sets of integers

Define the upper uniform density of a set $A\subset\mathbb{Z}$ to be
$$
D^+(A)=\lim_{r\rightarrow\infty}\sup_{a\in\mathbb{R}}\frac{|A\cap[a,a+r)|}{r}
$$
Fix an arbitrary permutation of the integers $\...

**4**

votes

**1**answer

127 views

### Maximum size of minimal sequence of transpositions whose product is a given permutation

Consider the sequence $S = 1,2,3,\ldots n$ of elements, along with a sequence $T = t_1, t_2, \ldots, t_m$ of transpositions. Each transposition $t_i$ is a tuple $(a_i, b_i) \in [n]^2$. When applying a ...

**1**

vote

**1**answer

126 views

### Counting faces on multipermutahedra/multipermutohedra

A multipermutahedron is the convex hull of all permutations of a list of numbers. For example, $\Pi(0,1,2)$ generates a regular hexagon, and $\Pi(0,1,1,2)$ generates a cuboctahedron.
In general, ...

**3**

votes

**1**answer

158 views

### Braid group: Can a left-twist increase the number of right twists?

Disclaimer: This question was first posted on math.se without any answer.
This is something that naturally occurs in my research, but I am no expert on this - it feels like a natural question so I am ...

**3**

votes

**1**answer

129 views

### Choosing $K$ “centers” from the space of permutations

Let $\Pi$ denote the space of all permutations of $\{1,\dots,n\}$, and let $d(\cdot,\cdot)$ be a metric on $\Pi$. Suppose I am given a large integer $K$ and I have to select $K$ permutations $\pi_1,\...

**5**

votes

**1**answer

169 views

### Counting the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$, where $i < j$ and number of inversions is $k$

How can I prove the following:
$d^{ij}(m,k) > d^{ji}(m,k)$ for all $k < \frac{1}{2}\binom{m}{2},$
where $d^{ij}(m,k)$ denotes the number of permutations of $(1,\ldots,i,\ldots,j,\ldots,m)$ ...

**0**

votes

**0**answers

50 views

### normal sets and conjugate generating sets of $S_n$

In this arXiv paper (p. 13), Steinhardt defines a normal set in $S_n$ as follows:
Definition: A split set of more than two cycles generating $S_n$ is said to be normal if any element is adjacent to ...

**1**

vote

**0**answers

38 views

### Invariants of Permutations with Predicate and Equivalency Relation

Has the following kind of problem been investigated previously and, where can I find information about it:
Given
the set $\mathbb{P}_{n_0}$ of all permutations of $n_0$ elements
a ...

**5**

votes

**1**answer

189 views

### Hyperoctahedral group acting on a special permutation

Let $[n]=\{1,...,n\}$ and $[\hat n]=\{\hat 1,...,\hat n\}$. Realize the hyperoctahedral group $H_n$ as the centralizer of the permutation $(1\hat 1)\cdots (n \hat n)$. It has $2^n n!$ elements.
Let $...

**2**

votes

**0**answers

67 views

### clustering permutations by shared subsequences [closed]

I have a question, stimulated by some biology, about comparing sets of permutations.
The problem
Let's think of genes on a bacterial chromosome as beads on a string - atomic, unique objects, with ...

**5**

votes

**0**answers

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

**1**

vote

**0**answers

63 views

### Decomposing a matrix into the tensor product of a permutation and orthogonal matrix

Suppose I have a square matrix $A \in \mathbb{R}^{mn \times mn}$. I want to find
$$\arg \min_{P, Q} \|A - P \otimes Q\|_F$$
where $P$ is an $m \times m$ permutation matrix and $Q$ is an $n \times n$...

**3**

votes

**2**answers

204 views

### Counting Specific Permutations of Elements in a Multiset

I have a question regarding counting permutations of a multiset's elements. The problem is the following:
Given a multi-set $M=\{0^{m}, 1^{n-m}\}$ the number of all possible permutations of its ...

**2**

votes

**2**answers

105 views

### On $XX'=I$ such that $AX=XB$ is true when $A,B\in\{0,1\}^{n\times n}$

Given real symmetric matrices $A,B\in\{0,1\}^{n\times n}$ is it true that $$AX=XB$$ has a solution of form $X$ a permutation matrix iff a solution with $XX'=I$ exists? We are over reals.
It is clear ...

**0**

votes

**0**answers

97 views

### On number of disjoint sets with small stack depth in a set of permutations

Given k-distinct permutations $\sigma_1,\sigma_2,...,\sigma_k \in S_n$ where $k \leq 2^{\sqrt{n}}$ and $k >1$ (note that k is much smaller than number of possible permutations on [n]),
What is ...

**12**

votes

**0**answers

190 views

### How does a permutation $P$ affect the singular value $\sigma_{\text{max}}(Q^\top P^\top Q)$ for orthogonal $Q$?

Let $q_i$ for $i=1,\ldots,m$ be the columns of the matrix $Q\in\mathbb{R}^{n\times m}$, $n\geq 2m$, which are pairwise orthonormal ( i.e.
$q_i^\top q_j = \begin{cases} 1 & \text{if}\quad i=j \\ 0 &...

**7**

votes

**2**answers

572 views

### Can all the sporadic groups be expressed as permutation groups based on a single big cycle?

Working on M11, I came up with that it can be generated using the following permutations:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[[2, 0, 1, 7], [3, 4, 5, 6]]
[[4, 0, 6, 7], [2, 3, 1, 5]]
[[0, 7], [4, 6], ...

**4**

votes

**2**answers

318 views

### Why does iterated indexing avoid cycles of length 5?

Start with a permutation $s_0$ of the numbers
$(1,\ldots,n)$, e.g., for $n=10$,
$s_0=(8,2,1,6,9,7,10,5,4,3)$.
Form $s_1$ by using the numbers in $s_0$ as indices into $s_0$.
So $s_1$ is composed of ...

**2**

votes

**2**answers

257 views

### $k$-th subset in order of increasing sum

I have an array of integers T[N] indexed from 1. For example T[1] = 1, T[2] = 4, T[3] = 5, T[4] = 9. Let's enumerate all subsets of this set in a certain order: increasing sum of the elements. In case ...

**3**

votes

**3**answers

139 views

### Characterizing (up to permutations) finite sequences of real numbers

Let $S=\{x_1,\cdots, x_N\}$ be a finite sequence of real numbers.
I am interested in characterizing the family of functions $F$ such that for any $f\in F$ the function
$$
c(\lambda) =\sum_{i=1}^{N}f(...

**5**

votes

**1**answer

104 views

### Weights on cyclic orderings

Are there standard or known weights/metrics on cyclic orders?
Cyclic orderings are different ways of listing elements from a finite set, where you call two lists the same if they differ only by a ...

**5**

votes

**1**answer

118 views

### What is the criterion for a matrix containing vectors and their permutations being invertible?

Consider the matrix $A\in\mathbb{R}^{m\times 2m}$. Let any arbitrary choice of $m$ columns of $A$ be linearly independent. Together with a permutation $P\in\mathcal{P_{2m}}$, one can build the matrix $...

**7**

votes

**1**answer

152 views

### Weighted Permutation Sum

I am trying to find out a closed-form formula (or a generating function at least) for the number of permutations $\sigma$ that satisfy $$ S = \sum_{i = 1}^{n} i\sigma(i)$$ for a given value of $S$. We ...

**2**

votes

**0**answers

126 views

### How hard is recognizing a permutation that is a square for the shift product?

This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...

**10**

votes

**3**answers

515 views

### Is the Number of Carries in Integer-Addition Associative?

Is it true that the number of carries, when calculating the sum of a finite set of finite positive integers, is constant (i.e. independent of their permutation and the order in which the additions ...

**2**

votes

**0**answers

61 views

### symmetric points on symmetric spaces

Let $M$ by an $m$-dimensional symmetric space (or a general Riemannian manifold). The finite distinct points $p_1,p_2,\cdots,p_n\in M$ are said symmetric, if for any permutation $\sigma$ on $1,2,\...

**1**

vote

**0**answers

48 views

### Finding optimal set of permutations [closed]

I have the following data set of a human population. The data set captures households and relationships of the persons living in those households. My problem is how to group the individuals into ...

**3**

votes

**1**answer

91 views

### convex hull of the set of permutations with one cycle

is there a way to describe the convex hull of the set of permutation matrices with exactly one non-trivial cycle?
or maybe I should ask for the convex hull of cycle matrices :
let $(i_{1},..,i_{k})$ ...

**0**

votes

**0**answers

52 views

### Sparse Matrix Reordering

Matrix reorderings are important for many direct solvers. Sometimes the objective
is to reduce the bandwith or the generated fill in by LU Decomposition.
I am interested in a reordering which reduces ...

**27**

votes

**5**answers

1k views

### How many rearrangements must fail to alter the value of a sum before you conclude that none do?

This will not be altogether unrelated to this earlier question.
For which classes $C$ of bijections from $\{1,2,3,\ldots\}$ to itself is it the case that for all sequences $\{a_i\}_{i=1}^\infty$ of ...

**0**

votes

**0**answers

69 views

### Efficient recognition of sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, I got interested in this sorting problem:
Input: a sequence $A$ of $2N$ positive integers.
...

**11**

votes

**1**answer

241 views

### A Collatz-like question about permutations

An answer to this question would provide an explicit counterexample to this question, but otherwise I don't know if it is interesting.
Consider all permutations $\pi$ on the natural numbers such that ...

**18**

votes

**1**answer

500 views

### Rearrangements that never change the value of a sum

I posted this question on math.stackexchange.com and so far the only answer posted (also mentioned in the comments under the question) shows that one of my rash initial guesses about the bottom-line ...

**0**

votes

**1**answer

223 views

### A question on permutations

Given integers $1$ through $n$, let $S$ be set of ordering of integers that respect even alternating or reverse alternating permutations (https://en.wikipedia.org/wiki/Alternating_permutation) up to ...

**2**

votes

**0**answers

80 views

### Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...

**0**

votes

**0**answers

84 views

### A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where $\beta\...