# Tagged Questions

**0**

votes

**0**answers

67 views

### Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by
$$\frac{k}{2n-k}{2n-k \choose n}.$$
The number of Dyck paths from the ...

**1**

vote

**0**answers

54 views

### Max flow with minimal requirements algo problem

While applying the algorithm to solve the max flow of the network with minimal requirements on edges, I have encountered a problem.
The algorithm states:
For graph G
create an edge from target to ...

**7**

votes

**3**answers

403 views

### Inclusion-preserving bijection between subsets of cardinality k and n-k

Let $n$ be a positive integer. A subset of $[n] := \{1,2,...,n\}$ having $k$ elements will be called a $k$-subset.
For $n,k \in \mathbb{N}$ with $k \leq \lfloor n/2 \rfloor$, it is clear that one can ...

**2**

votes

**1**answer

141 views

### A question about generalized Dyck words

I am interested in counting the following. How many words using $n-1$ copies of $u$ and ${n \choose 2} - n+1$ copies of $d$ begin with $uu$ and, in general, the $k^{th}$ $u$ is among the first ${k ...

**-1**

votes

**0**answers

79 views

### Estimating the moments of a random variable

Suppose i wanted to estimate the expectation and variance of a random variable $X$. More over suppose i could write a variable $X$ as a sum of indicator random variables $X=\sum_{i=1}^{k} X_{i}$. Are ...

**9**

votes

**1**answer

307 views

### Could there be an exact formula for the Ramsey numbers?

Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$.
Is it possible that there ...

**0**

votes

**0**answers

74 views

### Asymptotic analysis of a sum of complex summands using integral

I'm trying to find the exact asymptotics of a sum:
$$A = \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, $|x|\leq1, ...

**37**

votes

**4**answers

3k views

### A game of stones

How I arrived at this question is a rather long story having to do with the honors calculus class I am teaching. At this point it's sheer curiosity on my part. Here is the game.
...

**2**

votes

**1**answer

188 views

### Counting Ribbon graphs

Let $G$ be a ribbon graph (sometimes called fat graph) with $v$ vertices and $e$ edges. Furthermore each vertex is of degree $d$.
Q) What is the number of $G$ with the above properties? I mean does ...

**14**

votes

**1**answer

557 views

### Is it possible to define higher cardinal arithmetics

In number theory there are several operators like addition, multiplication and exponentiation defined from $\omega\times\omega$ to $\omega$. Each of them is defined as an ...

**3**

votes

**1**answer

160 views

### Determinant of the oriented adjacency matrix of a tree

Let $(V,E)$ be a finite oriented directed graph, with vertices and edges ordered, and $M$ the $|V|\times |E|$ matrix with entries
$$ m_{ve} = \begin{cases} 1 &\text{if $e$ points at $v$}\\
-1 ...

**2**

votes

**1**answer

178 views

### Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...

**2**

votes

**3**answers

565 views

### Koebe–Andreev–Thurston theorem - where can I find a proof?

Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...

**13**

votes

**3**answers

606 views

### Conjecture regarding closest point inside a discrete ball to a line

I'm a PhD student in image processing, where I've stumbled into a problem that seems to be essentially number theory. I've hunted around online and while I've found many results on similar problems, ...

**2**

votes

**1**answer

128 views

### A perfect $(n,k)$ shuffle function

Suppose you have a deck of $n$ cards; e.g., $n{=}12$:
$$
(1,2,3,4,5,6,7,8,9,10,11,12) \;.
$$
Cut the deck into $k$ equal-sized pieces, where $k|n$;
e.g., for $k{=}4$, the $12$ cards are partitioned ...

**3**

votes

**0**answers

84 views

### Partitions with each part dividing the original number

I have a question on partitions that I have not seen being discussed. It deals with those related to divisors.
My definition of partitions I am working with is as follow: a sequence of weakly ...

**4**

votes

**0**answers

114 views

### Reduction argument from a general vertex set V(G) to a prime power in Prof. Keevash's proof on the Existence of Designs

The proof flow of the paper "On the Existence of Designs" by Prof. Keevash as I understand it is the following:
-- Reduction from the general case to $V = \mathbb{F}_{p^a}$ (Lemma 6.3)
-- Covering ...

**0**

votes

**1**answer

42 views

### Minimal hypergraphs with respect to separation

Let $H = (V, E)$ be a hypergraph, that is $V$ is a set and $E \subseteq \mathcal{P}(V)$. We say that $H$ is $T_1$ if for $v\neq w$ there are $e_v, e_w \in E$ such that $v\in e_v, w\notin e_v, w\in ...

**0**

votes

**0**answers

101 views

### A question about the duality principle

Suppose $X$ and $Y$ are finite sets and $K:X\times Y\to \mathbb R$ is some function. We get an integral transform from the space of real functions on $X$ to real functions on $Y$ given by ...

**1**

vote

**0**answers

75 views

### combinatorial rectangles

Consider the set $S$ of all $m\times m$ matrices with $0-1$ entries with exactly $T$ combinatorial rectangles of all $0$s or all $1$s that partition each matrix in a non-overlapping manner.
Is there ...

**9**

votes

**2**answers

265 views

### Is there any relationship between the topologies of the clique complex and the independence complex?

Let $G$ be a simple graph on a finite vertex set. The clique complex $X(G)$ is the simplicial complex whose faces are complete subgraphs of $G$, and the independence complex $I(G)$ is the simplicial ...

**27**

votes

**2**answers

912 views

### “Nyldon words”: understanding a class of words factorizing the free monoid increasingly

BACKGROUND.
Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor ...

**5**

votes

**2**answers

176 views

### Decomposing polyhedral cones into “direct sums” and a polynomial

This question consists of two parts. I'm not breaking it up into two separate ones because posing the second question would essentially require me two rewrite the first one. Also, to some extent, the ...

**1**

vote

**1**answer

122 views

### NP hard problems on UD graphs

I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard.
...

**8**

votes

**2**answers

375 views

### Infected square

I saw the following problem in Mathematical Puzzles from Peter Winkler (very good book, by the way): imagine you infect k cases of a chessboard nxn and the infection spreads to a case if it has at ...

**10**

votes

**0**answers

117 views

### Polytopes with few vertices and few facets

I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that ...

**6**

votes

**1**answer

194 views

### Origin of the numbers game

The numbers game is a (one-player) game played on a finite graph with an initial assignment of numbers to its vertices, studied by Alon, Bj\"orner, Brenti, Donnelly, Eriksson, Krasikov, Mozes, Peres, ...

**1**

vote

**1**answer

81 views

### Regular unimodular triangulation for a certain simplex

Consider an $n$-simplex with vertices given by
$(0,0,\dots,r_i,r_{i+1},\dots,r_n)$ where $r_1,\dots,r_n$ are given natural numbers,
and $i=0,1,\dots,n+1$.
Does this simplex admit a regular, ...

**3**

votes

**1**answer

76 views

### Stable equilibria of points on the 2-sphere

Suppose $n$ points lie on the sphere $S^2=\{x\in\mathbb{R}^3\mid \|x\|=1\}$ and are subjected to a repulsive acceleration that pushes away a point from each other point with an intensity proportional ...

**13**

votes

**9**answers

1k views

### Combinatorial Databases

At one point, I remember being excited by seeing the website Encyclopedia of Combinatorial Structures as an extension of Sloane's Online Integer Sequence Database site. Unfortunately, the site (ECS) ...

**9**

votes

**0**answers

150 views

### Maximum number of vectors in a hypercube satisfying given conditions

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean ...

**0**

votes

**0**answers

206 views

### A hard combinatorial identity

I asked this questions on the http://math.stackexchange.com/questions/1016713/ But I don't get answer.
I try to prove the following hypothesis
$$\sum_{i=0}^{min\{k, n-1\}}(-1)^i { n+i-1 \choose ...

**6**

votes

**0**answers

125 views

### Does the weak Hadwiger conjecture imply the Hadwiger conjecture?

For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements:
(H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$.
...

**0**

votes

**0**answers

91 views

### Proof of Faà di Bruno's formula with convolution identity

Faa di bruno's formula can be expressed as follows
$$
\frac{d^n}{dx^n}[f(g(x))] = \sum_{k=1}^{n}f^{(k)}(g(x)) B_{n,k}(g'(x),....,g^{(n-k+1)}(x))
$$
On this Wikipedia page, there is a convolution ...

**-1**

votes

**1**answer

68 views

### Combinatorial Interpretation of Generalized Stirling numbers

I know the combinatorial interpretation of first, and second order Stirling numbers (#of k cycles of n items, and #of partitions n items into k subsets). Is there an interpretation for the generalized ...

**1**

vote

**0**answers

34 views

### Distributing partially known data between n parties

Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ ...

**2**

votes

**1**answer

93 views

### irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...

**0**

votes

**0**answers

94 views

### Best possible concentration inequality in high dimensions

Let $X_1,\ldots,X_n$ be independent random variables in $\mathbb{R}^d$ with $EX_i=0$ and $||X_i||_{2}\leq 1$. What is the best known exponential upper bound for
$$P(||X_1+\cdots+X_n||_{2}>x)?$$
In ...

**12**

votes

**1**answer

251 views

### Coloring the edges of a torus graph

Question:Consider the $2k \times 2k$ grid graph on a torus. Is it true that for every $2$-coloring of the edges, there is an antipodal pair of vertices connected by a path that changes colors at most ...

**2**

votes

**1**answer

131 views

### A property of monomials in a Schubert polynomial

I came across a property of monomials in a Schubert polynomial in Lascoux's book:
http://www-igm.univ-mlv.fr/~al/ARTICLES/CoursYGKM.pdf
page 62, footnote 4. The property is as follows.
Let us ...

**12**

votes

**1**answer

195 views

### Number of orders of $k$-sums of $n$-numbers

Suppose we have a $n$-element set $S$. Denote the set of its $k$-element subsets by $K$ ($|K|=\binom{n}{k}$).
If the elements of $S$ are real numbers then to each $k$-element subset we can associate ...

**2**

votes

**1**answer

165 views

### Random walks with exponential decreasing steps

Let $g$ be the golden number (or another algebraic integer in $(0,1)$ that fullfills an equation with coefficients $\pm 1$). Consider the random walk on $\mathbb{R}$ starting with $0$ and walking ...

**10**

votes

**2**answers

372 views

### Number of paths through infinite trees with given “growth rates”

(Preface: This may be a naive or easy question for experts....)
Consider an infinite tree, rooted on the left, where each node has two children; the number of nodes at each level (distance from the ...

**0**

votes

**1**answer

93 views

### All $2$-designs arising from the action of the affine linear group on the field of prime order

Let $p$ be a prime and $\mathbb{Z}_p$ denote as usual the field of order $p$. Let $AL(p)$ be the affine linear group $\{x\mapsto ax+b \;|\; a\in \mathbb{Z}_p\setminus \{0\}, b\in\mathbb{Z}_p\}$. For a ...

**5**

votes

**1**answer

140 views

### Combinatorial proof of the Cauchy identity for double Schubert polynomials

The Cauchy identity for double Schubert polynomials states
$$ \mathfrak{S}_w(x;-y) = \sum_{\substack{u,v \in S_n \\ w=v^{-1}u \\ l(w) = l(v) + l(u)}} \mathfrak{S}_u(x)\mathfrak{S}_v(y).$$
Is there a ...

**2**

votes

**0**answers

186 views

### Minimizing $\{0,1\}$-sequence permutations

Explanation: For a given bit sequence $f$, reposition the bits as to minimize $G$ which can be thought of as a measure of how poorly proportional $f$ is to each of its subsequences.
Let $p \in ...

**6**

votes

**2**answers

226 views

### Counting valid coordinates

We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in ...

**5**

votes

**1**answer

180 views

### Bijective proof of an Abel-Hurwitz-type identity

Can anyone sketch for me a bijective proof of the fact that the number of spanning trees of the complete graph on $n$ vertices, $K_n$ (given by the formula $ t_n = n^{n-2}$), satisfies $ t_n = ...

**2**

votes

**1**answer

108 views

### Maximum number of hyperedges on a hypergraph without a spanning tree

Although every connected graph has a spanning tree, the same is not true for hypergraphs: consider the hypergraph on 4 vertices with all possible edges of size 3. You need to pick at least two edges ...

**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 ...