This is a collaborative project between the research groups of Stefan Langerman (Université Libre de Bruxelles) and Luc Devroye (McGill University, Montreal) to study coloring problems on geometric graphs and hypergraphs when points are randomly placed in Euclidean space.

French résumé. Étant donné un ensemble de points dans le plan, est-il possible de les colorier avec k couleurs de telle façon que tout disque unitaire contenant au moins 100k points contienne toutes les couleurs? Ce type de question, simple à énoncer mais à ce jour non résolu, sera le point focal de ce projet. De manière plus formelle, on définit la structure combinatoire d'un tel problème sous forme d'un hypergraphe géométrique pour en èxtraire les propriétés les plus fondamentales. La diversité des applications de ces hypergraphes est trop grande que pour les décrire exhaustivement. On y compte la dérandomisation, la géométrie algorithmique et combinatoire, les recherches régionales, la théorie de l'apprentissage, la biologie moléculaire et les réseaux de senseurs. Par exemple le problème énoncé ci-dessus peut servir à modéliser une allocation de fréquences où les points représentent des antennes radio et le disque représente la puissance d'un récepteur. Le but de ce projet sera d'étudier des problèmes de coloriages d'hypergraphes géométriques dans le cas où les points sont placés suivant une probabilité de distribution donnée.

Principal funding support comes from Luc Devroye's NSERC Discovery Grant, and Stefan Langerman's FNRS Grant.

By email: stefan.langerman@ulb.ac.be, lucdevroye@gmail.com.

Mailing address: School of Computer Science, McGill University, 3480 University Street, Montreal, Canada H3A 2A7.

Start. Preliminary discussions took place between May and August 2009. Progress was made, with Nicolas Broutin, on the problem of height of a random simplex tree on deterministic point sets in d-dimensional space. The conjecture that the height is not more than for the random binary search tree is false for d equal to four and above, and it is likely, but unproven, that it is also false for dimensions two and three.

Next meeting. Working meetings took place in March 2010 in Montreal, and June 2010 in Brussels.

Luc Devroye's group includes Erin McLeish, Jamie King, Nicolas Fraiman, and Omar Fawzi.