Newsgroups: sci.math
From: hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: Mon, 27 Dec 1993 17:23:57 GMT
Subject: Re: unequal halves

Two weeks ago k...@spdcc.com (Karl Heuer) asked:

> Can the vertices of the n-cube (n >= 1) be partitioned into two
> equal-sized subsets which are not congruent to each other?

Not for n=1,2,3, but yes for n>=4.  For n=4, labelling the vertices by
binary coordinates:

  0000--0010--0011              1000--1010--1110
   |     |     |                 |     |
  0100--0110--0111        1101--1001--1011
   |           |           |     |
  1100        1111        0101--0001

The adjacency graphs are not even isomorphic.  Also, the former
contains a square of diagonal 2 (0000,0011,1111,1100) while the
rectangle of diagonal 2 in the latter is 1 by sqrt(3)
(0001,0101,1110,1010).

I (not extremely carefully) enumerated the ways of partitioning the
vertices of the 4-cube into connected 8-point subsets, and counted
that four of the twenty-four partitions were into non-congruent parts.

I suspect that the partitions into congruent parts become
asymptotically scarce, but I haven't figured out how to prove it.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil