ترغب بنشر مسار تعليمي؟ اضغط هنا

Extending the Backman-Baker-Yuens Geometric Bijection to a subgraph-orientation correspondence

49   0   0.0 ( 0 )
 نشر من قبل Changxin Ding
 تاريخ النشر 2021
  مجال البحث
والبحث باللغة English
 تأليف Changxin Ding




اسأل ChatGPT حول البحث

Let $G$ be a connected finite graph. Backman, Baker, and Yuen have constructed a family of explicit and easy-to-describe bijections $g_{sigma,sigma^*}$ between spanning trees of $G$ and $(sigma,sigma^*)$-compatible orientations, where the $(sigma,sigma^*)$-compatible orientations are the representatives of equivalence classes of orientations up to cycle-cocycle reversal which are determined by a cycle signature $sigma$ and a cocycle signature $sigma^*$. Their proof makes use of zonotopal subdivisions and the bijections $g_{sigma,sigma^*}$ are called emph{geometric bijections}. In this paper, we extend the geometric bijections to subgraph-orientation correspondences. Moreover, we extend the geometric constructions accordingly. Our proofs are purely combinatorial, even for the geometric constructions. We also provide geometric proofs for partial results, which make use of zonotopal tiling, relate to Backman, Baker, and Yuens method, and motivate our combinatorial constructions. Finally, we explain that the main results hold for emph{regular matroids}.

قيم البحث

اقرأ أيضاً

103 - David Callan 2016
There is a bijection from Schroder paths to {4132, 4231}-avoiding permutations due to Bandlow, Egge, and Killpatrick that sends area to inversion number. Here we give a concise description of this bijection.
117 - David Callan 2016
We show that sequences A026737 and A111279 in The On-Line Encyclopedia of Integer Sequences are the same by giving a bijection between two classes of Grand Schroder paths.
A di-sk tree is a rooted binary tree whose nodes are labeled by $oplus$ or $ominus$, and no node has the same label as its right child. The di-sk trees are in natural bijection with separable permutations. We construct a combinatorial bijection on di -sk trees proving the two quintuples $(LMAX,LMIN,DESB,iar,comp)$ and $(LMAX,LMIN,DESB,comp,iar)$ have the same distribution over separable permutations. Here for a permutation $pi$, $LMAX(pi)/LMIN(pi)$ is the set of values of the left-to-right maxima/minima of $pi$ and $DESB(pi)$ is the set of descent bottoms of $pi$, while $comp(pi)$ and $iar(pi)$ are respectively the number of components of $pi$ and the length of initial ascending run of $pi$. Interestingly, our bijection specializes to a bijection on $312$-avoiding permutations, which provides (up to the classical {em Knuth--Richards bijection}) an alternative approach to a result of Rubey (2016) that asserts the two triples $(LMAX,iar,comp)$ and $(LMAX,comp,iar)$ are equidistributed on $321$-avoiding permutations. Rubeys result is a symmetric extension of an equidistribution due to Adin--Bagno--Roichman, which implies the class of $321$-avoiding permutations with a prescribed number of components is Schur positive. Some equidistribution results for various statistics concerning tree traversal are presented in the end.
95 - Heesung Shin 2008
In 1980, G. Kreweras gave a recursive bijection between forests and parking functions. In this paper we construct a nonrecursive bijection from forests onto parking functions, which answers a question raised by R. Stanley. As a by-product, we obtain a bijective proof of Gessel and Seos formula for lucky statistic on parking functions.
The abstract induced subgraph poset of a graph is the isomorphism class of the induced subgraph poset of the graph, suitably weighted by subgraph counting numbers. The abstract bond lattice and the abstract edge-subgraph poset are defined similarly b y considering the lattice of subgraphs induced by connected partitions and the poset of edge-subgraphs, respectively. Continuing our development of graph reconstruction theory on these structures, we show that if a graph has no isolated vertices, then its abstract bond lattice and the abstract induced subgraph poset can be constructed from the abstract edge-subgraph poset except for the families of graphs that we characterise. The construction of the abstract induced subgraph poset from the abstract edge-subgraph poset generalises a well known result in reconstruction theory that states that the vertex deck of a graph with at least 4 edges and without isolated vertices can be constructed from its edge deck.12
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا