The ACO Seminar (2014–2015)

We give an almost complete description of matrices M_n of real entries under which the hypercube H_n={-1,1}ⁿ is nearly invariant: that is when the intersection set {Mx, x ∈ H_n} ∩ H_n has size close to 2ⁿ. In application, we show that if in addition M_n is orthogonal, then it must be close to a product of permutation and reflection matrices.