Le séminaire a lieu les jeudis de 10:45–11:45 en salle de séminaires IRMA. La fréquence est variable. Les exposés commencent à 10:45, durent 60 minutes et sont suivies de questions.

Sauf mention explicite, le lien pour accès en distanciel par visio sera https://bbb.unistra.fr/b/xia-d9z-u7n. Et le lien pour le café virtuel https://gather.town/app/9KMzSyMpZIZOx8CO/semsto.

Prochain exposé du séminaire stochastique (Attention: le programme est régulièrement enrichi ou modifié):

Le 18-08-2022 à 10:45:00 dans la Salle de séminaires IRMA
Mikhail Isaev (Monash University)

The expected number of spanning trees in random graphs with given degrees


We consider a uniformly chosen random labelled graph G with n vertices and given degree sequence dvec = (d_1, d_2, ..., d_n). We derive asymptotic formulas for the expected number of spanning trees tau(G). This graph parameter is also known as the complexity of G and has connections to a wide range of topics, including the study of electrical networks, algebraic graph theory, statistical physics and number theory.<br /> <br /> <br /> Our proofs are based on known asymptotic enumeration results of graphs with specified substructures and degrees. The main difficulty is estimating the average of exp(F(dvec, T)) over all trees on n vertices. The function F(dvec,T) is too large to allow any useful expansion of the exponential. We do this by applying the theory of exponentials of martingales. Our martingale construction is based on the Pruffer code. As an intermediate step, we derive an exact explicit formula for substructures occurrences probabilities in a random tree which appears to be new and of independent interest.<br /> <br /> <br /> The talk is based on the following two papers.<br /> [1] C. Greenhill, M. Isaev, M. Kwan, B.D. McKay, The average number of spanning trees in sparse graphs with given degrees, European J. Combin,<br /> 63 (2017), 6-25.<br /> <br /> [2] C. Greenhill, M. Isaev, B.D. McKay, Subgraph counts for dense random graphs with specified degrees, Combinatorics, Probability and Computing<br /> 30 (3) (2021), 460-497.

Exposés à venir Listes des exposés depuis 1999

Informations pour les orateurs / Information for speakers

A propos du séminaire / About the seminar