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
A Two-level Auction for Resource Allocation in Mul
Réseaux sans fil et mobiles
Friday 09 March 2018 - 14h30
Salle : 445 - PCRI-N
Mira Morcos .............................................

Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 09 February 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Approximate Bayesian Computation and Random Forest
Thursday 08 February 2018 - 00h00
Salle : 455 - PCRI-N
Valentin Thouzeau .............................................

A concurrent lock-free algorithm for computing a f
Combinatoire
Friday 12 January 2018 - 14h30
Salle : 445 - PCRI-N
James Mitchell .............................................

Acyclic Partitioning of Large Directed Acyclic Gra
Calcul à haute performance
Tuesday 09 January 2018 - 10h30
Salle : 465 - PCRI-N
Julien Herrmann .............................................