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
Refining Transitive and Pseudo-Transitive Relation
Gestion de données du Web
Monday 24 January 2022 - 13h00
Salle : 455 - PCRI-N
Shuai Wang .............................................

Discovering Causal Rules in Knowledge Graphs using
Intégration de données et de connaissances
Monday 10 January 2022 - 15h00
Salle : 455 - PCRI-N
Lucas Simonne .............................................

Meta-Learning for Few-Shot Link Prediction in Know
Intégration de données et de connaissances
Monday 13 December 2021 - 13h00
Salle : 455 - PCRI-N
Taha Halal .............................................

Knowledge Graph Refinement based on Triplet BERT-N
Gestion de données du Web
Monday 29 November 2021 - 13h00
Salle : 455 - PCRI-N
Armita Khajeh Nassiri .............................................

A Hyper-graph Approach for Computing EL+-Ontology
Raisonnement automatique
Monday 15 November 2021 - 13h00
Salle : 445 - PCRI-N
Hui Yang .............................................