17/12/2004.
This page is under construction and still has many faulty links.
Stay tuned.
This is a (commented) thematic list of my works. Not many comments yet, but this should improve.
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.
Larger texts
- 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.
- 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.
Jumping particles
Succinct data structures
Triangulations and planar maps
Bijection, Coding and Sampling with conjugacy classes of trees
- Dissections and trees: applications
to optimal mesh encoding and random sampling, by Eric
Fusy, Dominique Poulalhon and Gilles Schaeffer, SODA'05.
- 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 coding and sampling of
triangulations, by Dominique Poulalhon and Gilles
Schaeffer. To appear in Algorithmica.
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.
- Also appears as extended abstract in
Formal Power Series and Algebraic Combinatorics,
University of Melbourne, proceedings of the International
Conference FPSAC'03.
- 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.
- A note on bipartite eulerian
planar maps, by Dominique Poulalhon and Gilles
Schaeffer. Manuscript, 5pp.
- 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.
- 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.
- 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.
The shape of random maps
- On the asymptotic number of plane curves and
alternating knots, by Gilles Schaeffer and Paul
Zinn-Justin. Experimental Mathematics, 13(4):483--494.
- 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 Planar
Lattices and Integrated SuperBrownian Excursion, by
Philippe Chassaing and Gilles Schaeffer.
Probability Theory and Related Fields, 128, no. 2,
161--212, 2004.
Also appear as extended abstract
in Algorithms, Trees, Combinatorics and Probability 2002,
Birkauser, proceedings of the colloquium on computer science
and mathematics, Versailles.
- 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.
Other approaches
- Une bijection simple pour les cartes
orientables, by Michel Marcus and Gilles
Schaeffer. Manuscript, 10pp.
This text present the only bijection I know that work on
higher genus surfaces
- 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 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.
Random sampling (without maps)
- 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.
- É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.
Generatingfunctionology (without maps)
- 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.
- 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.
- 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.
- An Asymptotic Freiheitssatz for finitely
generated groups, with Pierre-Alain Cherix. In
Enseign. Math., 44(1-2):9-22.
Bijections (without maps)
Manipulatorics in the symmetric group
- Factorizations in the Symmetric Group and Bicolored Polygon Gluings,
by Gilles Schaeffer and Ekaterina Vassilieva. Submitted to JCTA, 28p.
See also the conference paper:
- A bijection for Unicellular Partitioned Bicolored Maps,
by Gilles Schaeffer and Ekaterina Vassilieva. FPSAC'06.
- Content evaluation and class symmetric
functions by Sylvie Corteel, Alain Goupil and
Gilles Schaeffer. Advances in Mathematics, 188(2), 315-336.
- 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.
- Factorisations of a n-cycle
into m permutations, by Dominique Poulalhon and
Gilles Schaeffer. In Discrete Mathematics, 254(1-3):433-458.
- 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,
- Factoring n-cycles and couting
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)
Other
- 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).
Gilles SCHAEFFER
Le 17 décembre 2003