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

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

Activités de recherche : Graph Theory

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
Knowledge Graph Refinement based on Triplet BERT-N
Web data management
Monday 29 November 2021 - 13:00
Salle : 455 - PCRI-N
Armita Khajeh Nassiri .............................................

A Hyper-graph Approach for Computing EL+-Ontology
Automated Reasoning
Monday 15 November 2021 - 13:00
Salle : 445 - PCRI-N
Hui Yang .............................................

Semantic approaches to predict the presence of asb
Integration of Data and Knowledge
Monday 08 November 2021 - 13:00
Salle : 455 - PCRI-N
Thamer Mecharnia .............................................

Pierre Andrieu - Agrégation de classements pour le
Thursday 21 October 2021 - 00:00
Salle : 435 - PCRI-N
.............................................

A counting argument for graph colouring
Graph Theory
Friday 08 October 2021 - 11:00
Salle : 445 - PCRI-N
Francois Pirot .............................................