Une surprenante symétrie pour le greedy independent set sur les arbres de Cayley.
1 : Laboratoire de Mathématiques dÓrsay
Université Paris-Saclay
Nous prouvons que la taille $G_n$ du greedy independent set sur un arbre de Cayley uniforme a (presque) la même loi que la taille de son complémentaire. En particulier, nous montrerons que $G_n$ a la même loi que le nombre de sommets à hauteur paire dans un arbre de Cayley. Nous montrerons aussi comment explorer $G_n$ de façon markovienne.
| Type : | : | Résumé |
| Thématiques | : | Probabilités discrètes et mécanique statistique |
| PDF version | : |  PDF version |
