Bijections and random generation

[videlec]

There are many bijections between maps (possibly with extra structure such as a coloring, orientation, ...) and other objects (decorated trees, walks, ...). Among other things, these bijections can sometimes be used for efficient (random or exhaustive) generation. The goal of this issue is to list the known constructions and organize their implementation in topsurf.
Questions:

Work in progress:

Reduced maps (or one-vertex-one-face maps)

In fixed genus, uniform reduced maps can be generated using a reasonably efficient rejection algorithm using split and join sequences. This is done in uniform_reduced_map in 8bb5866

Questions

• Given a map, isn't there a way to make a canonical tree-cotree decomposition to obtain a reduced map (= one-vertex-one-face map)? The blossoming bijection of Albenque-Lepoutre is only half-way through.

References

• G. Chapuy, V. Feray, E. Fusy, A simple model of trees for unicellular maps (2013) Zbl 1278.05081

  not quite a bijection but a n-to-1 map

• E. Fusy, E. Guitter Maps of unfixed genus and blossoming trees (2021) Zbl 1468.05011

  bijection of maps (unfixed genus) with blossoming trees

• M. Lepoutre Blossoming bijection for higher-genus maps (2019) Zbl 1414.05149

  reduction process of a map to a pair (unicellular map (in same genus), and a tree). The tree describes the gluing rules to recover the original map.

• CVS bijection between planar maps and 3-colored trees

• J. Bouttier, Di Francesco, Guitter Planar maps as labeled mobiles (2004)

• G. Schaeffer Bijective Census and Random Generation of Eulerian Planar Maps with Prescribed Vertex Degrees (1997)

  Eulerian maps and Eulerian tree, only planar

• D. Poulhalon, G. Schaeffer Optimal Coding and Sampling of triangulations (2004)

  bijection between planar simple triangulations and some trees, allows fast sampling

• Alonso, Remy, Schott A linear-time algorithm for the generation of trees (1997)

[jschabanel]

On peut déjà commencer par les bijection avec les quadrangulations/les cartes médianes

• Bijection de Schaeffer
  between planar maps and 3 colored trees

• Bouttier, Di Francesco, Guitter Planar Maps as Labeled Mobiles (2004)
  in the title

• Schaeffer, Bijective Census and Random Generation of Eulerian Planar Maps with Prescribed Vertex Degrees (1997)
  eulerian maps and eulerian tree, only planar

• Poulhalon, Schaeffer, Optimal Coding and Sampling of triangulations (2004)
  bijection between planar simple triangulations and some trees, allows fast sampling

[jschabanel]

If we want to do random sampling we'll need a tree sampler at some point. If it doesn't already exist then
Alonso, Remy, Schott A linear-time algorithm for the generation of trees (1997)

[jschabanel]

We'll also need to have some decorated map structure (for the leaves/buds). One solution would be to use the colored map structure and color degree 1 vertices as leaf/bud/inner vertex, I think we could be more efficient but this works without extra code.