Combinatorics - Summer School

Gulbenkian Foundation, LISBON — 23 to 27 JULY 2012



sketch for the panel Começar by José de Almada Negreiros - image reproduced with kind permission of the Gulbenkian Foundation

Program

This school comprises three 5-lecture courses (in English) aimed at 1st- or 2nd-year undergraduate students of mathematics, complemented by problem sessions.

Courses

Symmetric polynomials and Schubert polynomials

by Allen KNUTSON (Cornell University)

Abstract:
Consider the ring of polynomials in variables x1, x2,... and call a polynomial symmetric in xi and xj if switching them results in the same polynomial., e.g. x1 + x2 or x1x2. Highly symmetric polynomials tend to have a lot of terms, which suggests that writing them in terms of monomials (as usual) might not be the best way to study them.
We'll introduce Schubert polynomials, which are a different basis of the ring of polynomials in infinitely many variables. While their definition will be clear from an algebraic point of view, it will turn out (quite nonobviously) that they have positive integer coefficients, so combinatorics enters. The Schubert polynomials in k variables and symmetric in all k are the much more classical "Schur polynomials" and we'll investigate the even richer theory of the multiplication on Schur polynomials.
The only background for the course is familiarity with polynomials and permutations.

Probabilistic Methods

by Benny SUDAKOV (University of California at Los Angeles)

Abstract:
The Probabilistic Method is a powerful tool in tackling many problems in Combinatorics. It belongs to those areas of mathematics which have experienced a most impressive growth in the past few decades. Roughly speaking, its basic idea can be described as follows. In order to prove existence of a combinatorial structure with certain properties, we construct an appropriate probability space, and show that a randomly chosen element of this space has the desired property, with positive probability.
This course provides a gentle introduction to the Probabilistic Method, with emphasis on methodology. We will try to illustrate the main ideas by showing how to use probabilistic reasoning to solve various combinatorial problems.
Most of the course will be self contained (we review the tools and results which we use) but some elementary knowledge of probability and graph theory would certainly be helpful.

Combinatorics and Geometry - a match made in heaven

by Nathan LINIAL (Hebrew University of Jerusalem)

Abstract:
I will present several topics which involve a mix of combinatorics, linear algebra and geometry.
The girth of a graph G is defined as the length of the shortest cycle in G. It is not so simple to construct graphs of high girth, i.e., graphs without short cycles. Concretely, for given d and n we consider the question: What is the largest possible girth of a d-regular graph with n vertices? One specific topic on which I will concentrate in this area is the (almost) complete characterization of k-regular graphs on k^2+1 vertices of girth 5. The girth problem is closely related to the notion of linear error-correcting codes and I will present next some basic results from that area.
If time permits I will go into somewhat more advanced topics. One particularly beautiful topic I hope to be able to present is the refutation of the Borsuk conjecture from geometry.

Schedule

Monday, July 23 Tuesday, July 24 Wednesday, July 25 Thursday, July 26 Friday, July 27
9:30-10:00 opening
10:00-11:00 A. KNUTSON N. LINIAL A. KNUTSON A. KNUTSON A. KNUTSON
11:00-11:30 coffee break coffee break coffee break coffee break coffee break
11:30-12:30 B. SUDAKOV B. SUDAKOV A. KNUTSON N. LINIAL B. SUDAKOV
12:30-14:00 lunch break lunch break N. LINIAL
(until 13.30)
lunch break lunch break
14:00-15:00 N. LINIAL B. SUDAKOV N. LINIAL B. SUDAKOV
15:00-15:30 coffee break coffee break coffee break coffee break
15:30-17:00 PROBLEM SESSION PROBLEM SESSION PROBLEM SESSION PROBLEM SESSION

Friday, July 27, at 21:30 there will be a gathering with the lecturers at Hotel Príncipe Lisboa, Av. Duque de Ávila, 201 (right next to Hotel Alif Avenidas) where participants will be able to talk to the lecturers about their careers in a relaxed setting.

Mini-conference

On Saturday, July 28, there will be student mini-conference at the Gulbenkian Foundation which will include talks by Profs. Knutson and Sudakov.
All school participants are invited to attend this mini-conference.

Schedule for mini-conference (28/July/2011)

Assistants

João Guerreiro () and João Gouveia ()

Venue

The school takes place in the headquarters of the Gulbenkian Foundation (Avenida de Berna, Lisbon), with lectures and problem sessions in Sala 1.