Hypercube orientations with only two in-degrees

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:118

Article

Buhler, Joe¹  Butler, Steve²  Graham, Ron³  Tressler, Eric⁴ 

[1] Ctr Commun Res, La Jolla, CA 92121 USA

[2] Univ Calif Los Angeles, Dept Math, Los Angeles, CA 90095 USA

[3] Univ Calif San Diego, Dept Comp Sci & Engn, La Jolla, CA 92093 USA

[4] HRL Labs LLC, Malibu, CA 90265 USA

关键词: Hypercube;    Orientations;    Hamming balls;    Hat guessing strategies;   

DOI  :  10.1016/j.jcta.2011.02.003

来源: Elsevier

【 摘 要 】

We consider the problem of orienting the edges of the n-dimensional hypercube so only two different in-degrees a and b occur. We show that this can be done, for two specified in-degrees, if and only if obvious necessary conditions hold. Namely, we need 0 <= a, b <= n and also there exist non-negative integers s and t so that s + t = 2(n) and as + bt=n2(n-1). This is connected to a question arising from constructing a strategy for a hat puzzle. (C) 2011 Elsevier Inc. All rights reserved.

【 授权许可】

Free