All Questions
17 questions
3
votes
0
answers
92
views
Realized graph of majority of permutations
This question was asked several months ago on Math.SE, but remains unsolved.
For any collection of permutations of $\{1,2,\dots,n\}$, we say that it realizes a directed multigraph with $1,2,\dots,n$ ...
- 277
5
votes
1
answer
213
views
Partition an $(2n+1)$-permutation into two parts in which there are no three consective elements in given sequences
Let $a_1a_2\ldots a_{2n+1}$ ($n\geq 2$) be a given permutation of the numbers from $1$ to $2n+1$ and let
$\alpha_i=\{i,i+1,i+2\},~1\leq i\leq 2n-1$
$\alpha_{2n}=\{2n,2n+1,1\}$
$\alpha_{2n+1}=\{2n+1,1,...
- 557
-1
votes
1
answer
127
views
A permutation and combination problem about the number of connections in a sequence of n numbers [closed]
There is a sequence of n numbers as 1,2,3,...,n
How many combinations of the connections between two numbers in the sequence without overlaping?
...
6
votes
1
answer
726
views
Combinatorics and symmetry in matrices under row and column swaps
Suppose we have a $m\times n$ matrix and a sequence of numbers with which to fill the matrix, $\{c_1,c_2 \dots c_k \}$. I like to think of the numbers as colors, hence the notation. How many unique ...
3
votes
2
answers
316
views
Relation graph isomorphism to discrete logarithm
$\DeclareMathOperator\ora{ora}$Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$
permutation matrix of multiplicative order $\rho$.
Let $X$ be positive integer and $B_0=P_0^X A_0 P_0^{-X}$.
Q1 ...
- 25.4k
3
votes
1
answer
161
views
Probability permutation in turned to cycle
Let $M$ be a $0/1$ square matrix having one $1$ per row and column (permutation matrix).
If you permute the columns and rows independently what is the probability resulting permutation matrix is a ...
- 13.9k
4
votes
1
answer
187
views
Number of permutations with combinatorial geometric constraints
We are given a $d$-dimensional hypercube $H$, where each vertex is labeled with an integer $\ell\in\{1, 2, \ldots, 2^d\}$. Let $L$ be this labelling.
Question: How many labelling permutations $L'$ of ...
- 1,677
5
votes
1
answer
258
views
A graph similar to the Bruhat graph, what is it called?
The weak Bruhat graph (or 1-skeleton of the permutohedron) $B_n$ can be constructed as follows:
the vertices of $B_n$ are the permutations of the tuple $(1,...,n)$, two are joined by an edge, if they ...
- 13.6k
4
votes
1
answer
190
views
Cliques in Cayley graph on $n$-cycles
Let $S\subset S_n$ be the set of all $n$-cycles. I want to know if the Cayley graph $(S_n,S)$ has large dense subgraphs. I'm expecting it to not have super-polynomial size and $1-o(1)$ dense subgraphs....
- 203
7
votes
1
answer
509
views
A permutation problem
Here I ask a question on permutations of $n$ distinct real numbers.
QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\...
- 15.6k
13
votes
1
answer
409
views
When is the union of a graph and a random permutation thereof connected?
First things first: in what follows, a "random permutation" of a set $\Omega$ with $n$ elements does not necessarily mean an element chosen uniformly at random from $\textrm{Sym}(\Omega)$. Rather, and ...
- 20.2k
4
votes
0
answers
207
views
Have wiring diagrams been generalized to arbitrary digraphs?
A "combinatorial wiring diagram" is a way to define a permutation by a drawing of a particular planar digraph. For example, this wiring diagram corresponds to the permutation $(3412)$:
In Coxeter ...
- 1,389
0
votes
0
answers
96
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\...
- 13.9k
28
votes
2
answers
1k
views
Is this graph polynomial known? Can it be efficiently computed?
I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...
- 281
0
votes
1
answer
185
views
What are the number of possible ways to build up a certain path?
What are the number of possible ways to build up a certain path?
I was working on a graph problem and was trying to find out in how many possible ways can you build/grow a given path. With building/...
12
votes
1
answer
766
views
Sliding blocks puzzle
Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square of $S$, 1 green, some red and the rest are blue, a move consists of ...
- 121
12
votes
4
answers
2k
views
Cyclic Permutations - but not what you think
This question is not about elements of $S_n$ that consist of a single $n$-cycle, though naturally it's related.
Instead, consider permutations modulo the action of $(123\ldots n)$. That is, we ...
- 367