Premium
Forbidden vector‐valued intersections
Author(s) -
Keevash Peter,
Long Eoin
Publication year - 2020
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms.12338
Subject(s) - mathematics , conjecture , combinatorics , statement (logic) , intersection (aeronautics) , dimension (graph theory) , product (mathematics) , entropy (arrow of time) , set (abstract data type) , discrete mathematics , computer science , law , physics , geometry , engineering , quantum mechanics , political science , programming language , aerospace engineering
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.