# Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

7,206
questions

**2**

votes

**0**answers

75 views

### Anything similar to cone product formula (for convex polytopes)?

The convex polytope flag vector ring $\mathcal{R}$ satisfies the cone product formula
$$
C(U) C(V) = C(J(U, V)) + DUV
$$
where
$$
J(U, V) = U C(V) + C(U) V - e_1 UV
$$
is the join formula.
Note: ...

**15**

votes

**3**answers

589 views

### When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?

Also posted on the Math Stackexchange: When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?
Introduction
Recently, a friend told me about the following ...

**6**

votes

**0**answers

170 views

### A class of symmetric functions

When attacking a symmetric problem via an asymmetric method, I encountered the following function: $$U_2(n, m) = \sum_{a = 0}^n\binom na (2^a + 2^{n - a})^m.$$
It is easy to see that this function is ...

**1**

vote

**0**answers

50 views

### total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...

**3**

votes

**2**answers

99 views

### NE-Lattice paths from $(0,0)$ to $(n,n)$ with $k$ peaks

Let $n$ and $k$ be natural numbers. I will consider North-East lattice paths (NE-paths) from $(0,0)$ to $(n,n)$ and encode these as strings of length $2n$ with letters $\mathsf{N}$ and $\mathsf{E}$. A ...

**0**

votes

**1**answer

57 views

### Complexity of edge coloring graphs with $\Delta(G) \ge n/3$ assuming the overfull conjecture

Closely related to this on cstheory.
Let $G$ be graph of order $n$ with $\Delta(G) \ge n/3$.
Assume the overfull conjecture.
Can we edge color $G$ with minimal number of colors in polynomial time?
...

**1**

vote

**1**answer

188 views

### Integral zeros of a multivariate polynomial

Consider the multivariate polynomial
$$f(x_1,\ldots,x_m)=mk\sum_{i=1}^mx_i^2-mk(k-1)\sum_{i=1}^mx_i-\left(\sum_{i=1}^mx_i\right)^2,$$
for integers $m,k\ge2$. We are looking for integral zeros of $f$ ...

**1**

vote

**2**answers

234 views

### Is $ \{ \frac{1}{n} + \frac{1}{m} : n,m \in \mathbb{N} \}$ dense in some interval of $\mathbb{R}$? [closed]

Consider the set $\{\frac{1}{n} + \frac{1}{m}: n,m \in \mathbb{N} \}$. Is this set dense in some interval of $\mathbb{R}$?
More generally let $S_k= \{\sum_{i=1}^k \frac{1}{n_i}: n_i \in \mathbb{N} \} ...

**1**

vote

**2**answers

161 views

### Moments of a combinatorial ensemble of random variables

Suppose $X_1,\dots,X_n$ are jointly distributed random variables such that the random $n$-tuple $(X_1,\dots,X_n)$ is uniformly distributed on the set of $n$-tuples of nonnegative integers summing to $...

**2**

votes

**1**answer

108 views

### Minimum local permutation data needed to globally merge locally sorted sequences?

We have $k$ blocks of integer sequences $B_1,\dots,B_k$ where $B_i$ is a sequence $$a_{i,1},\dots,a_{i,n_i}$$ with $a_{i,j}\leq a_{i,j+1}$.
Denote the permutation matrix $M_{\ell,\ell'}$ that merges $...

**5**

votes

**1**answer

254 views

### Proofs of Euler's characteristic formula for n-Dim polytopes

Twenty proofs of Euler's formula V - E + F - 1 = 1, which applies to convex polyhedrons, i.e., 3-dimensional polytopes, are presented at the Geometry Junkyard.
I'm interested in proofs of the more ...

**2**

votes

**0**answers

52 views

### Reference on the faces of the circulation polytope

On page 4 of Generating all vertices of a polyhedron is hard it is mentioned that the facial structure of the circulation polytope* is well understood. I am trying to find a reference for this.
I ...

**1**

vote

**1**answer

132 views

### How many matrices $C \in \mathrm{M}_3(\mathbb{F}_q)$ such that $\det(C-A)=\det(C-B) = 1$?

I am studying the special unit-graph $G$ on $M_3(\mathbb{F}_q).$ Now, I want to estimates the upper bound for the second largest eigenvalue of adjacency matric of $G.$ One of questions that I need is ...

**2**

votes

**1**answer

82 views

### A question relating to certain algebraic manipulation of a formal power series written in the form of infinite product

Suppose there is formal power series in infinite product form as follows: $$\prod_{d\geq 1} \left(1+\frac{u^d}{q^d-1}\right)^{a_d}$$, where $a_d$ are positive integers. Consider the expression $$\...

**0**

votes

**0**answers

23 views

### Path covering of a graph, but without the edge-disjoint property

Can you work out the minimum number of paths required to cover the edges of a graph, where the paths start and finish at the same points (all start at $v$, all finish at $w$)?
See e.g. Covering the ...

**0**

votes

**0**answers

79 views

### The least common multiple of all degrees of a finite Coxeter group and indecomposable elements in the generalized cycle decomposition

This question is a follow-up of the previous question and especially the last comment therein.
Let $(W,S)$ be a finite Coxeter system with reflections $T$. Let $\ell_T$ be the reflection length. ...

**2**

votes

**0**answers

45 views

### A combinatorial question about encoding the subsets of logarithmic-bounded cardinality

Let $k \in \mathbb N - \{0\}$ and $f(n) = \binom n 0 + \binom n 1 + \dotsc + \binom n {\log^k n}$.
Our question is:
$f(n) = o(2^{\log^{k+1} \ (n)})$ or $f(n) = \Theta(2^{\log^{k+1} \ (n)})$, which ...

**3**

votes

**1**answer

170 views

### Minimal neighbor distance in permutations

For any positive integer $n$, let $[n]:=\{1,\ldots,n\}$. Let $S_n$ denote the set of permutations (bijections) $\pi:[n]\to [n]$. For any $n>1$ and $\pi\in S_n$ we let the minimal neighbor distance ...

**2**

votes

**2**answers

79 views

### Counting the number of grids with certain disallowed dominoes

I'm curious if there is a general strategy for solving the following kind of counting problem.
Fix a positive integer $n$, and let $[n] = \{1, \dots, n\}$.
Preliminaries
Definition An $n$-grid of ...

**0**

votes

**1**answer

94 views

### Representations of modular lattices, extension to cellular sheaves

There are various "representation theorems" for lattices such as Birkhoff's Representation Theorem that states that every finite distributive lattice is isomorphic to a quasi-sublattice of the lattice ...

**2**

votes

**0**answers

82 views

### Number of permutations with precedence constraints : DP case [closed]

I have two sets of balls (blacks and whites), each set is numbered from $1$ to $n$, and all are put in a jar. My precedence constraint is expressed as following : to pick a black ball with index $i$, ...

**4**

votes

**0**answers

213 views

### How many arrangements of $n$ points with $k$ edge lengths exist in $d$ dimensions?

[Asking on behalf of a high school mathematics course, but responses written at any level are welcome!]
I was recently reading over a nice puzzle called the four points, two distances problem:
...

**4**

votes

**1**answer

211 views

### Given a symmetric polynomial in F_q, write it in terms as elementary symmetric polynomials. How to find out the coefficient?

Consider the finite field $F_q$, where $q$ is a power of an odd prime and $N$ is a power of $q$. We have a homogeneous symmetric polynomial
$$
E_{l,s}(x) = \sum_{\substack{l_1+l_2+\cdots +l_s=l \\ l_i\...

**1**

vote

**1**answer

67 views

### Expected value of maximal distance between neighbors in permutations

For any positive integer $n$, let $[n]:=\{1,\ldots,n\}$. Let $S_n$ denote the set of permutations (bijections) $\pi:[n]\to [n]$. For any $n>1$ and $\pi\in S_n$ we let the maximal neighbor distance ...

**0**

votes

**0**answers

60 views

### On the coxeter polynomial of bicomplexes

Let $C_{n}$ be the category of bicomplexes supported in an $n \times n$-grid (over vector spaces) and $A_{n}$ the corresponding quiver algebra with this module category.
Let $\phi_{n}$ be the Coxeter ...

**6**

votes

**2**answers

162 views

### Lovasz local lemma for the edge model

In order to successfully apply the Lovasz local lemma, one needs the events to be relatively independent. This (sometimes) works well in the $G(n,p)$ model of random graphs, where the presence or ...

**2**

votes

**1**answer

200 views

### Converse of Sperner's lemma

The famous Sperner's lemma states that, if a labeling of a triangulation of a simplex satisfies certain conditions on the boundary, then there must exist a sub-simplex in which all labels are ...

**4**

votes

**2**answers

389 views

### Showing this formula counts these things

I'm writing an article, and I got stuck trying to prove that some numbers are positive. I have a relatively good intuition for guessing what an expression is counting, but in this case I'm not being ...

**0**

votes

**1**answer

140 views

### What are all the possibilities of $A$ s.t. $\det(A)=k$?

Suppose we have $A \in M_3(\Bbb N\cup\{0\})$ s.t. sum of the elements of each row is $k $ for some fixed $k\in \Bbb N\cup\{0\}$. What are all the possibilities of $A$ s.t. $\det(A)=k$?
We can start ...

**0**

votes

**3**answers

275 views

### Im looking for an algorithm that can solve or approximate the solution to a problem

Let me first explain the problem using an analogy.
Let's say you have $N$ doors and $M$ keys. Each door can be opened with a combination of keys, each combination is also unique (i.e. there aren't be ...

**1**

vote

**0**answers

48 views

### Large bounded degree expanders in the hypercube

Does the $n$ dimensional hypercube graph contain large bounded degree expanders as subgraphs? For example, of exponential size in $n$?
If not, one could relax the problem and allow the maximum ...

**3**

votes

**1**answer

168 views

### Concentration of monochromatic edges in a graph

Let $G$ be a graph of order $n$ with $m$ edges. Color each vertices uniformly at random with $q$ colors. It is easy to see that expected number of monochromatic edges (edge whose end vertices are of ...

**1**

vote

**0**answers

48 views

### Prove duality of multiple zeta values by Extended Double Shuffle Relations

It is easy to prove the duality theorem of multiple zeta values (MZVs) by the integral representation of MZVs. However, how does one prove MZV's duality theorem solely by Finite Double Shuffle ...

**5**

votes

**4**answers

353 views

### Number of tree walks of bounded degree

Define a tree walk to be a walk $w$ on some tree starting and ending at the origin. Its support $\text{supp}(w)$ is the subtree consisting of the vertices and edges it traverses. Define the maximal ...

**0**

votes

**0**answers

62 views

### A variant of weighted set cover problem

I came across a paper that proves a generalized version of the weighted set cover problem is NP-complete.
The problem is stated as follows: Given a collection of $n$ elements, a collection of ...

**5**

votes

**1**answer

203 views

### Combinatorial Skeleton of a Riemannian manifold

In Chung and Yau's paper: "A combinatorial trace formula" (MSN), they proved
a combinatorial version of Selberg's trace formula for lattice graphs.
I learned also in the setup that it makes sense to ...

**5**

votes

**2**answers

824 views

### Proof that $3^ns + \sum_{k=0}^{n-1} 3^{n-k-1}2^{a_k}=2^m.$

How would I go about proving the following:
For any odd positive integer $s$, there exists a sequence of nonnegative integers $( a_0, a_1, \cdots, a_{n-1})$ and a nonnegative integer $m$ such that,
$...

**4**

votes

**0**answers

199 views

### Positivity of a finite sum involving Stirling numbers of the first kind

Past days I've been trying to prove that certain polynomials have positive coefficients. After a lot of thinking, I came up with a formula for each coefficient individually, and they are not that ugly....

**2**

votes

**2**answers

489 views

### An infinite version of the Dilworth theorem

The Dilworth theorem for finite posets implies that a finite poset contains either a "large" chain or a "large" antichain. I am sure I saw an infinite version of this :
An infinite poset has either ...

**2**

votes

**0**answers

59 views

### injective map between tensor products of two irreducible modules of simple Lie algebra sl_{n+1}

Let $1 \leq i_1 < i_2 < i_3 \leq n$. I know that there is an injective map from $V(\omega_{i_1}+\omega_{{i_2} -1})\otimes V(\omega_{{i_3}+1})$ to $V(\omega_{i_1}+\omega_{i_2})\otimes V(\omega_{...

**18**

votes

**2**answers

2k views

### A finite alternating sum

We have stumbled upon the following finite alternating sum, which we have trouble analyzing. The sum is:
$$
S_n = \sum_{j=0}^n \frac{ (-1)^j e^{-j} }{j!} (n-j)^j
$$
We have observed numerically that ...

**2**

votes

**2**answers

189 views

### Compositions $(n_1,…,n_r)$ of an integer $m$ such that $i$ divides $n_i$

I am studying the compositions $(n_1,...,n_r)$ of an integer $m$ such that $i\vert n_i$ for all $i=1,...,r$. (Recall that a composition $(n_1,...,n_r)\vDash m$ of $m$ is just a sequence $(n_1,...,n_r)\...

**0**

votes

**0**answers

98 views

### Combinatorics of merging sequences from multinomial coefficients

If you have $m$ sequences $a_{11},\dots,a_{1n_1}$ through $a_{m1},\dots,a_{mn_m}$ each sorted in ascending order (assume there are no duplicates) then there is an unique way to merge them.
How many ...

**1**

vote

**1**answer

79 views

### Does the Kimberling sequence map numbers “arbitrarily far away”?

The Kimberling sequence is a recursively defined "shuffling sequence" (pictorial description here). Let $k:\mathbb{N}\to \mathbb{N}$ be the Kimberling sequence. Does $k$ map members of $\mathbb{N}$ ...

**5**

votes

**0**answers

160 views

### Sum over permutations involving sign

The problem is to evaluate the following sum over all permutations $\sigma\in S_{d}$ of $\{1,2,...,d\}$:
$\displaystyle\sum_{\sigma\in S_{d}}\text{sgn}(\sigma)\displaystyle\frac{1}{\prod_{i=1}^{d}(\...

**0**

votes

**1**answer

69 views

### Recognition of a graph as a product of its quotients

Is there an algorithm to determine whether a given simple graph $G$ is a product graph, typically, say a cartesian product graph of two smaller simple graphs $G_1, G_2$, such that the two simple ...

**14**

votes

**0**answers

380 views

### Finite version special case Jacobi triple product formula

In this paper, Shanks uses the following formula:
$$ \sum_{s=0}^{n-1}q^{s(2n+1)} \times \left( \prod_{k=s+1}^{n} \dfrac{1-q^{2k}}{1-q^{2k-1}}\right) = \sum_{s=1}^{2n} q^{\frac{s(s-1)}{2}}$$
to get a ...

**0**

votes

**1**answer

142 views

### Is the union-closed sets conjecture open for the power sets case?

In a paper published by Bruhn and Schaudt, as well as in a presentation given by Bruhn, they point out how the union-closed sets conjecture is tight for power sets, implying it is still open. I am ...

**15**

votes

**3**answers

506 views

### Size of sets with complete double

Let $[n]$ denote the set $\{0,1,...,n\}$. A subset $S\subseteq [n]$ is said to have complete double if $S+S=[2n]$. Let $m(n)$ be the smallest size of a subset of $[n]$ with complete double. My ...

**1**

vote

**1**answer

125 views

### Estimation of Hypergeometric function ${_3F_2}$ [closed]

Is there any way to estimate the following function, which is a result of sum of ratios of Gamma functions?
$$
{_3F_2}\begingroup
\renewcommand*{\arraystretch}
% your pmatrix expression
\left[
\begin{...