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
Heterogeneous Treatment Effects Estimation: When M
Raisonnement automatique
Thursday 02 June 2022 - 10h30
Salle : 2011 - DIG-Moulon
Naoufal Acharki .............................................

Witness Generation for JSON Schema
Langages et systèmes centrés données
Monday 30 May 2022 - 00h00
Salle : 455 - PCRI-N
Mohamed-Amine BAAZIZI .............................................

TUTORIAL CODALAB - Apprenez à organiser un challen
Wednesday 13 April 2022 - 00h00
Salle : 1 - DIG-Moulon
Adrien Pavao .............................................

Generative Neural Networks for Observational Causa
Raisonnement automatique
Thursday 07 April 2022 - 10h30
Salle : 2011 - DIG-Moulon
Diviyan Kalainathan .............................................

Datamining in Epi- and Phylogenetics
Tuesday 15 March 2022 - 11h00
Salle : 455 - PCRI-N
Thomas Haschka .............................................