Mathematics Wiskunde

English

Enumerative combinatorics with applications to computer science

6 - 17 January 2025, Stellenbosch University, South Africa

Cimpa logo

The aim of this CIMPA school (part of the CIMPA series found here) will be to familiarise graduate students and early-career researchers with the field of enumerative and analytic combinatorics, and to show its many connections to other areas, especially computer science.

The courses range from introductory to more advanced levels. The introductory courses will lay the groundwork by discussing the basic concepts (such as generating functions and enumeration methods) and techniques (various enumeration techniques and analytic methods such as singularity analysis). Then, techniques relating to particular combinatorial objects will be discussed, covering partitions, trees, and permutations as objects. Practical courses in SageMath covering packages and techniques used in this type of combinatorics will be given.

In the final week of the school, some afternoons will be spent forming small research groups. It is hoped that these research groups will continue online after the school.

Administrative and scientific coordinators:

Scientific committee:

  • Sarah Selkirk (University of Warwick, United Kingdom)
  • Stephan Wagner (Uppsala University, Sweden & Graz University of Technology, Austria)

Scientific program:

Click on each course to reveal the lecturer and course outline.

Course 1: Enumeration methods By Dimbinaina Ralaivaosaona (Stellenbosch University, South Africa).
This course introduces algebraic techniques in enumerative combinatorics. Inner structures of a given class of combinatorial objects can be exploited to obtain information on the generating function associated with the class through a process known as the symbolic method (ref. “Analytic Combinatorics” by P. Flajolet and R. Sedgewick). We will rigorously explain this process in this course.
Course 2: Introduction to Analytic Combinatorics By Frédérique Bassino (Université Sorbonne Paris Nord, France).
This course is a short introduction to Analytic Combinatorics, a relatively recent and successful branch of mathematics which relies on combinatorial techniques and analysis to study the properties of (large) discrete combinatorial structures. The course will focus on the analysis of singularities (analytic techniques). Throughout the course, we will illustrate with many examples the basics of Analytic Combinatorics with applications from computer science, specifically from the analysis of algorithms and of data structures.
Course 3: Partitions and q-series By Darlison Nyirenda (University of the Witwatersrand, South Africa).
The goal of this course is to introduce the audience to a wide range of ideas in partition theory from an analytic perspective. Topics to be covered include: Elementary aspects of integer partitions and generating functions, Jacobi’s triple product identity, The Euler Pentagonal Number Theorem, q-series, MacMahon Partition Analysis, Gaussian polynomials and Ramanujan congruences for the partition function.
Course 4: Tree enumeration and tree parameters By Stephan Wagner (Uppsala University, Sweden & Graz University of Technology, Austria).
Many different types of tree structures are studied in combinatorics: labelled and unlabelled, rooted and unrooted, ordered and unordered, and with different additional conditions. They also occur prominently in many applications, such as data structures and phylogenetics. In this course, we first study enumerative questions with the aim to find exact or asymptotic formulas for the number of trees of a specific kind. We then move on to tree parameters that capture different structural aspects of trees and discuss how to determine information about the distribution of such parameters (such as mean, variance, or limiting distribution).
Course 5: Exploring Permutation Statistics and their Far-reaching Consequences By Olivia Nabawanda (Mbarara University of Science & Technology, Uganda).
In this course, participants shall be introduced to some of the classical results about permutation statistics, using purely enumerative combinatorics techniques. Connections between these results and analytic combinatorics will also be explored. Topics to be covered include: Introduction to permutation statistics and examples, recurrence relations and combinatorial interpretations, multivariate recursive constructions and how they can be used to prove real rootedness and stability in polynomials and systems.
Course 6: Analysis of algorithms By Amalia Duch-Brown (Universitat Politècnica de Catalunya, Spain).
This course is intended to present in an intuitive and pragmatical way the formal and experimental analysis of classic algorithms and data structures. It will emphasize (but not be limited to) the average-case analysis of sorting algorithms such as quicksort and some of its variants as well as data structures such as binary search trees and related ones. The course is self-contained and assumes no specific background on algorithmics or programming nor in the formal tools required to analyse algorithms. However, several concepts from the course “Introduction to analytic combinatorics” of this summer school will be used and reinforced.
Course 7: Generating Combinatorial Objects and Experimental Combinatorics in SageMath By Sarah Selkirk (University of Warwick, United Kingdom).
In The Art of Computer Programming volume 4, a thorough discussion of how to efficiently generate combinatorial objects including partitions, permutations, and trees (covered in previous courses in this school) is given. In this course, we will discuss these methods and use them to study parameters or properties of combinatorial objects which can then be used very experimentally to formulate conjectures and search for counter-examples.
Course 8: Generating Functions and Asymptotic Expansions in SageMath By Clemens Heuberger (University of Klagenfurt, Austria)
Introduction to manipulating various representations of generating functions in the open source mathematics software SageMath, in particular using the ore_algebra package. Furthermore, asymptotic expansions (using the built-in package for Asymptotic Rings) in SageMath will be discussed. In particular, singularity analysis will be carried out in SageMath.

A detailed schedule can be found here.

Professional development events

These will be optional events for school attendees

  • Creating an Online Presence: Creating a professional website, making use of online tools to increase your visibility as a mathematician.
  • Effective Presentation at Conferences and in Scientific Writing: How to create a lasting positive impression when presenting research, and how to write a well-written scientific paper.
  • Doing Mathematics in Africa: Obstacles and Opportunities: A group discussion about challenges faced by researchers in Africa, and what can be done to overcome them.

Registration:

All participants are required to register here. Please note that your registration does not imply that you will be invited to attend the school - invitations will be sent out after the deadline.

Food and accommodation of all participants will be covered through the sponsorship of our generous funders.

We can provide financial support for travel for a limited number of participants from developing countries, application details will be available soon.

Registration and application deadline: 30 September 2024

We as the organisers are committed to creating a welcoming environment for everybody. As such, we would like to strongly encourage people from underrepresented groups to apply to the school. Additionally, if there is anything that we can do to accommodate your needs, please contact us.

Accommodation:

Accommodation is planned to be in a Stellenbosch University student residence, within walking distance of the university. All participants will be housed in the same location, which has dining facilities for breakfast, lunch, and dinner.

If you require any special dietary or living arrangements, please contact the organisers.

Contact us:

Sarah Jane Selkirk (sarah.selkirk@aau.at)

Dimbinaina Ralaivaosaona (naina@sun.ac.za)

Sponsors

EMS logo