Dept Banner
Dept Banner


Download as iCal file

Discrete Math

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530