Linear separability

[Alberto Ibaqez Rodrmguez]

About a couple of months ago we sent a question to the list concerning the 
existence of a fast method to determine whether two subsets of the set of 
vertices of a hypercube are linerly separable (every vertex in the 
hypercube falls in one of the subsets).

Most of the mails that were sent dealt with linear programing, perceptrons 
and some of them about the Walsh transform, convex polytopes or k-
summability.

Thank you to everyone for the interest and for dedicating time to  
that interesting discussion.

The question arised from a simple method we arrived at, which looks like it
works. However, we have not been able to prove that it will keep
working in high dimension hypercubes.

The idea is as follows:

A subset of vertices (as defined formerly) is linearly separable from the 
other iff there exists a hyperplane perpendicular to the  segment that joins 
the barycentres of the subsets in which the hypercube has been divided.
 
If this proposition is correct, we can project every point in the subsets on 
this segment and find out if both sets of projections are separated. If so, 
the hyperplane equation can easily be calculated.


We would appreciate any comments and especially if someone finds out how to
prove or disprove it.

Thank you very much

Alberto Ibaqez et al.