Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
2answers
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 ...
48
votes
1answer
3k views

(Approximately) bijective proof of $\zeta(2)=\pi^2/6$ ?

Given $A,B\in {\Bbb Z}^2$, write $A \leftrightarrows B$ if the interior of the line segment AB misses ${\Bbb Z}^2$. For $r>0$, define $S_r:=\{ \{A, B\} | A,B\in {\Bbb Z}^2,||A||<r,||B||<r, |...
15
votes
1answer
475 views

To find a longer path with fixed endvertices in a graph satisfies the following property

Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where $$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$ I found that if the path $P$ satisfies: ...
13
votes
1answer
965 views

Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$. Consider the bipartite ...
9
votes
1answer
928 views

Hobbled rook tour - Hamiltonian cycle on square grid

Consider square grid of even sides ($2n \times 2n$). It is easy to see that there must exist Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balance if the number of vertical ...
7
votes
1answer
374 views

Homomesy in perfect matchings

Assume $n \geq 2$. Let $\mathcal{M}_n$ denote the set of perfect matchings on $[2n] := \{1,\ldots,2n\}$, i.e., the set of partitions of $[2n]$ into pairs. For $M \in \mathcal{M}_n$, and $p = \{a,b\}$,$...
7
votes
1answer
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 ...
6
votes
1answer
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 ...
6
votes
1answer
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 ...
6
votes
1answer
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, ...
5
votes
1answer
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. ...
5
votes
1answer
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 ...
4
votes
1answer
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$) ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
3
votes
1answer
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$ ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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) \},\\‎ ‎...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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) ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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$ ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
-1
votes
1answer
265 views

Odd & even permutations and unit fractions

One more motivated by recent questions of Zhi-Wei Sun. Let $S_n$ be the group of permutations of $\{1,2,\ldots, n\}$. Is it true that, for every $n \ge 8$, there is at least one even permutation $\...
-1
votes
1answer
63 views

Transforming random variables for having good property?

For arbitrary functions $A$ and $B$ and independent random variables $X$ and $Y$, assume that \begin{align} \Omega&\triangleq \{(x,y): A(x,y)=1\},\\ \Lambda&\triangleq \{x: B(x)=1\}. \end{...
-1
votes
1answer
91 views

What type of graph is this? (Edges that are valid / invalid depending on route to node)

I'm trying to model a questionnaire where the flow between questions depends on the answers given in previous questions. Example. (Node represent questions, edges represent answers). As you can see ...
-1
votes
1answer
229 views

Bins and colored balls

Consider $n$ color balls. We throw them as follows. For a given ball $i$, randomly choose $k$ bins; create $k$ 'copies' of the ball (i.e., of the same color of the ball $i$); throw a 'copy ball' into ...
-1
votes
1answer
192 views

Collecting terms of a linear expression with nested sums and combinatorics in coefficients

I need to collect the $\Pr(\cdot)$ terms of the following expression: $\sum_{m=3}^{n}\frac{g_{m}\left( \cdot \right) }{\left( \sqrt{\theta \left( 1-\theta \right) }\right) ^{m}}\left[ \sum_{j=2}^{m-1}...
-1
votes
0answers
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, ...
-1
votes
0answers
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.
-1
votes
0answers
41 views

Max+Min of a specific data set

Let $r\geq 6$ and $3\leq f \leq 2r-3$ be integers. Suppose we have $f$ data points $x_0,x_1,\ldots, x_{f-1}$ such that for each i, $1\leq x_i \leq r-4$ is an positive integer. for each i in $\mathbb ...
-1
votes
0answers
140 views

What is known about Carmichael function distribution and growth?

Let $\lambda(n)$ be the Carmichael Lambda Function of $n$. We know that for every $m$ there is the largest $n_m\in\Bbb N$ such that for every $n>n_m$ we have $\lambda(n)\neq m$ and $\lambda(n_m)=m$...