Maximum number of edge-disjoint and almost-largest cliques in a random graph
Location: Hill 705
Date & time: Monday, 17 October 2016 at 2:00PM - 2:11PM
Huseyin Acan, Rutgers: Let \omega be the clique number of the Erdos-Renyi graph G(n,1~2). It is known that \omega is asymptotically 2\log_2(n) and it is concentrated on two values (in most cases on just one value). For k=\omega-4, Bollobas showed that, in G(n,1~2), the expected value of the size of a largest family of edge-disjoint k-cliques is at least (1+o(1))n^2~k^4. Later, Alon and Spencer conjectured that it is at least cn^2~k^2 for some constant c>0. We disprove the conjecture of Alon and Spencer by showing that this expectation is O(n^2~k^3). We also improve the lower bound to \Omega(n^2\log(k)~k^4).Joint with Jeff Kahn.