[seqfan] Next term after 2,2,4?

Neil Sloane njasloane at gmail.com
Tue Mar 29 04:50:11 CEST 2016


Consider the 2^n points {0,1}^n in real Euclidean space.
Let a(n) = max size of a subset S of these 2^n points
such that there is no triple of points P,Q,R in S which subtends a
right angle.  That is, we are not allowed to have P-Q perpendicular to R-Q.

Then a(1)=2 (use 0, 1),
a(2)=2 (use 00, 11),
and a(3)=4 (use 000, 011,101,110, which forms a tetrahedron
and so does not contain a right angle).
If I had a couple more terms I could look it up!

It is a bit like A003432, but different.

There is an existence proof due to Erdos and Furedi that
exponentially large subsets S exist, see for example theorem 2.3
of Noga Alon's survey Probabilistic Methods in Extremal Finite Set Theory
(http://www.tau.ac.il/~nogaa/PDFS/set3.pdf)



More information about the SeqFan mailing list