### Disproof of a packing conjecture of Alon and Spencer

- Series
- Combinatorics Seminar
- Time
- Friday, November 17, 2017 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Huseyin Acan – Rutgers University

A 1992 conjecture of Alon and Spencer says, roughly, that the ordinary random graph G_{n,1/2} typically admits a covering of a constant fraction of its edges by edge-disjoint, nearly maximum cliques. We show that this is not the case. The disproof is based on some (partial) understanding of a more basic question: for k ≪ \sqrt{n} and A_1, ..., A_t chosen uniformly and independently from the k-subsets of {1…n}, what can one say about P(|A_i ∩ A_j|≤1 ∀ i≠j)?
Our main concern is trying to understand how closely the answers to this and a related question about matchings follow heuristics gotten by pretending that certain (dependent) choices are made independently. Joint work with Jeff Kahn.