Avatar

Marc Noy

Universitat Politècnica de Catalunya

Departament de Matemàtica Aplicada II

Campus Nord, Edifici Omega (office 436),

Jordi Girona 1-3, 08034 Barcelona

marc.noy 'at' upc.edu

+34 934137709

Barcelona Graduate School of Mathematics BGSMath
Catalan, Spanish and European Mathematical Societies
Centre de Recerca Matemàtica CRM

Electronic Journal of Combinatorics
Arxiv Combinatorics
Online Encyclopedia of Integer Sequences
MathSciNet
UPC Seminar on Combinatorics, Graph Theory and Applications


Teaching

Most of my teaching is within the Bachelor and Master Degree in Mathematics at UPC.

Fall 2014

Combinatorics and Graph Theory (Bachelor in Mathematics)
Graph Theory (Master in Mathematics)

Spring 2015

Complex Analysis (Bachelor in Mathematics)
Discrete Mathematics (Bachelor in Mathematics)
Combinatorics (Master in Mathematics)


Students

Past Ph.D. students

Lander Ramos, starting 2013
Juanjo Rué, 2009: Enumeration and limit laws of topological graphs. Currently Junior Professor at Free University Berlin.
Omer Giménez, 2005: Enumerative aspects and Tutte polynomials of graphs and matroids.Currently Engineer at Google, Palo Alto, CA.
Sergi Elizalde, 2004: Consecutive patterns and statistics on restricted permutations.Currently Associate Professor at Dartmouth College, NH.
Anna de Mier, 2003: Graphs and matroids determined by their Tutte polynomials. Currently Associate Professor at UPC.
Carmen Hernando (co-advisor Ferran Hurtado), 1999: Complexity of geometric and combinatorial structures. Currently Associate Professor at UPC.

Master students

Ivan Geffner, 2014
Katerina Bohmova, 2011


Non-academic

If you wish to enjoy music in Barcelona, check the programs at our two concert halls. L’Auditori, a modern and well designed hall, host of the orchestra of Barcelona. And Palau de la Música, a stunning building in art nouveau style (and not too comfortable): pay attention, a number of concerts are ‘tourist-oriented’ of dubious musical quality. For opera lovers, check our opera theater El Liceu. Here is a list of some musical suggestions.


About Me

I am Professor at the Department of Mathematics in Barcelona at UPC, the Technical University of Catalonia. I am affiliated with the School of Mathematics and Statistics, where I do most of my teaching, and with the Barcelona Graduate School in Mathematics (BGSMath), of which I am currently the Director. I am also head of the 2015-2019 Excellence program BGSMath/María de Maeztu.

My research interests are in the area of Combinatorics and Graph Theory, in particular asymptotic enumeration and random graphs. I am also interested in discrete geometry and Tutte polynomials. Here is a short CV. Additional information can be found here.

I am in the editorial board of the Electronic Journal of Combinatorics and the Bulletin of the Catalan Mathematical Society (in Catalan).

Publications

Recent Papers
  1. Logical 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.
  2. 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.
  3. Graph enumeration PDF. Chapter 6 from the Handbook of Enumerative combinatorics, edited by Miklós Bóna (CRC Press 2015).
  4. 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)).
  5. 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
  1. 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.
  2. 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).
  3. 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.
  4. 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.
  5. 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.
  6.  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).
  7. Clusters, generating functions and asymptotics for consecutive patterns in permutations (with Sergi Elizalde) Adv. Appl. Math 2012 PDF
  8. On the maximum number of cycles in outerplanar and series-parallel graphs (with Anna de Mier) Graphs Combin. 2012 PDF
  9. The maximum degree of series-parallel graphs (with Michael Drmota and Omer Giménez) Combin. Probab. Comput. 2011 PDF
  10. Degree distribution in random planar graphs (with Michael Drmota and Omer Giménez) J. Combin. Theory Ser. A 2011 PDF
  11. 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
  12. Growth constants of minor-closed classes of graphs (with Olivier Bernardi and Dominic Welsh) J. Combin. Thery Ser. B 2010 PDF
  13. Vertices of Given Degree in Series-Parallel Graphs (with Michael Drmota and Omer Giménez) Random Structures Algorithms 2010 PDF
  14. Asymptotic enumeration and limit laws for planar graphs (with Omer Giménez) Journal AMS 2009 PDF
  15. Counting planar graphs and related families of graphs (with Omer Giménez) in Surveys in Combinatorics 2009 PDF.
  16. Asymptotic enumeration and limit laws of series-parallel graphs (with Manuel Bodirsky, Omer Giménez and Mihyun Kang) European J. Combin. 2007 PDF
  17. Computing Tutte polynomials of graphs with bounded clique-width (with Omer Giménez and Petr Hlineny) SIAM J. Discrete Math. 2006 PDF
  18. A solution to the tennis ball problem (with Anna de Mier) Theoret. Comput. Sci. 2005 PDF
  19. Lattice Path Matroids: enumerative aspects and Tutte polynomials (with Joseph Bonin and Anna de Mier). J. Combin. Theory Ser. A 2003 PDF
  20. Graphs determined by polynomial invariants. Theoret. Comput. Sci. 2003 PDF
  21. Irreducibility of the Tutte polynomial of a connected matroid (with Criel Merino and Anna de Mier). J. Combin. Theory Ser. B 2001 PDF
  22. 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
  23. Analytic Combinatorics of non-Crossing Configurations (with Philippe Flajolet) Discrete Math. 1999 PDF
  24. Flipping edges in triangulations (with Ferran Hurtado and Jorge Urrutia). Discrete Comput. Geometry 1999 PDF
  25. Graph of triangulations of a convex polygon and tree of triangulations (with Ferran Hurtado). Comput. Geometry: Theory Applic. 1999 PDF
  26. Enumeration of non-crossing trees on a circle. Discrete Math 1998 PDF

Conferences

Forthcoming conferences and workshops
  1. CSASC Joint meeting of the Czech, Slovenian, Austrian, Slovak and Catalan mathematical societies, Barcelona September 2016
  2. FOCM Foundations of Computational Mathematics, Barcelona July 2017
Some meetings I have attended
  1. Discrete Mathematics Days Barcelona July 2016
  2. Symposium on Discrete Mathematics Berlin July 2016
  3. ALEA in Europe Munich February 2016
  4. Fall School on Random Graphs, Cargèse (Corsica)
  5. LMS/EMS Joint Anniversary Mathematical Weekend
  6. Workshop on Logic and Random Graphs, Leiden
  7. Meeting of the Spanish Mathematical Society RSME 2015, Granada
  8. Barcelona Mathematical Days BMD 2014, Barcelona
  9. International Congress of Mathematicians ICM 2014, Seoul
  10. Analysis of Algorithms AOFA 2014, Paris
  11. Workshop on Enumerative Combinatorics 2014, Oberwolfach
  12. Czech-Slovak Symposium on Graph Theory Combinatorics 2013, Kosice
  13. Czech-Slovak-Austrian-Slovenian-Catalan Mathematics Conference CSASC 2013, Koper
  14. ESF Conference Perpectives in Discrete Mathematics 2012, Barcelona
  15. Centennial Conference of the Spanish Mathematical Society 2011, Ávila
  16. FPSAC 2011 Formal Power Series and Algebraic Combinatorics, Reykjavik
  17. Colloquium on Combinatorics 2010, Saarbrücken
  18. Jornadas de Matemática Discreta y Algorítmica JMDA 2010, Castro Urdiales
  19. Workshop on Analysis of Algorithms, Fréjus 2009
  20. British Combinatorial Conference BCC 2009, St Andrews
  21. European Congress of Mathematics ECM 2008, Amsterdam
  22. Colloquium for Philippe Flajolet’s 60th Birthday 2008, Paris
  23. EUROCOMB 2007 European Conference on Combinatorics, Graph Theory and Applications, Sevilla
  24. One-Day Meeting in Combinatorics 2006, Oxford
  25. Séminaire Lotharingien de Combinatoire 2006, Strasbourg
  26. Czech-Catalan Conference in Mathematics 2005, Prague