# Tagged Questions

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

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

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

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

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 ...
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})$ ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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$ ...
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\...