Title:Maximum Number of Edge-Disjoint and Almost-Largest Cliques in A Random Graph
Speaker: Huseyin Acan, Rutgers University
Date: Monday, October 17, 2016 2:00 pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
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.