Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 27 novembre 2018 à 14h00 en B107, Wenjie Fang nous parlera de : Hypergraphes aléatoires sous-critiques, composantes d'ordre supérieur et hyperarbres

Résumé : Dans le modèle de graphe aléatoire d'Erdős–Rényi $G(n,p)$, l'émergence de la composante géante se situe à la fenêtre $p=n^{-1}+O(n^{-4/3})$. Lorsque $p$ varie de $(1-\epsilon)n^{-1}$ (sous-critique) à $n^{-1}$, puis à $(1+\epsilon)n^{-1}$, la plus grande composante varie de $O(\epsilon^{-2}\log(n\epsilon^3))$ à $\Theta(n^{2/3})$, puis $(1+o(1)) 2 \epsilon n$. Nous considérons une généralisation de $G(n,p)$ sur les hypergraphes k-uniformes, avec une notion de connexité d'ordre supérieur. Plus précisément, pour $1 \leq j < k$, considérons les ensembles de j sommets, appelés les j-ensembles. Deux j-ensembles sont j-connexes s'il existe entre eux un chemin d'hyperarêtes dont l'intersection de deux hyperarêtes consécutives contient au moins $j$ sommets. Une composante j-connexe est une famille maximale de j-ensembles qui sont j-connexes l'un à l'autre. Sous cette notion de j-connexité, nous avons déterminé, dans un régime sous-critique, la taille précise des $m$ plus grandes composantes j-connexes, et aussi leur structure. C'est un travail joint avec Oliver Cooley, Nicola Del Giudice et Mihyun Kang.


Dernière modification : Tuesday 23 October 2018 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr