Fiches de cours 2017-2018

PDF
 

Combinatorial geometry

MATH-402

Enseignant(s) :

Pach János

Langue:

English

Summary

Can we plant n trees in an orchard, not all along the same line, so that every line determined by two trees will pass through a third? This was raised by Sylvester and has generated interest among mathematicians. It led to the birth of combinatorial geometry with ties to convexity and graph theory.

Content

The course offers an introduction to this rapidly developing field, where combinatorial and probabilistic (counting) methods play a crucial role.

Topics: Extremal graph theory, Repeated distances in space, Arrangements of lines and curves, Geometric graphs, Epsilon nets, Discrepancy theory, Applications in computational geometry.

Keywords

forbidden graph, hypergraph, incidence, arrangement, Vapnik-Chervonenkis dimension, random sampling

Learning Prerequisites

Required courses

Discrete Mathematics

Recommended courses

Probability Theory

Important concepts to start the course

graph, planar graph, random variable, expected value, variance

Teaching methods

Lectures, exercises

Expected student activities

Solving homework problems, answering questions during lecture and exercise sessions

Supervision

Office hours Yes
Assistants Yes

Resources

Bibliography

J. Pach and P. Agarwal: Combinatorial Geometry,
J. Matousek: Lectures on Discrete Geometry

Ressources en bibliothèque

Dans les plans d'études

Semaine de référence

 LuMaMeJeVe
8-9    BS260
9-10    
10-11    BS260
11-12    
12-13     
13-14     
14-15     
15-16     
16-17     
17-18     
18-19     
19-20     
20-21     
21-22     
 
      Cours
      Exercice, TP
      Projet, autre

légende

  • Semestre d'automne
  • Session d'hiver
  • Semestre de printemps
  • Session d'été
  • Cours en français
  • Cours en anglais
  • Cours en allemand