# Tagged Questions

**11**

votes

**0**answers

96 views

### On some special spanning trees of grid graphs

I would like to know if there are existing results on the following objects:
spanning trees of a grid graph, with no corridor
where a corridor is a vertex having exactly two neighbors, on ...

**1**

vote

**1**answer

138 views

### Probability of each edge in K-clique [closed]

For $c \in R$ and $k \in N$, $k \geq 3$ let
$p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$.
I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy ...

**0**

votes

**1**answer

76 views

### Using upper bound information in graph search

I am using A* (A-Star) to search a graph. A* algorithm takes advantage of the information $h(x)$, which is a lower bound of the distance between a vertex $x$ and the destination vertex.
In other ...

**4**

votes

**1**answer

271 views

### The formula for a perhaps basic identity (move from stackexchange)

The following question is moved from math stackexchange. It seems that this is not a popular question, but I really want to know the answer so I moved it to here. The question reads as follows.
We ...

**1**

vote

**0**answers

123 views

### Simultaneous vanishing of convolutions of Mertens function with itself

By Landau's theorem on Dirichlet series, we know that all the step functions ($k\geq 1$)
$$M_k(x)=\frac{1}{2\pi i}\int^{2+i\infty}_{2-i\infty}\frac{x^sds}{\zeta^k(s)s}=\sum_{n\leq ...

**7**

votes

**5**answers

452 views

### Bound on sum of complex summands involving binomial coefficients

I am trying to find the asymptotic behavior of the sum:
$$ \sum^n_{i=0} \begin{pmatrix} 2n \\ i \end{pmatrix} x^i y^{2n-i}$$
as $n\rightarrow\infty$. Here $x$, $y$ are complex numbers and I have ...

**5**

votes

**0**answers

158 views

### The sum of all the elements of every non empty subset of $A$ is not a multiple of $n$

Let $N=\{1,2,\ldots ,n\},n>1$. We wish to construct a set $A\subseteq N$ with the property:
The sum of all the elements of every non empty subset of $A$ is not a
multiple of $n$.
...

**1**

vote

**1**answer

208 views

### Probability of connected graph on torus

Let $G = (V, E)$ be a graph on n vertices constructed in the following way:
Each vertex $v \in V$ is positioned uniform randomly in $[0, 1] × [0, 1]$.
Connect two vertices $u, v \in V$ if $d(v,u) ≤ ...

**1**

vote

**0**answers

50 views

### clustering in a graph on boolean functions

Fix some n and k. Consider the following directed graph: vertices are all functions $2^n\rightarrow 2^n$ and a vertex f has an edge to a vertex g for every h such that $f=h\circ g$ and h depends only ...

**5**

votes

**2**answers

138 views

### Positivity of Ehrhart polynomial coefficients

Are there any results stating that a given family of convex polytopes have Ehrhart polynomials with non-negative coefficients?
What methods are available for proving such a property for some family ...

**0**

votes

**0**answers

139 views

### Problem regarding orthogonal vectors

Suppose $C_{1},C_{2},...,C_{n}$ are $0-1$ vectors of length $m$. Given $C_{i} \in \{0,1\}^{m}$ with $C_{i}=x_{i1}x_{i2}...x_{im}$ we say $C_{i}'=x_{i1}'x_{i2}'...x_{im}'$ is a subvector of $C_{i}'$ if ...

**3**

votes

**2**answers

262 views

### Graph game minimum vertex degree

Consider the following graph game, given a graph $G=(V,E)$ on $n$ vertices with minimum degree $ >> log(n)$. Players are BR and MA (BR moves first):
BR claims an unclaimed edge from $E$, adds ...

**2**

votes

**1**answer

195 views

### Solving assignment problem using Hungarian method vs min cost max flow problem

The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method.
However, it can also be reduced to a min cost max flow ...

**3**

votes

**2**answers

105 views

### Number of monomials of deg D where each variables has low degree

Let $D,n,d$ be three positive integers.
I am looking for the number of monomials of degree $D$ in $n$ variables where each variable appears with exponent at most $d$.
As a result of an application ...

**3**

votes

**1**answer

148 views

### Polygamous stable marriage/ assignment problem

I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...

**2**

votes

**2**answers

237 views

### System of boolean equations, Satisfiability

Are there any methods to "solve" large systems of boolean equations?
$$x_{i1}\vee x_{i2}\vee x_{i3} = b_i, \quad\text{for}\quad i=1,\dots,N,$$
where $x_i, b_i \in\{0, 1\}$
For example
$$x_{1}\vee ...

**4**

votes

**0**answers

177 views

### Navigation in a graph

The problem
Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$.
Assumptions about the graph: You may ...

**12**

votes

**2**answers

444 views

### Who first noticed that Stirling numbers of the second kind count partitions?

When the Stirling numbers of the second kind were introduced by James Stirling in 1730, it was not combinatorially; rather, the numbers ${n \brace k}$ were defined via the polynomial identity
$$
x^n = ...

**11**

votes

**0**answers

152 views

### When is a group Fibonacci sequence contained in a single conjugacy class?

First a definition: a Fibonacci sequence in a group is a sequence in which the first two elements may be arbitrary, and from there on each element is a product (using the group operation) of the ...

**6**

votes

**1**answer

139 views

### Lattice model for Affine Grassmannians of non type A

There is a Lattice model for affine Grassmannians of type A, due to Lusztig. It describes affine Grassmannians of type A as the moduli space of certain subspaces in an infinite-dimensional ...

**4**

votes

**1**answer

277 views

### How to visualise Bollobas' 1965 theorem?

Theorem
$[n]=\{1,\ldots,n\}$. Let $\lbrace (R_i, S_i), i \in I \rbrace, R_i, S_i \subset [n]$ be such that $R_i \cap S_i = \emptyset, R_i \cap S_j \ne \emptyset (i \ne j)$. Then $$\sum_{i \in I} ...

**1**

vote

**1**answer

68 views

### Computing row-sum scaled unsigned Stirling nos. of the 1st kind

As the title suggests, I would like to compute probability vectors with elements proportional to (unsigned) Stirling numbers of the first kind by row. For easy reference, here is the Wiki page.
For ...

**2**

votes

**3**answers

323 views

### Probability that a sum of intependent random variables hits a point

Let $X_1,\ldots,X_n$ be independent random elements of a normed space $X$. Suppose that $\sup_{x\in X}\mathbb{P}(X_i=x)=p_i$. What is the best known upper bound for
$$\sup_{x\in X} ...

**7**

votes

**2**answers

187 views

### Are sums of 0-1 Pareto efficient vectors Pareto efficient?

Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that:
The entries of $A$ are $\in \{0, 1\}$.
For all pairs of columns $u, v$ of $A$ the entries of $u - ...

**3**

votes

**0**answers

168 views

### What is God's number for the WrapSlide puzzle?

WrapSlide is a slide-puzzle (reminding of Rubik's Cube) consisting of a 6x6 grid of coloured tiles which are separated into four quadrants of 3x3 tiles. When it is unmixed all the tiles in a quadrant ...

**3**

votes

**1**answer

132 views

### When are all sums of the elements of a set different?

Consider a set $S = \{x_1, \dots, x_n\} \subset \mathbb{Q}\setminus\{0\}$ and assume that for any $I, J \subset [n]$ with $I \neq J$ we have that
\begin{equation}
\sum_{i \in I} x_i \neq \sum_{j \in ...

**3**

votes

**2**answers

205 views

### A problem on chains of squares — can one find an easy combinatorial proof?

Consider the unit square $ S = [0,1] \times [0,1] $. For each $ n \in \mathbb{N} $, we can tessellate $ S $ by the collection
$$
A
= \left\{
\left[ \frac{i}{n},\frac{i + 1}{n} \right] \times
...

**2**

votes

**0**answers

61 views

### Number of maximal chains in Bruhat order

Is there a formula for the number of maximal chains between two permutation in the (strong) Bruhat order?

**3**

votes

**1**answer

167 views

### A number array related to colored necklaces and the primes

I stumbled upon entry OEIS-A208535 on the enumeration of certain kinds of colored necklaces and noticed that the integers for the odd prime rows of the table there seem to be given by the Moreau ...

**6**

votes

**0**answers

107 views

### What is known about the chromatic number for minimum-distance graphs in higher dimensions?

For a set of points in $\mathbb{R}^d$ with minimum distance $a$, the minimum-distance graph connect two points iff they are at distance $a$. We can also view it as the tangency graph for a set of ...

**1**

vote

**0**answers

74 views

### Fundamental invariants for root subsystems

Let $\Phi$ be an irreducible root system of rank $\ell$. The fundamental invariants of $\Phi$ is a set of $\ell$ integers $d_1, \cdots, d_\ell$ canonically attached to $\Phi$.
Now suppose $\Psi$ is ...

**7**

votes

**0**answers

216 views

### On the ratio of Gilbreath sequences

Definitions: let $n \in \mathbb{N}_{>0} \cup \{ \infty \}$ and let $E_n$ be the set of sequences $(d_i)_{i=1}^n$ such that $d_1=1$, $d_i$ is an even integer (for $i > 1$) and $0<d_i \le i$. ...

**8**

votes

**3**answers

515 views

### Separating points in the plane II

Let A be a set of $2m$ points on the plane so that no open set of diameter $2$ has more than m of them. Define $A+A+...+A$ ($k$ times) to be the multiset of $k$-sums from $A$. That is, we consider all ...

**5**

votes

**1**answer

436 views

### Is fourier analysis necessary to prove this?

I have a couple of inequalities that I want to prove. The proof is easy using fourier analysis but I am wondering whether there is a proof that does not use fourier analysis.
1) For any $c, s > ...

**0**

votes

**1**answer

112 views

### Poisson approximation of random sub-graphs

I add the edges of $G(n)$ the complete graph on $n$ vertices one by one, at random and without replacement, and denote by $G(n,m)$ the resulting Erdos Renyi random graph process. At step $m$ in the ...

**1**

vote

**1**answer

157 views

### A generalisation of Narayana-like numbers (walks on the 2D lattice)

I apologize in advance if this question has a trivial answer. I am pretty sure this kind of problem was already studied and I am mostly asking for good references.
Given integers $0 < k \le n+1,$ ...

**1**

vote

**1**answer

117 views

### Ordinary or Rational Generating Function for Associated Stirling Numbers $b(n,k)$

I am trying to identify or find the ordinary or rational generating function (not the exponential generating function) for the Associated Stirling numbers of the Second kind, denoted ...

**14**

votes

**2**answers

298 views

### Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?

Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by ...

**3**

votes

**1**answer

68 views

### Are all marked order polytopes normal?

Richard Stanley showed that order polytopes have a unimodlar ttriangulation.
In particular, this implies that they are integrally closed/normal.
One can generalize order polytopes to marked order ...

**1**

vote

**1**answer

171 views

### Name for series $\sum f_n x^n / (n! (n+k)!)$

Let $(f_n)_{n\ge0}$ be a real sequence. Then $\sum f_n {x^n \over n!}$ is called the exponential generating function of $(f_n)$.
Let $k\ge0$ be a nonnegative integer. If we add another factorial ...

**13**

votes

**2**answers

372 views

### What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$

Every $f\colon\{-1,1\}^n\to \mathbb{R}$ can be repsenented as a multilinean polynomial of the form $$f(x_1,x_2,\ldots ,x_n)=\sum _{S\subseteq [n]} \hat{f}(S)\prod_{i\in S} x_i $$ The degree of the ...

**1**

vote

**0**answers

120 views

### current status of combinatorial optimization solvers [closed]

What is the current status of the solvers in combinatorial optimization? For example, what is the "usual feasible size" for a traveller sale's man problem, say, how many nodes and edges are "usually ...

**2**

votes

**2**answers

128 views

### Choosing subsets to cover larger sets

Consider the set $S=\{1,2,\ldots, n\}$, and let $a<b<n$. What is the minimum number $f(a,b)$ such that there exist $f(a,b)$ subsets of $S$ of size $a$ for which any subset of $S$ of size $b$ ...

**3**

votes

**1**answer

49 views

### Average vertex degree in finite Delaunay triangulations in high dimensions

In $\mathbb{R}^2$ it's known that with a "random" point configuration, the average degree of a vertex in its Delaunay triangulation is 6.
Does anyone know of a similar result in higher dimension? I ...

**2**

votes

**2**answers

89 views

### Probability of a contiguous sub-sequence with different elements

Let $a$ and $b$ be two positive integers, and say $b\gg a$. Let $S$ be a random sequence with $ab$ elements, whose entries are all integers from $1$ to $a$, such that each number from $1$ to $a$ ...

**8**

votes

**1**answer

327 views

### Coloring of the plane

I would like to know the minimum number k such that the plane R^2 can be coloured with k colors such that no colour contain all the possible distances. In other words, a colouring such that each color ...

**6**

votes

**1**answer

183 views

### Some polytopes in $\mathbb R^n$ whose vertices have coordinates 1, -1 or 0

Let $n$ and $k$ be positive integers with $k\leq n$.
Let $P(n,k)$ be the convex hull in $\mathbb R^n$ of the $2^k {n \choose k}$ vectors whose exactly $k$ coordinates belong to $\{\pm 1\}$ all the ...

**1**

vote

**1**answer

94 views

### Evaluation of the multiple integral [closed]

Would you give me any suggestions or comments on evaluating the following $n$-dimensional
integral? $$ \int_{[0,t]^n} h(x) dx $$
where
$ x=(x_1 ,x_2 , \cdots, x_n ), h(x)= \prod_{k=1}^n min( ...

**2**

votes

**0**answers

50 views

### Computing basis of a lower set given basis of complementary upper set

In a poset $P$, $U\subseteq P$ is an upper set when for all $x\in U$, we have $y\ge x$ implies $y\in U$. Any subset of $P$ generates an upper set, and the basis of an upper set $U$ is the smallest ...

**2**

votes

**0**answers

87 views

### Counting strings with alternating letters with generating functions

It is a classical problem that of finding the generating function (GF) of the number of strings with length $n$ having $m$ different letters (basically, the problem reduces to that of writing the ...