Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GraphComb
Independent dominating sets in graphs by the semi-random method
Ararat Harutyunyan

08 February 2013, 10h30 - 08 February 2013, 11h30
Salle/Bat : 475/PCRI-N
Contact : Ararat.Harutyunyan@lri.fr

Activités de recherche :

Résumé :
One of the most powerful tools in probabilistic combinatorics is the semi-random method where one uses a randomized algorithm to incrementally construct an object with a particular desirable property. Used by V. Rodl (1985) to prove the Erdos-Hanani conjecture, the technique as been used to derive many fundamental results in discrete mathematics in the last two decades. We will first introduce the basic method and briefly discuss some of these results. The second half of the talk will be devoted to the presentation of a recent application of the method, which proves the existence of independent dominating sets of size at most O(n log d / d) in n-vertex d-regular graphs of girth five. We show that the bound is asymptotically optimal, and that the regularity and girth conditions essentially cannot be relaxed. Joint work with Paul Horn and Jacques Verstraete.

Pour en savoir plus :
Séminaires
Programmation mathématique multi-objectif pour la
Thursday 13 December 2018 - 14h30
Salle : unknown - unknown
Audrey Legendre .............................................

Redundancy in Distributed Proofs
Algorithmique distribuée
Tuesday 04 December 2018 - 00h00
Salle : 465 - PCRI-N
Ami Paz .............................................

Some recent results on the integer linear programm
Théorie des graphes
Friday 30 November 2018 - 00h00
Salle : 445 - PCRI-N
Hung Nguyen .............................................

Scalable and exhaustive screening of metabolic fun
Wednesday 28 November 2018 - 11h00
Salle : 465 - PCRI-N
Clémence Frioux .............................................

Studying the three-dimensional structure of DNA fr
Thursday 22 November 2018 - 15h00
Salle : unknown - unknown
Nelle Varoquaux .............................................