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.

Filter by
Sorted by
Tagged with
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{...

1 3 4 5 6 7 145