Séminaire d'équipe(s) Graph Theory and Combinatorial Optimization
Independent dominating sets in graphs by the semi-random method
Ararat Harutyunyan
08 February 2013, 10:30 - 08 February 2013, 11:30 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.
