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
0answers
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
3answers
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
2answers
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
2answers
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
1answer
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
3answers
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
0answers
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
1answer
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
0answers
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
4answers
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
0answers
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
1answer
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
2answers
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
0answers
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
2answers
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
0answers
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
2answers
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
3answers
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
1answer
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{...
