Publications

Recent papers

  • Counting outerplanar maps (with Ivan Geffner) Electr. J. Combinat. 2017.
  • Limit laws for minor-closed classes of graphs (with Peter Heinig, Tobias Muller and Anusch Taraz), to appear in J. Combin. Theory Ser. B PDF. We establish zero-one laws and convergence laws for several minor-closed classes of graphs, both in first order and monadic second order logic. A main result is the existence of an MSO convergence law for every addable minor-closed class.
  • Maximum degree in minor-closed classes of graphs (with Omer Giménez and Dieter Mitsche) Europ. J. Combinat. 2016 PDF. Given a class of graphs G closed under taking minors, we study the maximum degree of random graphs from G under the uniform distribution. We prove several lower and upper bounds that hold with high probability.
  • Graph enumeration PDF. Chapter 6 from the Handbook of Enumerative combinatorics, edited by Miklós Bóna (CRC Press 2015).
  • On the diameter of random planar graphs (with Guillaume Chapuy, Éric Fusy and Omer Giménez) Combinat. Probab. Comput. 2015 PDF. We show that the diameter of a random planar graph with n vertices is of order n^(1/4+o(1)).
  • The probability of planarity of a random graph near the critical point (with Vlady Ravelomanana and Juajo Rué) Proc. AMS 2015 PDF. We give an answer to an old question of Erdos and Renyi on the probability of a random graph with n vertices and n/2 edges being planar.

Selected past papers

  • Random planar graphs and beyond, in Proc. ICM 2014 PDF. A survey of random planar graphs, graphs on surfaces, and graphs from minor-closed classes.
  • The maximum degree of random planar graphs (with Michael Drmota, Omer Giménez, Kosta Panagiotou and Angelika Steger) Proc. London Math. Soc. 2014 PDF. We show that the maximum degree of a random planar graph with n vertices is concentrated around c log(n) for some explcit constant c. Previously McDiarmid and Reed (2008) had shown that it is θ(log n).
  • Extremal statistics on non-crossing configurations (with Michael Drmota and Anna de Mier) Discrete Math. 2014 PDF. We show that the maximum vertex degree and the size of the largest component in various random non-crossing configurations is of order log(n), and the diameter is of order √n.
  • On the number of self-dual rooted maps (with Sergey Kitaev and Anna de Mier) European J. Combin. 2014 PDF. We show that the number of self-dual rooted maps with n edges is 3^n*C(n), where C(n) is a Catalan number. We also determine the number of 2- and 3-connected self-dual rooted maps.
  • Graph classes with given 3-connected components (with Omer Giménez and Juanjo Rué) Random Structures Algorithms 2013 PDF. A general framework based on singularity analyis is presented for analyzing classes of graphs defined in terms of their 3-connected members. This scheme includes planar, series-parallel and related classes.
  •  Evaluation of the Tutte polynomial at the points (1,−1) and (2,−1) (with Andrew Goodall, Criel Merino and Anna de Mier) Ann. Comb. 2013 PDF. Motivated by the identity t(Kn+2; 1,−1) = t(Kn; 2, −1), where t(G; x, y) is the Tutte polynomial of a graph G, we search for graphs G having the property that there is a pair of vertices u, v such that t(G; 1, −1) = t(G− {u, v}; 2, −1).
  • Clusters, generating functions and asymptotics for consecutive patterns in permutations (with Sergi Elizalde) Adv. Appl. Math 2012 PDF
  • On the maximum number of cycles in outerplanar and series-parallel graphs (with Anna de Mier) Graphs Combin. 2012 PDF
  • The maximum degree of series-parallel graphs (with Michael Drmota and Omer Giménez) Combin. Probab. Comput. 2011 PDF
  • Degree distribution in random planar graphs (with Michael Drmota and Omer Giménez) J. Combin. Theory Ser. A 2011 PDF
  • Asymptotic enumeration and limit laws for graphs of fixed genus (with Guillaume Chapuy, Éric Fusy, Omer Giménez, and Bojan Mohar, Bojan) J. Combin. Theory Ser. A 2011 PDF
  • Growth constants of minor-closed classes of graphs (with Olivier Bernardi and Dominic Welsh) J. Combin. Thery Ser. B 2010 PDF
  • Vertices of Given Degree in Series-Parallel Graphs (with Michael Drmota and Omer Giménez) Random Structures Algorithms 2010 PDF
  • Asymptotic enumeration and limit laws for planar graphs (with Omer Giménez) Journal AMS 2009 PDF
  • Counting planar graphs and related families of graphs (with Omer Giménez) in Surveys in Combinatorics 2009 PDF.
  • Asymptotic enumeration and limit laws of series-parallel graphs (with Manuel Bodirsky, Omer Giménez and Mihyun Kang) European J. Combin. 2007 PDF
  • Computing Tutte polynomials of graphs with bounded clique-width (with Omer Giménez and Petr Hlineny) SIAM J. Discrete Math. 2006 PDF
  • A solution to the tennis ball problem (with Anna de Mier) Theoret. Comput. Sci. 2005 PDF
  • Lattice Path Matroids: enumerative aspects and Tutte polynomials (with Joseph Bonin and Anna de Mier). J. Combin. Theory Ser. A 2003 PDF
  • Graphs determined by polynomial invariants. Theoret. Comput. Sci. 2003 PDF
  • Irreducibility of the Tutte polynomial of a connected matroid (with Criel Merino and Anna de Mier). J. Combin. Theory Ser. B 2001 PDF
  • Lower bounds on the number of crossing-free graphs of K_n (with Alfredo García and Javier Tejel). Comput. Geometry: Theory Applic. 2000 PDF
  • Analytic Combinatorics of non-Crossing Configurations (with Philippe Flajolet) Discrete Math. 1999 PDF
  • Flipping edges in triangulations (with Ferran Hurtado and Jorge Urrutia). Discrete Comput. Geometry 1999 PDF
  • Graph of triangulations of a convex polygon and tree of triangulations (with Ferran Hurtado). Comput. Geometry: Theory Applic. 1999 PDF
  • Enumeration of non-crossing trees on a circle. Discrete Math 1998 PDF