Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCycles on a multiset with only even-odd drops
119
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For a finite subset $A$ of $mathbb{Z}_{>0}$, Lazar and Wachs (2019) conjectured that the number of cycles on $A$ with only even-odd drops is equal to the number of D-cycles on $A$. In this note, we introduce cycles on a multiset with only even-odd drops and prove bijectively a multiset version of their conjecture. As a consequence, the number of cycles on $[2n]$ with only even-odd drops equals the Genocchi number $g_n$. With Laguerre histories as an intermediate structure, we also construct a bijection between a class of permutations of length $2n-1$ known to be counted by $g_n$ invented by Dumont and the cycles on $[2n]$ with only even-odd drops.
rate research
Read More
Recently, Lazar and Wachs (arXiv:1910.07651) showed that the (median) Genocchi numbers play a fundamental role in the study of the homogenized Linial arrangement and obtained two new permutation models (called D-permutations and E-permutations) for (median) Genocchi numbers. They further conjecture that the distributions of cycle numbers over the two models are equal. In a follow-up, Eu et al. (arXiv:2103.09130) further proved the gamma-positivity of the descent polynomials of even-odd descent permutations, which are in bijection with E-permutations by Foatas fundamental transformation. This paper merges the above two papers by considering a general moment sequence which encompasses the number of cycles and number of drops of E-permutations. Using the combinatorial theory of continued fraction, the moment connection enables us to confirm Lazar-Wachs conjecture and obtain a natural $(p,q)$-analogue of Eu et als descent polynomials. Furthermore, we show that the $gamma$-coefficients of our $(p,q)$-analogue of descent polynomials have the same factorization flavor as the $gamma$-coeffcients of Brandens $(p,q)$-Eulerian polynomials.
In this paper, we investigate the ratio of the numbers of odd and even cycles in outerplanar graphs. We verify that the ratio generally diverges to infinity as the order of a graph diverges to infinity. We also give sharp estimations of the ratio for several classes of outerplanar graphs, and obtain a constant upper bound of the ratio for some of them. Furthermore, we consider similar problems in graphs with some pairs of forbidden subgraphs/minors, and propose a challenging problem concerning claw-free graphs.
We prove that every family of (not necessarily distinct) odd cycles $O_1, dots, O_{2lceil n/2 rceil-1}$ in the complete graph $K_n$ on $n$ vertices has a rainbow odd cycle (that is, a set of edges from distinct $O_i$s, forming an odd cycle). As part of the proof, we characterize those families of $n$ odd cycles in $K_{n+1}$ that do not have any rainbow odd cycle. We also characterize those families of $n$ cycles in $K_{n+1}$, as well as those of $n$ edge-disjoint nonempty subgraphs of $K_{n+1}$, without any rainbow cycle.
Let $G = (V, E)$ be an $n$-vertex edge-colored graph. In 2013, H. Li proved that if every vertex $v in V$ is incident to at least $(n+1)/2$ distinctly colored edges, then $G$ admits a rainbow triangle. We establish a corresponding result for fixed even rainbow $ell$-cycles $C_{ell}$: if every vertex $v in V$ is incident to at least $(n+5)/3$ distinctly colored edges, where $n geq n_0(ell)$ is sufficiently large, then $G$ admits an even rainbow $ell$-cycle $C_{ell}$. This result is best possible whenever $ell otequiv 0$ (mod 3). Correspondingly, we also show that for a fixed (even or odd) integer $ell geq 4$, every large $n$-vertex oriented graph $vec{G} = (V, vec{E})$ with minimum outdegree at least $(n+1)/3$ admits a (consistently) directed $ell$-cycle $vec{C}_{ell}$. Our latter result relates to one of Kelly, Kuhn, and Osthus, who proved a similar statement for oriented graphs with large semi-degree. Our proofs are based on the stability method.
For a graph $H$ and an integer $kge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $mge4$ vertices and let $Theta_m$ denote the family of graphs obtained from $C_m$ by adding an additional edge joining two non-consecutive vertices. Unlike Ramsey number of odd cycles, little is known about the general behavior of $R_k(C_{2n})$ except that $R_k(C_{2n})ge (n-1)k+n+k-1$ for all $kge2$ and $nge2$. In this paper, we study Ramsey number of even cycles with chords under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. For an integer $kgeq 1$, the Gallai-Ramsey number $GR_k(H)$ of a graph $H$ is the least positive integer $N$ such that every Gallai $k$-coloring of the complete graph $K_N$ contains a monochromatic copy of $H$. We prove that $GR_k(Theta_{2n})=(n-1)k+n+1$ for all $kgeq 2$ and $ngeq 3$. This implies that $GR_k(C_{2n})=(n-1)k+n+1$ all $kgeq 2$ and $ngeq 3$. Our result yields a unified proof for the Gallai-Ramsey number of all even cycles on at least four vertices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
