Disproof of a packing conjecture of Alon and Spencer. Issue 3 (29th July 2019)

• Record Type: Journal Article
• Authors: Acan, Hüseyin; Kahn, Jeff
• Is Part Of: Random structures & algorithms. Volume 55:Issue 3(2019)
• Page Start: 531
• Page End: 544
• Publication Date: 2019-07-29
• Subjects: edge‐disjoint cliques -- hypergraph matchings -- random graph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20884
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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 ≪ 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.