General Events - Department of Mathematics

View Full Calendar

Graph Theory and Combinatorics Seminar: Clique packings in random graphs

Event Type
Seminar/Symposium
Sponsor
N/A
Location
Zoom
Date
Oct 12, 2021   1:00 pm  
Speaker
Leticia Mattos (Instituto de Matemática Pura e Aplicada)
Views
20

Let u(n,p,k) be the k-clique packing number of the random graph G(n,p), that is, the maximum number of edge-disjoint k-cliques in G(n,p). In 1992, Alon and Spencer conjectured that for p = 1/2 we have u(n,p,k) = Ω(n²/k²) when k = k(n,p) - 4, where k(n,p) is minimum t such that the expected number of t-cliques in G(n,p) is less than 1. This conjecture was disproved a few years ago by Acan and Kahn, who showed that in fact u(n,p,k) = O(n²/k³) with high probability, for any fixed p ∈ (0,1) and k = k(n,p) - O(1).

In this talk, we show a lower bound which matches Acan and Kahn's upper bound on u(n,p,k) for all p ∈ (0,1) and k < k(n,p) - 3. To prove this result, we follow a random greedy process and use the differential equation method. This is a joint work with Simon Griffiths and Rob Morris. 

Contact Sean at SEnglish (at) illinois (dot) edu for Zoom information.

link for robots only