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

[Rob Pratt]

http://oeis.org/A089676

-----Original Message-----
From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Neil Sloane
Sent: Monday, March 28, 2016 10:50 PM
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Subject: [seqfan] Next term after 2,2,4?

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)

--
Seqfan Mailing list - http://list.seqfan.eu/