The largest subset that forms a simplex cannot be larger than n+1, and by the Hadamard conjecture these exist for all n=3 mod 4. Here's the construction: Take a Hadamard matrix of order n+1 and flip the sign of each row so that the first element equals 1. Delete the first element in each row and replace -1 with 0. The n+1 rows are then your elements X(n). The Hamming distance between any pair of elements is (n+1)/2; this is the square of the euclidean distance. -Veit On Oct 6, 2012, at 6:30 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Consider the corners of the (say) unit n-cube: {0,1}^n, in R^n.
QUESTION: What is the size |X(n)| of a largest subset X(n) of the 2^n corners, such that all nonzero distances in X(n) have the same value?
The distinct distances are {sqrt(k) | 0 <= k <= n}.
For a fixed k > 0, the number of distances = sqrt(k) is 2^(n-1) * C(n,k), where C(n,k) := n!/(k! (n-k)!).
MORE GENERAL QUESTION: What is the size |X(n,k)| of a largest subset X(k,n) having all its nonzero distances = sqrt(k) ?
(These questions can be rephrased to ask what is the size of the largest clique in the constant-distance graphs for {0,1}^n.)
F'rinstance, in {0,1}^4, the graph of all distances = sqrt(2) has two components. Each is isomorphic to what you get if you connect all pairs of vertices of an octagon (or 3-cube), except antipodes, with an edge. So each component of the graph has 8 vertices and 24 edges. The largest clique has only 4 vertices.
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun