Bijective counting of plane bipolar orientations and Schnyder woods (Q1039437)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Bijective counting of plane bipolar orientations and Schnyder woods
scientific article

    Statements

    Bijective counting of plane bipolar orientations and Schnyder woods (English)
    0 references
    0 references
    0 references
    0 references
    30 November 2009
    0 references
    The authors introduce a bijection \(\Phi\) between plane bipolar orientations with prescribed numbers of vertices and faces, and non-intersecting triples of upright lattice paths with prescribed extremities, this bijection provides a combinatorial proof of the following formula due to Baxter [\textit{R.J. Baxter}, ``Dichromatic polynomials and Potts models summed over rooted maps'', Ann. Comb. 5, No.\,1, 17--36 (2001; Zbl 0983.05041)] for the number \(\Theta_{ij}\) of plane bipolar orientations with \(i\) non-polar vertices and \(j\) inner faces: \[ \Theta_{ij}=2\frac{(i+j)! (i+j+1)! (i+j+2)!}{i! (i+1)! (i+2)! j! (j+1)! (j+2)!}. \] It is also shown that \(\Phi\) specializes into the bijection of Bernardi and Bonichon between Schnyder woods and non-crossing pairs of Dyck words.
    0 references
    0 references
    0 references
    bijection
    0 references
    bipolar orientations
    0 references
    non-intersecting paths
    0 references
    0 references
    0 references
    0 references