Forbidden vector-valued intersections

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • University of Oxford

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.

Details

Original languageEnglish
Pages (from-to)702–742
Number of pages41
JournalProceedings of the London Mathematical Society
Volume121
Issue number3
Publication statusPublished - 2 May 2020

Keywords

  • extremal set theory, intersection theorems