Forbidden vector-valued intersections

Author: 

Keevash, P
Long, E

Publication Date: 

2 May 2020

Journal: 

Proceedings of the London Mathematical Society

Last Updated: 

2021-03-17T01:28:25.583+00:00

Issue: 

3

Volume: 

121

DOI: 

10.1112/plms.12338

page: 

702-742

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\"odl 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.

Symplectic id: 

701182

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article