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

learn more… | top users | synonyms

0
votes
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
2answers
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
2answers
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
2answers
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
2answers
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
2answers
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
0answers
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
0answers
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
2answers
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
2answers
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
2answers
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
3answers
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
1answer
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
1answer
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
1answer
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
0answers
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
3answers
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
0answers
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
0answers
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
1answer
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
0answers
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
5answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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\...