Counting Gray codes for an improved upper bound of the Grünbaum-Hadwiger-Ramos problem

Abstract

We give an improved upper bound for the Grünbaum--Hadwiger--Ramos problem: Let $d,n,k\in \mathbb{N}$ such that $d\ge 2^n(1+2^{k-1})$. Given $2^{n+1}$ masses on ${\mathbb{R}}^d$, there exist $k$ hyperplanes in ${\mathbb{R}}^d$ that partition it into $2^k$ sets of equal size with respect to all measures. This is an improvement to the previous bound $d\ge 2^{n+k}$ by Mani-Levitska, Vrećica & Živaljević in 2006. This is achieved by classifying the number of certain Gray code patterns modulo 2. The reduction was developed by Blagojević, Frick, Haase & Ziegler in 2016. It utilizes the group action of the symmetric group $(\mathbb{Z}/2{)}^k⋊{\mathfrak{S}}_k$ of $k$ oriented hyperplanes. If we restrict to the subgroup $(\mathbb{Z}/2{)}^k$ as Mani-Levitska et al. we retrieve their bound.

16 pages