Conférences dans le cadre de l’École CRMClay en combinatoire additive
Lectures at the CRMClay School on Additive Combinatorics
"Combinatorial and ergodic techniques for proving Szemereditype theorems "
This is a series of lectures exploring the graph theory, hypergraph theory, and ergodic theory approaches to Szemeredi's famous theorem on arithmetic progressions in sets of positive density, emphasizing the connections between the techniques.
Le vendredi 31 mars 2006 / Friday, March 31, 2006
15h45 / 3:45 pm
Le samedi 1er avril 2006 / Saturday, April 1, 2006
9h30 / 9:30 am
Le dimanche 2 avril 2006 / Sunday, April 2, 2006
9h30 / 9:30 am
Pavillon RogerGaudry, Université de Montréal
Salle / Room M415
Le mardi 4 avril 2006 / Tuesday, April 4, 2006
11h00 / 11:00 am
Pavillon J.ArmandBombardier, Université de Montréal
Salle / Room 1035
Conférence dans le cadre de l’Atelier en combinatoire additive
Lectures at the Workshop on Additive Combinatorics
"An Infinitary Approach to (Hyper)graph Regularity and Removal"
The famous Szemeredi regularity lemma gives a structural theorem for very large (but finite) dense graphs, which then has many applications to such graphs, for instance in being able to efficiently eradicate all copies of a given subgraph by edge removal if the original number of such copies was small. These results have been extended to hypergraphs (leading for instance to another proof of Szemeredi's theorem on arithmetic progressions) but the proofs, while elementary and finitary, are somewhat messy and lengthy in nature. Here we present an alternate "infinitary" route to these results, by passing from a sequence of large finite dense deterministic graphs to an infinite dense random graph, and analysing the resulting object instead. The advantage of doing this is that many of the "epsilon" quantities present in the finitary theory go to zero in the infinite limit, and one can now bring techniques from infinitary probability theory (in particular, the theory of conditional independence) to bear on the subject.
Le jeudi 6 avril 2006 / Thursday, April 6, 2006
9h45 / 9:45 am
Pavillon RogerGaudry, Université de Montréal
Salle / Room M415
