Séminaires : Séminaire Francilien de Géométrie Algorithmique et Combinatoire

Equipe(s) : co,
Responsables :Arnaud de Mesmay, Alfredo Hubard et Arnau Padrol
Email des responsables : arnau.padrol@imj-prg.fr
Salle :
Adresse :IHP
Description

Le Séminaire de Géométrie Algorithmique et Combinatoire vise à regrouper des exposés dans ce domaine au sens le plus large, et dans les disciplines connexes en mathématiques et informatique. Il est ouvert à tous les chercheurs et étudiants intéressés. Les exposés sont destinés à un public large.


Orateur(s) János Pach - (Bézout chair),
Titre Strings and Order
Date07/11/2019
Horaire14:00 à 15:00
Diffusion
Résume

Let $\omega(G)$ and $\chi(G)$ denote the clique number and chromatic number of a graph $G$, respectively.  The disjointness graph of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called $x$-monotone if every vertical line intersects it in at most one point.

We solve a 25 years old problem by showing that for arbitrarily large integers $k$, there exist families of $x$-monotone curves such that their disjointness graphs $G$ satisfy $\omega(G)=k$ and $\chi(G)=\Omega(k^4)$.  This bound is asymptotically tight.

If we drop the condition that the curves are $x$-monotone, then $\chi(G)$ cannot be bounded in terms of $k$. We construct, for every $g>3$, families of $n$ curves such that the girth of their disjointness graphs $G$ is at least $g$ and $\chi(G)=\Omega_g(\log n)$. This improves a result of Bollobás. Joint work with István Tomon.

Salle
AdresseIHP
© IMJ-PRG