Enumerations of peaks and valleys on non-decreasing Dyck paths

A valley in a Dyck path is a local minimum, and a peak is a local maximum. A Dyck path is non-decreasing if the $y$-coordinates of the valleys of the path valley form anon-decreasing sequence. In this paper we provide some statistics about peaks and valleys in non-decreasing Dyck paths, such as their total number, the number of low and high valleys, low and high peaks, etc. Our methods include bijective proofs, recursive relations, and the symbolic method for generating functions.     

Pairs of noncrossing free Dyck paths and noncrossing partitions

Using the bijection between partitions and vacillating tableaux, we establish a correspondence between pairs of noncrossing free Dyck paths of length 2n and noncrossing partitions of [2n+1] with n+1 blocks. In terms of the number of up steps at odd positions, we find a characterization of Dyck paths constructed from pairs of noncrossing free Dyck paths by using the Labelle merging algorithm.     

List colouring of graphs and generalized Dyck paths

The Catalan numbers occur in various counting problems in combinatorics. This paper reveals a connection between the Catalan numbers and list colouring of graphs. Assume $G$ is a graph and $f:V\left(G\right)\to N$ is a mapping. For a nonnegative integer $m$, let $f^{\left(m\right)}$ be the extension of $f$ to the graph $G$

 $\overline{K_m}$ for which $f^{\left(m\right)}\left(v\right)=\left|V\left(G\right)\right|$ for each vertex $v$ of $\overline{K_m}$. Let $m_c(G,f)$ be the minimum $m$ such that $G$

 $\overline{K_m}$ is not $f^{\left(m\right)}$-choosable and $m_p(G,f)$ be the minimum $m$ such that $G$

 $\overline{K_m}$ is not $f^{\left(m\right)}$-paintable. We study the parameter $m_c(K_n,f)$ and $m_p(K_n,f)$ for arbitrary mappings $f$. For $\overrightarrow{x}=(x_1,x_2,\dots ,x_n)$, an $\overrightarrow{x}$-dominated path ending at $(a,b)$ is a monotonic path $P$ of the $a\times b$ grid from $(0,0)$ to $(a,b)$ such that each vertex $(i,j)$ on $P$ satisfies $i\le x_{j+1}$. Let $\psi \left(\overrightarrow{x}\right)$ be the number of $\overrightarrow{x}$-dominated paths ending at $(x_n,n)$. By this definition, the Catalan number $C_n$ equals $\psi \left((0,1,\dots ,n?1)\right)$. This paper proves that if $G=K_n$ has vertices $v_1,v_2,\dots ,v_n$ and $f\left(v_1\right)\le f\left(v_2\right)\le \dots \le f\left(v_n\right)$, then $m_c(G,f)=m_p(G,f)=\psi \left(\overrightarrow{x}\left(f\right)\right)$, where $\overrightarrow{x}\left(f\right)=(x_1,x_2,\dots ,x_n)$ and $x_i=f\left(v_i\right)?i$ for $i=1,2,\dots ,n$. Therefore, if $f\left(v_i\right)=n$, then $m_c(K_n,f)=m_p(K_n,f)$ equals the Catalan number $C_n$. We also show that if $G=G_1\cup G_2\cup ?\cup G_p$ is the disjoint union of graphs $G_1,G_2,\dots ,G_p$ and $f=f_1\cup f_2\cup ?\cup f_p$, then $m_c(G,f)={\prod }_{i=1}^p{m}_c(G_i,f_i)$ and $m_p(G,f)={\prod }_{i=1}^p{m}_p(G_i,f_i)$. This generalizes a result in Carraher et al. (2014), where the case each $G_i$ is a copy of $K_1$ is considered.     

A bijection between 2-triangulations and pairs of non-crossing Dyck paths

A k-triangulation of a convex polygon is a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. We present a bijection between 2-triangulations of a convex n-gon and pairs of non-crossing Dyck paths of length 2(n−4). This solves the problem of finding a bijective proof of a result of Jonsson for the case k=2. We obtain the bijection by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.     

Enumeration of Łukasiewicz paths modulo some patterns

For any pattern $\alpha$ of length at most two, we enumerate equivalence classes of ?ukasiewicz paths of length $n\ge 0$ where two paths are equivalent whenever the occurrence positions of $\alpha$ are identical on these paths. As a byproduct, we give a constructive bijection between Motzkin paths and some equivalence classes of ?ukasiewicz paths.     

A note on 2-distant noncrossing partitions and weighted Motzkin paths

We prove a conjecture of Drake and Kim: the number of 2-distant noncrossing partitions of {1,2,…,n} is equal to the sum of weights of Motzkin paths of length n, where the weight of a Motzkin path is a product of certain fractions involving Fibonacci numbers. We provide two proofs of their conjecture: one uses continued fractions and the other is combinatorial.     

Knight's paths towards Catalan numbers

We provide enumerating results for partial knight's paths of a given size. We prove algebraically that zigzag knight's paths of a given size ending on the x-axis are enumerated by the generalized Catalan numbers, and we give a constructive bijection with peakless Motzkin paths of a given length. After enumerating partial knight's paths of a given length, we prove that zigzag knight's paths of a given length ending on the x-axis are counted by the Catalan numbers. Finally, we give a constructive bijection with Dyck paths of a given length.     

Two disjoint shortest paths problem with non-negative edge length

In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs $(s_1,t_1)$ and $(s_2,t_2)$, and the objective is to find two vertex-disjoint paths $P_1$ and $P_2$ such that $P_i$ is a shortest path from $s_i$ to $t_i$ for $i=1,2$, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.     

Inversion polynomials for 321-avoiding permutations

We prove a generalization of a conjecture of Dokos, Dwyer, Johnson, Sagan, and Selsor giving a recursion for the inversion polynomial of 321-avoiding permutations. We also answer a question they posed about finding a recursive formula for the major index polynomial of 321-avoiding permutations. Other properties of these polynomials are investigated as well. Our tools include Dyck and 2-Motzkin paths, polyominoes, and continued fractions.     

Complete graphs and complete bipartite graphs without rainbow path

Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs $G$ and $H$, the $k$-colored Gallai–Ramsey number $g{r}_k(G:H)$ is defined to be the minimum integer $n$ such that $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete graph $K_N$ contains a monochromatic copy of $H$. In this paper, we first provide some exact values and bounds of $g{r}_k(P_5:K_t)$. Moreover, we define the $k$-colored bipartite Gallai–Ramsey number $bg{r}_k(G:H)$ as the minimum integer $n$ such that $n^2\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete bipartite graph $K_{N,N}$ contains a monochromatic copy of $H$. Furthermore, we describe the structures of complete bipartite graph $K_{n,n}$ with no rainbow $P_4$ and $P_5$, respectively. Finally, we find the exact values of $bg{r}_k(P_4:K_{s,t})$ ($1\le s\le t$), $bg{r}_k(P_4:F)$ (where $F$ is a subgraph of $K_{s,t}$), $bg{r}_k(P_5:K_{1,t})$ and $bg{r}_k(P_5:K_{2,t})$ by using the structural results.     

Geometric aspects of p-capacitary potentials

We provide monotonicity formulas for solutions to the p-Laplace equation defined in the exterior of a convex domain. A number of analytic and geometric consequences are derived, including the classical Minkowski inequality as well as new characterizations of rotationally symmetric solutions and domains. The proofs rely on the conformal splitting technique introduced by the second author in collaboration with V. Agostiniani.     

The size of 3-uniform hypergraphs with given matching number and codegree

To determine the size of $r$-graphs with given graph parameters is an interesting problem. Chvátal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted maximum degree and matching number; Khare (DM, 2014) studied the same problem for linear 3-graphs with restricted matching number and maximum degree. In this paper, we give a tight upper bound of the size of 3-graphs with bounded codegree and matching number.     

The genesis of involutions (Polarizations and lattice paths)

The number of Borel orbits in the symmetric space $S{L}_n∕S(G{L}_p\times G{L}_q)$ is analyzed, various (bivariate) generating functions are found. Relations to lattice path combinatorics are explored.     

New upper bound for multicolor Ramsey number of odd cycles

Let $r_k\left(C_{2m+1}\right)$ be the $k$-color Ramsey number of an odd cycle $C_{2m+1}$ of length $2m+1$. It is shown that for each fixed $m\ge 2$, $r_k\left(C_{2m+1}\right)<c^k\sqrt{k!}$for all sufficiently large $k$, where $c=c\left(m\right)>0$ is a constant. This improves an old result by Bondy and Erd?s (1973).     

H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups

We consider the structure of $H$-free subgraphs of graphs with high minimal degree. We prove that for every $k>m$ there exists an $???(k,m)>0$ so that the following holds. For every graph $H$ with chromatic number $k$ from which one can delete an edge and reduce the chromatic number, and for every graph $G$ on $n>n_0\left(H\right)$ vertices in which all degrees are at least $(1??)n$, any subgraph of $G$ which is $H$-free and contains the maximum number of copies of the complete graph $K_m$ is $(k?1)$-colorable.We also consider several extensions for the case of a general forbidden graph $H$ of a given chromatic number, and for subgraphs maximizing the number of copies of balanced blowups of complete graphs.