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
Some recent results on the integer linear programm
Théorie des graphes
Friday 12 October 2018 - 14h30
Salle : 445 - PCRI-N
Hung Nguyen .............................................

Maximum Independent Set in H-free graphs
Théorie des graphes
Friday 05 October 2018 - 14h30
Salle : 445 - PCRI-N
Edouard BONNET .............................................

A Family of Tractable Graph Distances
Gestion de données du Web
Wednesday 04 July 2018 - 10h30
Salle : 465 - PCRI-N
Stratis Ioannidis .............................................

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

Distributionally Robust Optimization with Principa
Optimisation combinatoire et stochastique
Friday 29 June 2018 - 11h00
Salle : 455 - PCRI-N
Dr. Jianqiang Cheng .............................................