On the enumeration of plane bipolar posets and transversal structures

05/14/2021
by   Éric Fusy, et al.
0

We show that plane bipolar posets (i.e., plane bipolar orientations with no transitive edge) and transversal structures can be set in correspondence to certain (weighted) models of quadrant walks, via suitable specializations of a bijection due to Kenyon, Miller, Sheffield and Wilson. We then derive exact and asymptotic counting results, and in particular we prove (computationally and then bijectively) that the number of plane bipolar posets on n+2 vertices equals the number of plane permutations of size n, and that the number t_n of transversal structures on n+2 vertices satisfies (for some c>0) the asymptotic estimate t_n∼ c (27/2)^nn^-1-π/arccos(7/8), which also ensures that the associated generating function is not D-finite.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset