

A089676


a(n) is the maximal size of a set S of points in {0,1}^n in real ndimensional Euclidean space such that every angle determined by three points in S is acute.


2



1, 2, 2, 4, 5, 6, 8, 9, 10, 16, 17
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Consider the 2^n points {0,1}^n in real Euclidean space. Then a(n) = maximal 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 PQ perpendicular to RQ.
There is an existence proof due to Erdős and Füredi that exponentially large subsets S exist: see for example Theorem 2.3 of Noga Alon's survey "Probabilistic Methods in Extremal Finite Set Theory". This was improved by Bevan and later by Ackerman and BenZwi.
As explained by ErdősFuredi, these sets of points are equivalent to set systems none of which is sandwiched between the intersection and the union of two others. In turn these are equivalent to socalled (2,1)separating systems. As far as I know the best construction is the one in my Israel J. Math. 2013 paper. It uses algebraic geometry and coding techniques, and it implies a lower bound on a(n) of roughly 11^{3n/50}. This is better than ErdősFuredi, Bevan, or AckermanBenZwi, which are all about (4/3)^{n/2}. It is remarkable that this construction beats the probabilistic method (and note that it implies that for large n, naive computer search will have exponentially small chance to find optimal configurations). I should also add that ErdősFuredi claimed (without proof) a lower bound of 2^{n/4} which, if correct, would be even better (but also nonconstructive).  Hugues Randriambololona, Apr 08 2016
For a(10)=17 a combinatorial search algorithm shows that a cubic acute 10set with 18 vertices is not possible. For a complete enumeration of sets with maximal size, see A289972.  Fausto A. C. Cariboni, Jul 17 2017
The best known lower bounds for a(1115) are 24, 32, 33, 64 and 128. a(1114) were found by D. Kamenetsky, while a(15) was found by D. Kamenetsky and V. Chubenko (see attached file). Lower bounds for n > 15 have been found by V. Harangi (see Table 3 in his paper).  Dmitry Kamenetsky, May 18 2018 and Jun 05 2018


LINKS

Table of n, a(n) for n=0..10.
Eyal Ackerman and Oren BenZwi, On sets of points that determine only acute angles, European Journal of Combinatorics 30 (2009) 908910.
N. Alon, Probabilistic Methods in Extremal Finite Set Theory
D. Bevan, Sets of Points Determining Only Acute Angles and Some Related Coloring Problems, Electronic J. of Combinatorics, 13(1), 2006, #R12.
L. Danzer and B. Grünbaum, Uber zwei Probleme bezüglich konvexer Körper von P. Erdős und von K. L. Klee, Math. Zeitschrift 79 (1962) 9599.
P. Erdős and Z. Füredi, The greatest angle among n points in the ddimensional Euclidean space, Annals of Discrete Math. 17 (1983) 275283.
Viktor Harangi, Acute Sets In Euclidean Spaces, Journal on Discrete Mathematics, volume 25, issue 3, (2011) 12121229.
Dmitry Kamenetsky, Lower bounds and their solutions for a(1115)
Math StackExchange, Tight Acute Sets
Hugues Randriambololona, (2,1)Separating systems beyond the probabilistic bound, Israel Journal of Mathematics, 195 (2013), 171186; DOI: 10.1007/s1185601201269.
Hugues Randriambololona, (2,1)Separating systems beyond the probabilistic bound, arXiv:1010.5764 [math.CO], 20102012.


FORMULA

If k <= m <= n, a(k+2m) >= a(k)a(m), a(k+2m+3n) >= a(k)a(m)a(n).
a(n) >= 2*floor((sqrt(6)/9)(2/sqrt(3))^n), which is approximately 0.544*1.155^n.


EXAMPLE

a(3) = 4: {000, 011, 101, 110}.
a(4) = 5: {0011, 0101, 0110, 1000, 1111}.
The following sets are given by Bevan (2006), who also shows they are optimal:
a(5) = 6:
0 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 1 0 0 1
1 0 0 0 1
1 1 1 1 0
a(6) = 8:
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
0 1 1 1 1 0
1 0 1 0 1 0
1 0 1 1 0 1
1 1 0 0 1 1
1 1 0 1 0 0
a(7) = 9:
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 1 1 0 1
0 1 1 0 0 0 1
0 1 1 1 1 1 0
1 0 1 0 1 0 1
1 0 1 1 0 1 0
1 1 0 0 1 1 0
1 1 0 1 0 0 1
a(8) = 10:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 1 1 0 0 1
0 1 1 0 0 0 0 1
0 1 1 1 1 1 1 0
1 0 1 0 1 0 0 1
1 0 1 1 0 1 1 0
1 1 0 0 1 1 1 0
1 1 0 1 0 0 0 1
For a(9) = 16 Bevan uses the construction in his Theorem 4.2, which shows that a(3k) >= a(k)^2 for all k, and then a computer search shows that this is optimal for k = 3. Let v0,v1,v2,v3 denote the four vectors for a(3). Then to get a(9)=16 use the vectors { v_i v_j v_{ji mod 4}, 0 <= i,j <= 3 }.  N. J. A. Sloane, Mar 30 2016
a(10) = 17, from Hugues Randriambololona, Apr 08 2016:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 1 1 1
1 1 1 0 1 1 1 0 0 1
0 0 1 0 0 1 1 1 0 1
1 1 0 0 0 1 0 1 0 1
1 1 0 0 1 0 1 1 1 1
0 1 0 1 1 0 0 1 0 0
1 1 1 0 0 0 0 0 1 1
1 0 0 1 1 1 1 0 1 1
1 0 1 0 1 1 0 0 1 0
0 1 0 1 0 1 1 0 0 0
1 0 0 0 0 1 1 1 1 0
1 0 1 0 1 0 1 1 0 0
1 0 1 1 0 0 1 1 1 1
1 1 1 1 0 1 0 1 1 0
0 1 1 0 1 1 1 1 1 0
1 0 1 1 1 1 0 1 0 1
a(11) >= 23, from Dmitry Kamenetsky, Jan 05 2018:
0 1 1 0 0 0 1 0 1 1 1
0 0 0 0 1 0 0 0 0 0 1
0 0 1 1 0 0 1 0 0 0 1
0 1 1 0 1 0 1 1 1 0 0
0 0 1 0 1 1 0 0 1 1 1
1 1 0 1 1 0 0 0 1 1 0
1 0 0 1 1 0 0 1 0 1 1
1 0 0 1 0 1 1 0 1 1 0
1 1 1 1 1 1 0 0 0 0 0
1 0 0 1 1 1 1 1 1 0 1
1 0 1 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 1 1 1 1
0 1 0 0 1 0 1 0 0 1 0
1 1 0 0 0 0 0 0 1 0 1
1 1 1 0 0 1 1 1 0 1 1
1 1 0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 1 1 0 1 0
1 0 1 1 1 1 1 0 0 1 1
1 1 1 1 0 0 0 1 0 0 1
0 1 1 1 0 0 0 1 1 1 0
0 1 1 0 1 1 0 1 0 1 0
0 0 0 0 0 1 0 1 0 0 0
0 1 0 1 0 1 0 0 0 0 1


CROSSREFS

Cf. A289972.
Sequence in context: A244017 A071528 A056902 * A230059 A302486 A266745
Adjacent sequences: A089673 A089674 A089675 * A089677 A089678 A089679


KEYWORD

nonn,more,nice


AUTHOR

David Bevan, Jan 06 2004


EXTENSIONS

Edited by N. J. A. Sloane, Mar 29 2016 and Apr 08 2016
a(10) from Fausto A. C. Cariboni, Jul 17 2017


STATUS

approved



