Date/heure
12 février 2026
10:45 - 11:45
Lieu
Salle de conférences Nancy
Oratrice ou orateur
Leticia Mattos (Heidelberg)
Catégorie d'évènement Séminaire Probabilités et Statistique
Résumé
We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erdős-Rényi random graph $G(n,p)$. Recently Acan and Kahn showed that the largest such family contains only $O(n^2/(\log{n})^3)$ cliques, with high probability, which disproved a conjecture of Alon and Spencer. We prove the corresponding lower bound, $\Omega(n^2/(\log{n})^3)$, by considering a random graph process which sequentially selects and deletes near-maximal cliques. The main tool in our analysis is the so-called Differential Equation Method. This is a joint work with Simon Griffiths.