Journal of Algebraic Combinatorics (EMIS Electronic Version)

Home > Vol 32, No 3 (2010)

On balanced colorings of the n-cube

William Y.C. Chen and Larry X.W. Wang

DOI: 10.1007/s10801-010-0219-7

Abstract

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.

Pages: 379–387

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

Full Text: PDF

References

1. Brenti, F.: Unimodal, log-concave, and Pólya frequency sequences in combinatorics. Mem. Am. Math. Soc. 413, 1-106 (1989)
2. Canfield, E.R., Gao, Z., Greenhill, C., McKay, B.D., Robinson, R.W.: Asymptotic enumeration of correlation-immune Boolean functions.
3. Palmer, E.M., Robinson, R.W.: Enumeration under two representations of the wreath product. Acta Math. 131, 123-143 (1973)
4. Palmer, E.M., Robinson, R.W.: Enumeration of self-dual configurations. Pac. J. Math. 110, 203-221 (1984)
5. Palmer, E.M., Read, R.C., Robinson, R.W.: Balancing the n-cube: A census of colorings. J. Algebr. Comb. 1, 257-273 (1992)
6. Stanley, R.P.: Log-concave and unimodal sequences in algebra, combinatorics and geometry. Ann. N.Y.

	EMIS Electronic Library of Mathematics (ELibM) The Open Access Repository of Mathematics
	JOURNAL OF ALGEBRAIC COMBINATORICS
	Editors-in-chief: C. A. Athanasiadis, T. Lam, A. Munemasa, H. Van Maldeghem ISSN 0925-9899 (print) • ISSN 1572-9192 (electronic)
	Home > Vol 32, No 3 (2010) On balanced colorings of the n-cube William Y.C. Chen and Larry X.W. Wang DOI: 10.1007/s10801-010-0219-7 Abstract 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. Pages: 379–387 Keywords: keywords unimodality; $n$-cube; balanced coloring Full Text: PDF References 1. Brenti, F.: Unimodal, log-concave, and Pólya frequency sequences in combinatorics. Mem. Am. Math. Soc. 413, 1-106 (1989) 2. Canfield, E.R., Gao, Z., Greenhill, C., McKay, B.D., Robinson, R.W.: Asymptotic enumeration of correlation-immune Boolean functions. 3. Palmer, E.M., Robinson, R.W.: Enumeration under two representations of the wreath product. Acta Math. 131, 123-143 (1973) 4. Palmer, E.M., Robinson, R.W.: Enumeration of self-dual configurations. Pac. J. Math. 110, 203-221 (1984) 5. Palmer, E.M., Read, R.C., Robinson, R.W.: Balancing the n-cube: A census of colorings. J. Algebr. Comb. 1, 257-273 (1992) 6. Stanley, R.P.: Log-concave and unimodal sequences in algebra, combinatorics and geometry. Ann. N.Y. © 1992–2009 Journal of Algebraic Combinatorics © 2012 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition

JOURNAL OF ALGEBRAIC COMBINATORICS

On balanced colorings of the n-cube

Abstract

References

JOURNAL OF
ALGEBRAIC
COMBINATORICS