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

1,586 questions
605 views

### Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by $$\frac{k}{2n-k}{2n-k \choose n}.$$ The number of Dyck paths from the ...
3k views

784 views

### Best possible sieves for the jacobsthal problem, linear programming, and the prime 2

Background/Motivation Gerhard Paseman asked a question about bounds on the Jacobsthal function a while ago, which made me curious about whether the known bounds are best possible. Briefly, the ...
186 views

### Problem with the vertices of a convex quadrilateral on integer lattice

I made the following observation and I am wondering if it is always true. Let $x_1$, $x_2$, $x_3$ and $x_4$ be four positive integer points in the plane ($x_i\in\mathbb{Z^2_{\geq 0}}$) forming a ...
171 views

### Triangulations of convex surfaces

Let $M$ be a smooth closed positively curved surface in Euclidean 3-space, $T$ be a geodesic triangulation of $M$, and $E$ be the edge graph of the convex hull of vertices of $T$. It is easy to see ...
611 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, ...
496 views

### What is the six positive real number for a dice producing a highest chance?

Say there is a dice with six faces, each face has a positive real number different from others. There is a chessman on the origin of the number axis. In each trial, the dice rolls infinite times. ...
233 views

### Finding a semi-sparse vertex in a grid

Let $H$ be a $r \times r$ grid. Suppose that at most $r/10^5$ vertices of this grid are colored red. For every vertex $v \in V(H)$, let $B_i(v)$ be the ball of radius $i$ centered at $v$. (Or for ...
185 views

### Distribution of longest run locations in a random string

Let x be a random n-bit string, and let $I ={i_1,i_2,...,i_n}$ be the starting indexes of the longest 0-runs of x, sorted in decreasing order (so $i_1$ is the starting index of the longest (~$\log n$) ...
397 views

### Combinatorial optimization problem for bipartite graphs

Let $G(V_1\cup V_2, E)$ be a simple bipartite graph having $n$ vertices and $m$ edges, such that $|V_1|=|V_2|$ (which implies that $n$ is an even number). Given any node $i \in V_1\cup V_2$, we denote ...
479 views

### Birthday Inequality for non uniform distribution with specific collision entropy

Let $D$ be a distribution with collision-entropy $k$, i.e., $H_2(D) = k$. Let $n$ samples are chosen independently according to the distribution $D$. Let $E_n$ be the event that there is no ...
207 views

### Which 3-regular graphs are Schreier coset graphs

Given a group $G$ and a subgroup $H$ the Schreier coset graph (w.r.t. some set $S$ of $G$) is the directed (and labelled) graph whose vertices are the cosets of $H$ (i.e. the set $G/H$) and $x \sim y$ ...
312 views

### Generating Uniquely k-Optimal Point Sets

This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the ...
139 views

### Does the likelihood of these tables exist?

Probably it does, and may be a number near $e^{-3/2}$ for 2-deficient tables. First some background. Early on in my studies of universal algebra, I encountered a result of Vadim Murskii, with the ...
236 views

### H-generalized join graph

The $A$-join of a set of graphs $\{ G_a \}_{a \in A}$ as‎ ‎the graph $H$ with vertex and edge sets‎ ‎\begin{eqnarray*}‎ ‎V(H) &=& \{(x,y) \ | \ x \in V(A) \ \& \ y \in V(G_x) \},\\‎ ‎...
78 views

### Evaluation of a complete homogeneous symmetric polynomial related to Stirling number of 2nd kind

It is well known that the complete homogeneous symmetric polynomial $h_{n-k}(1,\,2,\,3, ...,\,k-1,\,k)$ equals $S(n,\,k)$ the Stirling number of the second kind. [Wikipedia] During a research project ...
61 views

### Asymptotic upper bound for partial binomial-like sum

I want to upper bound the quantity $$\sum_{i\le \alpha n} \binom{n}{i}\lambda^i$$, where ${\lambda>1}$, $0<\alpha<1$. It is not the same as partial sum of binomial coefficients. An asymptotic ...
67 views

### Random Optimization on Graphs: Minimum Cut

Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...
143 views

### Coefficients of the monomials appearing in a Schubert polynomial

It is known that the coefficients of the monomials appearing in a Schubert polynomial are always positive. My question is: Is it always true that at least one such coefficient must be $1$? If that is ...
179 views

### Bounds on degrees of minors obtained by edge contractions of regular graphs

Given a connected $d$-regular graph $G=(V,E)$, generate a sequence of minors by performing only edge contractions and loop deletions (as, e.g., in Karger's algorithm) until the graph collapses to a ...
84 views

### Finding $P$ points among $N$ to approximate a probability density function?

Let $f$ be a probability density function (positive such that $\int_{\mathbb{R}} f(x) \mathrm{d} x = 1$) and $X_0 = \{x_n\}_{1\leq n \leq N}$ be $N$ given real points. We also fix $1 \leq P \leq N$ ...
97 views

### Description of Linear Time Algorithm for TSP in Halin Graphs

I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in "G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...
385 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
265 views

44 views

### Multiplicities of ordered pairs in pairing of two multisets

This is a repost from a question on math.stackexchange. Problem: I have two multisets, $X$ and $Y$. Each is a $k$-combination with repetition of a set $N=\{1,2,3,\dots,n\}$, where $n$ can be greater, ...
53 views

### Is there any relationship between the Hungarian Algorithm and the Hesse Diagram method for ranking and sorting?

The Hungarian algorithm is used for the assignment problem. I would like to know whether the Hesse diagram method can be used to rank and sort as the Hungarian algorithm can.
41 views