# 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
Filter by
Sorted by
Tagged with
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: ...
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 ...
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 ...
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 ...
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 ...
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? ...
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$ ...
234 views

108 views

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....
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 ...
59 views

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