moteur de recherche

Séminaire Algo - Sergey Dovgal
Séminaire Algo - Sergey Dovgal
30-Mar-2021 14:00
Age: 78 days





Sergey Dovgal

A survey: generating functions of graphs, directed graphs and 2-SAT

Zoom (if you want to participate, please request the meeting password. If your interest in the seminar is more general, you can request to be added to the announcement mailing list which will contain the password for each meeting)

Abstract : When the "average degree" of a random graph, directed graph or a 2-CNF formula stays, respectively, below or above 1, the structural picture of these objects is, with high probability, totally different. The change in this picture is often referred to as the phase transition. The gold standard approach in the study of the related probabilities and distributions is first to construct the generating functions of the families appearing with high probability, and second, to carry out the asymptotic analysis of their coefficients to see how these probabilities transition from 1 to 0. In this survey, I will take you a dive into the realm of four worlds of generating functions to discover the gems of

 

  1. subcritical graphs ([Wright '1970], [Janson, Knuth, Luczak, Pittel '1993])
  2. supercritical graphs ([De Panafieu '2016+] [De Panafieu, D., Singh '2021+])
  3. directed graphs ([Liskovets et al ~'1970] [De Panafieu, D. et al ~2020])
  4. 2-SAT ([De Panafieu, D., Ravelomanana 2021+])

 

We are going to touch the corals of the asymptotic analysis  very briefly just to see their current state of the development.

This survey includes the results obtained with Élie De Panafieu, Dimbinaina Ralaivaosaona, Vonjy Rasendrahasina, Vlady Ravelomanana, Alexandros Singh and Stephan Wagner.








<- Back to: Accueil