**7**

votes

**1**answer

126 views

### Factoring a multiset into a product of two multisets

Given a multiset $S$ of $mn$ numbers, how hard is to find multisets $A$ and $B$, of $m$ and $n$ numbers respectively, such that
$$ S = \{ xy \mid x\in A, y\in B \}~~~~\text{(multiset sense)}, $$
or ...

**10**

votes

**2**answers

600 views

### What is the probability that two random permutations have the same order?

I am interested in the orders of random permutations. Since the law of the logarithm of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), ...

**0**

votes

**0**answers

12 views

### Approximation preserving reductions

I've seen in the following document
https://hal.archives-ouvertes.fr/hal-00958028/document
A definition of the $\leq_{S}$ reduction defined specifically for minimisation problems at the bottom of ...

**0**

votes

**0**answers

52 views

### Question on abstract polytopes

Let $(P,\le)$ be an abstract $n$-polytope, with $n\ge 2$. Let $H,H',K$ be $m$-faces, with $0\le m \le n-2$. Is it true that there is a sequence $\{H_0=H,H_1,...,H_{r-1},H_r=H' \} \subseteq P$ so that ...

**2**

votes

**1**answer

79 views

### Orthogonal embeddings and edge lengths

I'm interested in orthogonal embeddings of graphs into the 2-dimensional, i.e where vertices are placed at integer co-ordinates and edges are routed along the grid lines and are not allowed to ...

**1**

vote

**0**answers

23 views

### Some confusion regarding the definition of NPO reduction

I've seen the following definition in a paper on approximation preserving reductions.
Definition:Let $\pi_{1}$ and $\pi_{2}$ be two NPO maximization problems. Then we say that $\pi_{1} \leq_{R} ...

**1**

vote

**1**answer

94 views

### Determinant of discrete Laplacian

It can easy be shown by induction that the determinant of the $(N-1)\times (N-1)$ matrix
$$\begin{pmatrix}
2 & -1 & & \\
-1 & 2 & \ddots & \\
& ...

**5**

votes

**3**answers

317 views

### Fundamental solution of Discrete Laplace in the plane

We consider a discretization of the Laplace operator on $\mathbb Z^2$, https://en.wikipedia.org/wiki/Discrete_Laplace_operator
Then, it is natural to consider its fundamental solution $u$, i.e. ...

**13**

votes

**7**answers

2k views

### Special arithmetic progressions involving perfect squares

Prove that there are infinitely many positive integers $a$, $b$, $c$ that are consecutive terms of an arithmetic progression and also satisfy the condition that $ab+1$, $bc+1$, $ca+1$ are all perfect ...

**1**

vote

**0**answers

54 views

### Building an orthogonal embedding for a 4-planar graph

I'm interested in the following paper http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In particular i'm interested in the construction Valiant describes to prove that it is possible to ...

**0**

votes

**0**answers

8 views

### Maximization the difference of a monotone submodular function and a linear function with a cardinality constraint

Maximizing a monotone submodular function with a cardinality constraint can be solved by using a simple greedy heuristic. However, if the submodular function is non-monotone, the greedy heuristic can ...

**7**

votes

**1**answer

238 views

### Recursive sequence of binomial random variables

Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and
$$X_{k+1} = X_k + \text{Bin}(X_k,p).$$
Thus, $\mathbf E [ X_k ] = (1+p)^k$.
I would like a left tail bound. Perhaps, ...

**11**

votes

**7**answers

675 views

### Finite-space dynamical systems

This question is quite open-ended, but I will formulate several sub-questions that I'll try to make precise. It is about finite-state dynamical system: start with a finite set $X$, with say $n$ ...

**2**

votes

**2**answers

335 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**2**

votes

**1**answer

137 views

### Alternating sign binomial identity [closed]

I recently noticed that for a triple of integers $k \geq 2$, $k \geq m \geq t \geq 1$, the following identity seems to hold
$\sum_{j=0}^{m-t} (-1)^{m-t-j}{k \choose j}{m-1-j \choose t-1}={k-t \choose ...

**5**

votes

**4**answers

193 views

### Selecting subsets with size $\frac{n}{2}$ covering every pair of the elements

Given a set $S$ of $n$ elements. Let $T$ be the set of all subsets of $S$, with size $\frac{n}{2}$ ($n$ is even). We want to select a subset $T'$ of $T$, with the property that for any pair of the ...

**4**

votes

**1**answer

264 views

### Number of different positions of rooks on chessboard

I know that this topic as been mentioned before, but no accurate answer has been provided.
Suppose we have to place $n$ rooks on $n \times n$ chessboard so that no one attacks another. How to count ...

**2**

votes

**3**answers

296 views

### An identity involving a product of two binomial coefficients

I'm trying to find a closed formula (in the parameters $q,N$) for the following sum:
$$ \sum_{k=q}^{N} {{k-1}\choose{q-1}} {{k}\choose {q}} $$
Can anybody give me a lead?
Lior

**5**

votes

**1**answer

155 views

### Intersection of rotating regular polygons

This question has a recreational flavor, but may not be
entirely uninteresting.
Let $P_k$ be a unit-radius regular polygon of $k$ sides,
and $P_n$ a unit-radius regular polygon of $n \ge k$ sides.
...

**0**

votes

**0**answers

36 views

### On the stability analysis of a discrete difference system with multiplicative noise

If we assume that
\begin{equation*}
\rho \{\phi \otimes \phi+\psi \otimes \psi\}<1,
\end{equation*}
where $\rho$ denotes the spectral radius, then can we verify that the following inequality ...

**1**

vote

**1**answer

72 views

### Discrete summation of Gaussian functions. Decay time problem

I am facing the following problem. I have a function which is defined through a discrete sum of Gaussians
$$F_M(t) = 2\sum\limits_{n=1}^{M}e^{-t^2 \sigma^2 n^2}\times \sum\limits_{k=n}^{M}p_k p_{k-n} ...

**0**

votes

**0**answers

56 views

### Factorial Sums over Compositions or ``Unlabeled Permutations"

Let $C_n$ denote subset of integer compositions of $n$ and $c=(c_1,c_2,\dots c_n)$
In a divergent sum, the sequence
$$
a_n=\sum_{c\in C_n} \prod_{c_i\in c} c_i!
$$
frequently shows up and one ...

**6**

votes

**1**answer

452 views

### Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$
such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...

**2**

votes

**1**answer

627 views

### Probability generating function zero implies random variable is infinite

Let $V$ be a random variable supported on the nonnegative integers (including $\infty$) and $f(x) = \mathbf E x^V$ be the probability generating function. In our model $V$ is the number of visits to ...

**3**

votes

**0**answers

117 views

### Generating function of a sequence involving reciprocals of binomial coefficients

Question: Is there a closed-form expression for the following sum
$$
F(z,k,r)=\sum_{n=0}^{r} \frac{z^n}{{n+k} \choose {k}}\label{sum}\tag{1}
$$
where $z\in\mathbb{C}$, and $r$, $k$ are non-negative ...

**0**

votes

**0**answers

75 views

### Summing up costs over a Markov chain

I apologize in advance if this question is too simplistic to be appropriate for MathOverflow. I have inquired in multiple places but have found little to indicate that this is a previously studied ...

**6**

votes

**1**answer

88 views

### Above/below directed graph on cells of arrangement of lines

This question concerns the structure of a directed graph
built on the cells of an arrangement of lines.
My basic question is whether this graph has been
studied before, perhaps in another guise. I ...

**1**

vote

**0**answers

38 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

**0**answers

61 views

### What is the maximal number of partitions with this maximal intersection property?

Let $X = \{ 1, \dots, n = sk \}$ be a finite set. Let $\mathscr P, \mathscr Q$ be equi-partitions of $X$ into $k$ sets of size $s$. Denote by $V(\mathscr P, \mathscr Q)$ the maximum size of ...

**3**

votes

**3**answers

136 views

### Simplifying a Taylor polynomial that involves Stirling numbers of the second kind

I am currently trying to evaluate a complicated function $f$ at a point $x+a$ using a high order Taylor polynomial about the point $a$. The polynomial has the standard form:
$$\sum_{n=1}^k ...

**8**

votes

**2**answers

194 views

### Repeats of all binary strings of length k

The question seems like it should be known, but I was not able to find it anywhere.
How many binary strings of length $n$ are required so that for every $k$ positions in these strings, all $2^k$ ...

**10**

votes

**1**answer

241 views

### Finding combinatorial models / statistics

In many cases in combinatorics and especially algebraic combinatorics with some representation theory, the main problem is about finding the correct statistic on a mathematical object.
For example, ...

**7**

votes

**1**answer

847 views

### Integer solution to special system of linear equations

This problem appear in my research, but I am unable to solve it.
There should be an easy argument, but I have not yet found it.
Informal version
An integer $k\geq 2$ is fixed.
We are given a matrix ...

**2**

votes

**0**answers

95 views

### What kinds of complexes can be collapsed to?

A simplicial complex $S$ is collapsible if there is a sequence of elementary collapses that bring $S$ down to a single point; I'll denote this as $S \searrow \{pt\}$. I am wondering about a similar ...

**9**

votes

**1**answer

434 views

### Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)

The parameters of the problem are $m$ numbers which are integers (these numbers are denoted $b_i$), $n$ urns and in each urn, we can place $C$ numbers. We assume $nC \geq m$ so that the problem is ...

**5**

votes

**0**answers

85 views

### Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...

**0**

votes

**1**answer

150 views

### Decomposition of a regular graph and connected subgraphs

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...

**2**

votes

**1**answer

168 views

### Gradient of Probability Distribution

Given a random walk on a lattice $L$ (not necessarily centered - we allow $E[X_i] \neq 0$ for the i.i.d. increments $X_i$), let $p_t(x)$ denote the probability measure of state $x \in L$ after $t$ ...

**5**

votes

**1**answer

155 views

### Modification of matching

Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...

**19**

votes

**2**answers

667 views

### Generating random finite groups

I would like a method to efficiently generate a random finite group of a given order $n$.
If there are $g(n)$ non-isomorphic groups of order $n$,
ideally each group would occur with probability ...

**3**

votes

**0**answers

102 views

### “Standard” notation for symmetric functions?

Here is what I encountered in the paper "The Optimal Lattice Quantizer in Three dimensions" by Barnes and Sloane.
Here is the setup:
Let $\Lambda$ be a lattice in $\mathbb{R}^3$. Around each ...

**4**

votes

**1**answer

136 views

### Do random triangulation edge-flips maintain randomness?

Let $S$ be a fixed set of $n$ points in the plane in general position.
Let $T$ be a triangulation
of $S$, (somehow) selected
uniformly at random from all triangulations of $S$.
(There are an ...

**3**

votes

**1**answer

71 views

### Choosing k pairs l distance apart from n numbers

I need to choose $k$ pairs of numbers out of first $n$ natural numbers such that the elements in each pair are $l$ distance apart. For example, if $n = 10, k = 3$ and $l = 2$, $\{(1,3),(4,6),(7,9)\}$ ...

**7**

votes

**3**answers

544 views

### Computing the lexicographic indices of integer partition

If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that ...

**-4**

votes

**1**answer

147 views

### What exactly is wrong with this statement (Lucas-Penrose fallacy)? [closed]

Statement
"For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method."
...

**11**

votes

**2**answers

332 views

### The most number of points that realize only $k$ distinct distances

For $k \ge 1$, let $f_d(k)$ be the largest possible number of points $p_i$
in $\mathbb{R}^d$ that determine at most $k$ distinct (Euclidean) distances,
$\|p_i-p_j\|$.
Example. For points in the plane ...

**13**

votes

**2**answers

581 views

### Bit String Bijection

I am searching for a bijection between two types of bit strings (strings of 0's and 1's) both of even length (2n).
The restriction on the first type of bit string is that they must have the same ...

**13**

votes

**1**answer

403 views

### Minimal “sumset basis” in the discrete linear space $\mathbb F_2^n$

For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$.
I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...

**1**

vote

**1**answer

157 views

### Enumerating Lattice points

Let $A \in \mathbb{R}^{d\times d}$ be an invertible matrix. Consider the set
$$P_d := A\mathbb{Z}^d = \{A x| x \in \mathbb{Z}^d \} \subset \mathbb{R}^d$$.
and
$$ Q_d := [-1,1]^d.$$
I am interest in ...

**1**

vote

**0**answers

67 views

### Presentation of the Rybnikov matroid

In this well celebrated work Gregory Rybnikov exhibit an example of two arrangements with the same underlying matroid, but with fundamental groups which are not isomorphic. This is a key ...