Location: Hill 705
Date & time: Monday, 17 October 2016 at 2:00PM -
"Maximum number of edge-disjoint and almost-largest cliques in a random graph"
|Time: 2:00 PM|
|Location: Hill 705|
|Abstract: Let omega be the clique number of the Erdos-Renyi graph G(n,1/2). It is known that omega is asymptotically 2log_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^2log(k)/k^4). Joint with Jeff Kahn.|