Gilles Schaeffer: preprints & articles

[Home page] [Page maison]

17/12/2004. This page is under construction and still has many faulty links. Stay tuned.

This is an integrated list of my works.
I plan to provide separately: an integrated list, a bibtex file, a commented thematic bibliography, a selection of slides, a publication list, web pages of my coauthors.

to be updated...

2007

• Dissections and trees: applications to optimal mesh encoding and random sampling, by Eric Fusy, Dominique Poulalhon and Gilles Schaeffer, to appear in ACM Transaction on Algorithms
• Bijective counting of plane bipolar orientations, by Eric Fusy, Dominique Poulalhon and Gilles Schaeffer, Eurocomb'07
• The number of Z-convex polyominos, by Enrica Duchi, Simone Rinaldi and Gilles Schaeffer. To appear in Advances in Applied Math., 15p.
  See also the conference paper:
  • The number of Z-convex polyominos, by Enrica Duchi, Simone Rinaldi and Gilles Schaeffer. FPSAC'06.
• A bijective proof of Jackson's formula for the number of factorizations of a cycle, by Gilles Schaeffer and Ekaterina Vassilieva. To appear in JCTA, 28p (revised).
  See also the conference paper:
  • A bijection for Unicellular Partitioned Bicolored Maps, by Gilles Schaeffer and Ekaterina Vassilieva. FPSAC'06.

2006

• Optimal coding and sampling of triangulations, by Dominique Poulalhon and Gilles Schaeffer. Algorithmica, 46 (3-4):505-527.
  See also the conference paper:
  • Optimal coding and sampling of triangulations, by Dominique Poulalhon and Gilles Schaeffer. Extended abstract in Automata, Languages and Programming, C.M. Baeten, J.K. Lenstra, J. Parrow, and G.J. Woeginger eds.- LNCS 2719, Springer, 1080-1094, proceedings of the 30th International Colloquium ICALP'03, Eindhoven.
• On Generating Series of Coloured Planar Trees, by Roland Bacher and Gilles Schaeffer. Séminaire lotharingien de Combinatoire, B55e.
• Planar Graphs, via Well-Orderly Maps and Trees, by Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon and Gilles Schaeffer. Graphs and Combinatorics 22(2):185-202.
  See also the conference paper:
  • Planar Graphs, via Well-Orderly Maps and Trees, by Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon and Gilles Schaeffer. WG'04
• Optimal Succinct Representations of Planar Maps, by Luca Castelli Aleardi, Olivier Devillers and Gilles Schaeffer. SoCG'06

2005

• Dynamic updates of succinct triangulations, by Luca Castelli Aleardi, Olivier Devillers and Gilles Schaeffer. CCCG'05
• Succinct representation of triangulations with a boundary, by Luca Castelli Aleardi, Olivier Devillers and Gilles Schaeffer. WADS'05.
• A combinatorial approach to jumping particles: the parallel TASEP, by Enrica Duchi and Gilles Schaeffer. FPSAC'05.
• A combinatorial approach to jumping particles, by Enrica Duchi and Gilles Schaeffer. Journal of Combinatorial Theory, Series A, 110(1):1--29.
  See also the 2 related conferences papers:
  • A combinatorial approach to jumping particles I: maximal flow regime, by Enrica Duchi and Gilles Schaeffer. FPSAC'04.
  • A combinatorial approach to jumping particles II: general boudary conditions, by Enrica Duchi and Gilles Schaeffer. MathInfo'04.
• Dissections and trees: applications to optimal mesh encoding and random sampling, by Eric Fusy, Dominique Poulalhon and Gilles Schaeffer, SODA'05.
• On the asymptotic number of plane curves and alternating knots, by Gilles Schaeffer and Paul Zinn-Justin. Experimental Mathematics, 13(4):483--494.
• Katriel's Operators for Products of Conjugacy Classes of Sn, by Alain Goupil, Dominique Poulalhon and Gilles Schaeffer. Journal of Algebraic Combinatorics, 21(2):137--146.
• Counting, coding and sampling with words, by Dominique Poulalhon and Gilles Schaeffer. Preliminary version of a chapter for Lothaire's third volume, Applied Combinatorics on Words, 42pp.

2004

• Boltzmann Samplers for the Random Generation of Combinatorial Structures, by Philippe Duchon, Philippe Flajolet, Guy Louchard and Gilles Schaeffer. In Combinatorics, Probability and Computing, 13(4-5):577-625.
  Also appear as extended abstract in Automata, Languages and Programming, P. Widmayer, F. Triguero, R. Morales, M. Hennessy, S. Eidenbenz, R. Conejo eds.- LNCS 2380, Springer, 501-513, proceedings of the 29th International Colloquium ICALP 2002, Malaga.
• Airy Phenomena and Analytic Combinatorics of Connected Graphs, by Philippe Flajolet, Bruno Salvy and Gilles Schaeffer, Electronic Journal of Combinatorics, Volume 11(1), 2004, #R34, pp. 1--30.
• Content evaluation and class symmetric functions by Sylvie Corteel, Alain Goupil and Gilles Schaeffer. Advances in Mathematics, 188(2), 315-336.
• Random Planar Lattices and Integrated SuperBrownian Excursion, by Philippe Chassaing and Gilles Schaeffer. Probability Theory and Related Fields, 128(2):161--212.
  Also appear as extended abstract in Algorithms, Trees, Combinatorics and Probability 2002, Birkauser, proceedings of the colloquium on computer science and mathematics, Versailles.

2003

• A combinatorial interpretation of super-Catalan numbers of order two, by Gilles Schaeffer. Manuscript, 4pp.
• The degree distribution in bipartite planar maps: applications to the Ising model, by Mireille Bousquet-Mélou and Gilles Schaeffer. Manuscript, 32pp.
  Also appears as extended abstract in Formal Power Series and Algebraic Combinatorics, University of Melbourne, proceedings of the International Conference FPSAC'03.
• Description trees and Tutte's formulas, by Robert Cori and Gilles Schaeffer. In Theorical Computer Science. Selected papers in honor of Jean Berstel. 292(1):165--183.
  Also appears as extended abstract in Formal Power Series and Algebraic Combinatorics, proceedings of the International Conference FPSAC'97, Vienna.
• A bijection for triangulations of a polygon with interior points and multiple edges, by Dominique Poulalhon and Gilles Schaeffer. In Theoretical Computer Science, 307(2):385--401.
  Also appears as extended abstract in Formal Power Series and Algebraic Combinatorics, A. Guttmann eds.- University of Melbourne, proceedings of the International Conference FPSAC'02.
  This paper is not the long version of our ICALP'03 paper (appeared in Algorithmica above): here the triangulations are allowed to have multiple edges, as indicated in the title, whereas in the later paper Optimal coding and sampling of triangulations we consider the subset of (more standard) triangulations that have no multiple edges (and thus can be represented with straight edges).

2002

• A note on bipartite eulerian planar maps, by Dominique Poulalhon and Gilles Schaeffer. Manuscript, 5pp.
• Walks on the slitplane, by Mireille Bousquet-Mélou and Gilles Schaeffer. In Probability Theory and Related Fields, 124(3):305-344.
  Also appears as extended abstract in Mathematics and Computer Science: algorithms, trees, combinatorics and probabilities D. Gardy, A. Mokkadem eds. - Birkhauser, 2000 Trends in Mathematics, 101-112, proceedings of the colloquium Mathematics and Computer Science, Versailles.
• Factorisations of a n-cycle into m permutations, by Dominique Poulalhon and Gilles Schaeffer. In Discrete Mathematics, 254(1-3):433-458.

2001

• The asymptotic number of prime alternating links, by Sébastien Kunz-Jacques and Gilles Schaeffer. Extended abstract in Formal Power Series and Algebraic Combinatorics, H. Barcelo eds.-, proceedings of the International Conference FPSAC'01, Phenix.
• Random Maps, Coalescing Saddles, Singularity Analysis, and Airy Phenomena, by Cyril Banderier, Philippe Flajolet, Gilles Schaeffer and Michèle Soria. In Random Structures and Algorithms, 19:194-246.
  Also appears as extended abstract in Automata, Languages, and Programming, U. Montanari, J. Rolim, and E. Welzl eds.- LNCS 1853, Springer, 388-402, proceedings of the colloquium ICALP'00, Geneva.
• Une bijection simple pour les cartes orientables, by Michel Marcus and Gilles Schaeffer. Manuscript, 10pp.

2000

• Énumération et génération aléatoire de cactus m-aire, by Michel Bousquet, Cedric Chauve and Gilles Schaeffer. In Colloque LaCIM 2000, Université du Québec à Montréal.
• Central characters and conjugacy classes of the symmetric group (On some conjectures of J. Katriel) (Extended abstract), by Alain Goupil, Dominique Poulalhon and Gilles Schaeffer. In Formal power series and algebraic combinatorics, D. Krob, A. Mikhalev, V. Mikhalev eds.- Springer, 238-249, proceedings of the International Conference FPSAC'00, Moscou,
• Enumeration of planar constellations, by Mireille Bousquet-Mélou and Gilles Schaeffer. In Adv. in Applied Math., 24:337-368.
  Also appears as extended abstract in Formal power series and algebraic combinatorics, C. Martinez, M. Noy, O. Sera eds.- Universitat Politecnica de Catalunya, 96-107, proceedings of the International Conference FPSAC'99, Barcelona.

1999

• Random Sampling of Large Planar Maps and Convex Polyhedra, by Gilles Schaeffer. In Proceedings of the 31th annual ACM Symposium on the Theory of Computing (STOC'99), Atlanta, ACM press.
• The number of plane corner cuts, by Sylvie Corteel, Gaël Rémond, Gilles Schaeffer and Hugh Thomas. In Adv. in Applied Math., 23:49-53.

1998

• my PhD thesis, Conjugaison d'arbres et cartes combinatoires aléatoires, Université Bordeaux I.
  Prix SPECIF 1999. Ce prix doté distingue une thèse française en informatique chaque année.
  1999 SPECIF price. This award singles out one french computer science PhD thesis every year.
• Factoring n-cycles and counting maps of given genus, with Alain Goupil. In Europ. J. Combinatorics, 19(7):819-834.
  Also appears as extended abstract in Formal power series and algebraic combinatorics, I.P. Goulden eds.- Field Institute, 321-332, proceedings of the International Conference FPSAC'98, Toronto.
  The result is superseeded by Poulalhon and Schaeffer (Discrete Maths, 2002). A simpler proof was given by Biane (arXiv:math.CO/0307147)
• An Asymptotic Freiheitssatz for finitely generated groups, with Pierre-Alain Cherix. In Enseign. Math., 44(1-2):9-22.
• A bijective census of nonseparable planar maps, by Benjamin Jacquard and Gilles Schaeffer. In J. Combin. Theory Ser A., 83(1):1-20.
  A simpler construction than this one appears in Chapter 2 of my phd these.

1997

• Approximation of a direction in bounded coordinates, by Daniel Krob, Florent Hivert, Jean-Christophe Novelli, and Gilles Schaeffer In 1st DialM Conference, Budapest.
  See also Mobile Networks and Applications, 6(6):547-550 (2001).
• Bijective census and random generation of eulerian planar maps, In Electronic Journal of Combinatorics, vol 4, R20, 14pp.
  My first article and also the introduction of my method to contruct planar maps out of plane trees via closure.