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
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 .............................................

Caractérisation de réseaux égocentrés par l'énumér
Friday 15 June 2018 - 14h30
Salle : 455 - PCRI-N
Raphaël Charbey .............................................

DATA VERACITY ASSESSMENT: HOW A-PRIORI KNOWLEDGE E
Intégration de données et de connaissances
Friday 15 June 2018 - 14h00
Salle : 445 - PCRI-N
Valentina Beretta .............................................

Model Based Software and Data Integration (MBSDI)
Intégration de données et de connaissances
Tuesday 05 June 2018 - 15h00
Salle : 435 - PCRI-N
Dr. Ralf-Detlef Kutsche .............................................