Peter Keevash and Eoin Long: Forbidden vector-valued intersections

Peter Keevash and Eoin Long arxived some time ago a very nice paper:  Forbidden vector-valued intersections, which settled a problem that was first posed here on the blog. Here is the 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.

Actually, the original motivation for the problem was related to the cap-set problem. (Item 19 in the third post on the cap-set problem and the Frankl-Rodl’s theorem).  In 2009 I wrote three posts (A, B, C) with some ideas on connections between the cap-set problem and Frankl-Wilson/Frankl-Rodl’s theorem. The first post also dicusses various ways in which Frankl-Rodl’s theorem is more general than Frankl-Wilson.

Other related posts and papers:  Frankl-Wilson theorem; A 2014 paper by Keevash and Long Frankl-Rödl type theorems for codes and permutations;  Posts (I, II) on the startling solution of the cap-set prolems following the works of Croot, Lev, Pach, Ellenberg, and Gijswijt.