Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAction graphs, planar rooted forests, and self-convolutions of the Catalan numbers
73
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that families of action graphs, with initial graphs which are linear of varying length, give rise to self-convolutions of the Catalan sequence. We prove this result via a comparison with planar rooted forests with a fixed number of trees.
rate research
Read More
A well-known conjecture of Richard Stanley posits that the $h$-vector of the independence complex of a matroid is a pure ${mathcal O}$-sequence. The conjecture has been established for various classes but is open for graphic matroids. A biconed graph is a graph with two specified `coning vertices, such that every vertex of the graph is connected to at least one coning vertex. The class of biconed graphs includes coned graphs, Ferrers graphs, and complete multipartite graphs. We study the $h$-vectors of graphic matroids arising from biconed graphs, providing a combinatorial interpretation of their entries in terms of `edge-rooted forests of the underlying graph. This generalizes constructions of Kook and Lee who studied the Mobius coinvariant (the last nonzero entry of the $h$-vector) of graphic matroids of complete bipartite graphs. We show that allowing for partially edge-rooted forests gives rise to a pure multicomplex whose face count recovers the $h$-vector, establishing Stanleys conjecture for this class of matroids.
An edge-coloring of a connected graph $G$ is called a {em monochromatic connection coloring} (MC-coloring for short) if any two vertices of $G$ are connected by a monochromatic path in $G$. For a connected graph $G$, the {em monochromatic connection number} (MC-number for short) of $G$, denoted by $mc(G)$, is the maximum number of colors that ensure $G$ has a monochromatic connection coloring by using this number of colors. This concept was introduced by Caro and Yuster in 2011. They proved that $mc(G)leq m-n+k$ if $G$ is not a $k$-connected graph. In this paper we depict all graphs with $mc(G)=m-n+k+1$ and $mc(G)= m-n+k$ if $G$ is a $k$-connected but not $(k+1)$-connected graph. We also prove that $mc(G)leq m-n+4$ if $G$ is a planar graph, and classify all planar graphs by their monochromatic connectivity numbers.
Given a permutation $f$, we study the positroid Catalan number $C_f$ defined to be the torus-equivariant Euler characteristic of the associated open positroid variety. We introduce a class of repetition-free permutations and show that the corresponding positroid Catalan numbers count Dyck paths avoiding a convex subset of the rectangle. We show that any convex subset appears in this way. Conjecturally, the associated $q,t$-polynomials coincide with the generalized $q,t$-Catalan numbers that recently appeared in relation to the shuffle conjecture, flag Hilbert schemes, and Khovanov-Rozansky homology of Coxeter links.
The classical parking functions, counted by the Cayley number (n+1)^(n-1), carry a natural permutation representation of the symmetric group S_n in which the number of orbits is the nth Catalan number. In this paper, we will generalize this setup to rational parking functions indexed by a pair (a,b) of coprime positive integers. We show that these parking functions, which are counted by b^(a-1), carry a permutation representation of S_a in which the number of orbits is a rational Catalan number. We compute the Frobenius characteristic of the S_a-module of (a,b)-parking functions. Next we propose a combinatorial formula for a q-analogue of the rational Catalan numbers and relate this formula to a new combinatorial model for q-binomial coefficients. Finally, we discuss q,t-analogues of rational Catalan numbers and parking functions (generalizing the shuffle conjecture for the classical case) and present several conjectures.
We first establish the result that the Narayana polynomials can be represented as the integrals of the Legendre polynomials. Then we represent the Catalan numbers in terms of the Narayana polynomials by three different identities. We give three different proofs for these identities, namely, two algebraic proofs and one combinatorial proof. Some applications are also given which lead to many known and new identities.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
