introduction
Discrete mathematics is a wide (and very active) area in mathematics which has become a central topic in modern research due to its deep interplay with theoretical computer science. The research of the combinatorics group exploits multiple connections of this area with many research disciplines including probability theory, number theory and group theory, among many others. Its interplay with logic and algorithimc plays also a strong line of research for our team.
More precisely, we aim to study several open problems inside the combinatorics framework, within the interplay between areas and in the interaction between different disciplines. In the first direction, we are interested in the study of random discrete structures, as random graphs and random sets, by the use of Erdös probabilistic method. The use of these probability techniques let us to study the typical behaviour of large random objects, as well as their limiting properties. Applications in real-world problems (as the comprehension of large networks) is also an important point addressed in this direction.
Concerning the interplay inside the research team, we are very interested on the role of pseudorandomness in computation. The hardness-vs-randomness trade-off of Nisan and Wigderson transformed the role of randomness in the design of algorithms. In this context, we investigate whether hardness for a model of symmetric computation could be enough to derandomize specific randomized constructions or algorithms. A celebrated example where the analysis of the randomness in a specific algorithm led to the breakthrough of the AKS algorithm, establishing that PRIMES is in P. another important line of research deals with the study of constrained classes of random graphs and logic limit laws: by using a combination of combinatorial, analytic, probabilistic and logical tools we are able to study the enumeration of planar graphs enriched with a global structure, and to determinine the set of limiting probabilities of graph properties in first-order logic for random graphs with given degree sequence; and analyzing the width of thresholds of random graph properties defined in suitable logical languages.
Finally, we are very much interested in the study of number theoretical problems (arising in abelian groups and in non-abelian groups) from a combinatorial perspective. This is the content of Arithmetic combinatorics: in the last years, there has been a dramatic growth of the area due to its connections with Ergodic Theory, Functional Analysis and Extremal Combinatorics. We aim to make progress on this area by combining a wide variety of modern combinatorial techniques (regularity methods, hypergraph containers, and arithmetic removal lemmas) to get a better understanding of maximal densities of sets avoiding certain patterns in groups (finite or infinite); and quasirandomness properties of the associated Cayley graphs, including the stationary behavior of random walks on these structures.
research lines
Logic & Algorithmics
Since its inception, mathematical logic has both contributed to and has been motivated
by the study of foundations of mathematics. Contemporary work in the foundations
of mathematics often focuses on establishing which parts of mathematics can be
formalized in particular formal systems. Algorithmics works in the description of the
set of steps that can be used to solve a specific computation and is becoming more
important in all mathematical fields
Combinatorics
Combinatorics is an area of mathematics concerned with the study of discrete
objects, for example, set systems, graphs, hypergraphs, integers, etc.. It is closely
related to many other areas of mathematics and has many applications including
logic, statistical physics and group theory, among others. Especially with theoretical
computer science, there is a rich interchange that has made this area a very active
field of modern mathematics.
members
Albert Atserias
UPC – CRM
Website
Kolja Knauer
UB – CRM
Website
Marc Noy
UPC – CRM
Website
Arnau Padrol
UB – CRM
Website
Guillem Perarnau
UPC – CRM
Website
Juanjo Rué
UPC – CRM
Website
Oriol Serra
UPC – CRM
Website
postdoctoral researchers
Tássio Naia
Postdoctoral Fellow - CRM
IP: Guillem Perarnau
postdoctoral researchers
Jordi Castellvi
PhD Candidate - CRM
Supervisor: Marc Noy
PUBLICATIONS
Albert Atserias
Full Professor at the Computer Science Department of UPC (Oct 2018 – today)
Associate Professor at the Computer Science Department of UPC (Apr 2005 – Sep 2018).
Lecturer at the Computer Science Department of UPC (Mar 2002- Mar 2005).
Visiting research positions held: Postdoctoral Fellowship at Charles University, Prague (Jul 2006), Program Participant at Isaac Newton Institute for the Mathematical Sciences, Cambridge (Jan-Feb 2007, Jan-Feb 2012), Visiting Scholarship at University of California, Berkeley (Jan-Jun 2008).
Principal Investigator of an ERC Consolidator Grant 2015 – 2020.
Kolja Knauer
I am a Ramon y Cajal researcher at UB since 2019. Before I was an associate professor at Aix-Marseille University. My research lies in the interaction of Algebraic and Geometric Combinatorics with a focus on Graph Theory, (Oriented) Matroids. and Algorithmics. I have answered questions and conjectures of Babai & Pultr, Barat & Thomassen, Biedl & Stern, Fukuda, Golumbic et al., Halman et al., Harutyunyan, Hochstättler, Saks & West, and Winkler.
Marc Noy
Full Professor of Mathematics at the Universitat Politècnica de Catalunya.
Received the Humboldt Research Award (2012) for his achievements in Discrete Mathematics. During 2012-13 was Von Neumann invited Professor at the Technical University of Munich. Invited speaker at the International Congress of Mathematicians in Seoul (2014). Received the Medal Narcís Monturiol (2018) from the Catalan Government for significant contributions to science in Catalonia.
His main scientific achievement is the asymptotic enumeration of planar graphs (jointly with Omer Giménez), which opened the way to the fine analysis of random planar graphs.
He is currently director of the Institute of Mathematics (IMTech) of the Universitat Politècnica de Catalunya.
Arnau Padrol
Professor Titular at the Universitat de Barcelona since 2022.
Previously I was a Maître de Conférences at the Institute de Mathématiques de Jussieu – Paris Rive Gauche at Sorbonne Université (2015-2022), a postdoc under the supervision of Günter Ziegler and Raman Sanyal at the Discrete Geometry Group of the Freie Universität Berlin (2013-2015), and a PhD student under the supervision of Julian Pfeifle at the Universitat Politècnica de Catalunya (2009-2013).
Guillem Perarnau
I did my bachelor, master and PhD at Universitat Politècnica de Catalunya (UPC), advised by Oriol Serra. From 2013 to 2015 I had the pleasure to be a CARP Postdoc Fellow at McGill University, working with Bruce Reed and Louigi Addario-Berry. From 2016 to 2019 I was a Lecturer in the Combinatorics, Probability and Algorithms group at the University of Birmingham. Since 2019 I am an Associate Professor in GAPCOMB at UPC. I am affiliated to CRM and to IMTech, and a member of SCM.
My main research interests are in Probabilistic and Extremal Combinatorics, Random Combinatorial Structures, Discrete Stochastical Processes and the analysis of Randomized Algorithms.
Junajo Rué
Previous positions: Postdoctoral researcher at École Polytechnique (2009-2010) and ICMAT (2010-2013); Professor-W1 at Freie Universität Berlin (2013-2016). Associate Professor at UPC since February 2016
Oriol Serra
I graduated in Mathematics at the Universitat de Barcelona (1983) and obtained a PhD in Mathematical Sciences at Universitat Politècnica de Catalunya (1988). I am full professor at the department of mathematics of UPC since 1999.
I was visiting fellow at University of California, Santa Cruz (1994/95), ENS Télécommunications Paris (2000), Rényi Institute Budapest (2001), Charles University Prague (2005), Institute de Mathématiques de Bordeaux (2012).
I have served as chair of the department of mathematics (2011-2017), vicedean of research of the School of Mathematics at UPC (2007-2011), member of the Executive Committee of the Barcelona Graduate School of Mathematics (2012-2015) and member of the Counclil of the European Mathematical Society (2012-2017) among other duties.