Hou Tin Chau

Iterated shadows in the hypercube

Let n be an even integer, and let A be a family of (n/2)-element subsets of {1,2,...,n}, i.e., A is a subset of the middle layer of the n-dimensional hypercube. The rth iterated upper shadow of A is the family of all (n/2+r)-element subsets T of {1,2,...,n} such that T is a superset of S for some S in A (so it is a subset of the (n/2+r)th layer of the hypercube). The classical Kruskal-Katona theorem implies that, for A of measure ½, the measure (or density) of the rth iterated upper shadow of A is minimised by taking A to be an initial segment of the lexicographical ordering, and in this case one needs to go up r = Ω(n) layers for the upper shadow to get an Ω(1) density-increase in the (n/2+r)-th layer. Friedgut conjectured that, if A has measure ½ and we consider both A its complement A^c in the middle layer, then for every ε>0, going up only r = ⌈ε√n⌉ layers already guarantees that one of the upper shadows of A and A^c has an Ω_ε (1) density-increase, for sufficiently large n. We will outline a proof of this conjecture. We use the FKG inequality, together with a random restriction argument and a lemma saying that certain Johnson graphs have spectral gap uniformly bounded from below (we prove the latter by adapting a recently-introduced technique of Koshelev). Joint work with David Ellis and Marius Tiba.