|
Abstract |
Les graphes de Barak-Erdös sont une version orientée acyclique des graphes
aléatoires d'Erdös-Rényi : l'ensemble des sommets est {1,...,n} et pour
tout i<j, avec probabilité p on ajoute une arête orientée de i vers j,
indépendamment pour chaque paire i<j. La longueur du plus long chemin des
graphes de Barak-Erdös croît linéairement avec le nombre de sommets et le
taux de croissance C(p) est une fonction de la probabilité p de présence
d'une arête.
Foss et Konstantopoulos ont introduit un couplage entre les graphes de
Barak-Erdös et un cas particulier d'un système de particules en
interaction appelé modèle infini d'urnes. En utilisant ce couplage, nous
verrons que C(p) est analytique pour p>0 et dérivable une fois mais pas
deux en p=0. Nous verrons également que les coefficients du développement
en série entière de C(p) autour de p=1 sont entiers, suggérant que C(p)
est la fonction génératrice d'une classe d'objets combinatoires.
|
