On balanced colorings of the $n$-cube

Chen, William Y.C. ; Wang, Larry X.W.

Journal of Algebraic Combinatorics, Tome 32 (2010) no. 3, pp. 379-387.

Résumé

Summary: A 2-coloring of the $n$-cube in the $n$-dimensional Euclidean space can be considered as an assignment of weights of 1 or 0 to the vertices. Such a colored $n$-cube is said to be balanced if its center of mass coincides with its geometric center. Let $B _{ n,2 k }$ be the number of balanced 2-colorings of the $n$-cube with $2 k$ vertices having weight 1. Palmer, Read, and Robinson conjectured that for $n\geq 1$, the sequence ${ B _{ n,2 k}} _{ k=0,1, \frac{1}{4} ,2 $^ n -1 {B_n,2k}_k=0,1,ldots,2^n-1 is symmetric and unimodal. We give a proof of this conjecture. We also propose a conjecture on the log-concavity of $B _{ n,2 k }$ for fixed $k$, and by probabilistic method we show that it holds when $n$ is sufficiently large.

Détail

Keywords: keywords unimodality, $n$-cube, balanced coloring