# Tagged Questions

**2**

votes

**0**answers

120 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

270 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

941 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

182 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

125 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

390 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

119 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

205 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

101 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

79 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

158 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

214 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

128 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

96 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

71 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

37 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

94 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

96 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

259 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

146 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

202 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

169 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

376 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

96 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

142 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

189 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

230 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

188 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

112 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

103 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

139 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

80 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

274 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

126 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

459 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

162 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

52 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

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

**3**

votes

**2**answers

271 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

246 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

108 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

160 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

243 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

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

**13**

votes

**2**answers

470 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

155 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

154 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

284 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} ...