Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GALaC
A counting argument for graph colouring
Francois Pirot

08 October 2021, 11h00
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche : Théorie des graphes

Résumé :
In 2010, Moser and Tardos introduced an algorithmic version of the celebrated Lovász Local Lemma using the entropy compression method. Their method is now widely used in the community and has become a standard of the probabilistic method, mainly because it often provides the tightest existential bounds. However, it suffers from a major drawback ; the proofs requiring entropy compression are often very technical, which makes them hard to understand for the reader.
In this talk, I will present a simple counting argument that can systematically replace entropy compression in its most straightforward uses. The main goal of this talk will be to provide a short proof of the Johansson-Molloy theorem stating that every triangle-free graph of maximum degree Δ has chromatic number at most (1+o(1)) Δ/ln Δ, using that counting argument instead of entropy compression.
Joint work with Eoin Hurley.

Pour en savoir plus :
Séminaires
Pierre Andrieu - Agrégation de classements pour le
Thursday 21 October 2021 - 00h00
Salle : 435 - PCRI-N
.............................................

A counting argument for graph colouring
Théorie des graphes
Friday 08 October 2021 - 11h00
Salle : 445 - PCRI-N
Francois Pirot .............................................

Demographic reconstruction from paleogenomes of th
Thursday 25 February 2021 - 14h00
Salle : 435 - PCRI-N
Nina Marchi .............................................

A Graph-based Similarity Approach to Classify Recu
Thursday 18 February 2021 - 14h00
Salle : 435 - PCRI-N
Coline Gianfrotta .............................................

"Answer Set Programming for computing constraints-
Thursday 04 February 2021 - 14h00
Salle : 435 - PCRI-N
Maxime Mahout .............................................