Forbidden vector‐valued intersections. Issue 3 (2nd May 2020)

• Record Type: Journal Article
• Authors: Keevash, Peter; Long, Eoin
• Is Part Of: Proceedings of the London Mathematical Society. Volume 121:Issue 3(2020)
• Page Start: 702
• Page End: 742
• Publication Date: 2020-05-02
• Subjects: 05D05 (primary) -- 05D40 -- 52C10 (secondary); Mathematics -- Periodicals; Mathematics; Periodicals; 510
• DOI: 10.1112/plms.12338
• Languages: English
• ISSNs: 0024-6115

Abstract

Abstract: We solve a generalised form of a conjecture of Kalai motivated by attempts to improve the bounds for Borsuk's problem. The conjecture can be roughly understood as asking for an analogue of the Frankl–Rödl forbidden intersection theorem in which set intersections are vector‐valued. We discover that the vector world is richer in surprising ways: in particular, Kalai's conjecture is false, but we prove a corrected statement that is essentially best possible, and applies to a considerably more general setting. Our methods include the use of maximum entropy measures, VC‐dimension, dependent random choice and a new correlation inequality for product measures.