The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A089676 a(n) is the maximal size of a set S of points in {0,1}^n in real n-dimensional 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 P-Q perpendicular to R-Q. 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 Ben-Zwi. As explained by Erdős-Furedi, 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 so-called (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ős-Furedi, Bevan, or Ackerman-Ben-Zwi, 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ős-Furedi claimed (without proof) a lower bound of 2^{n/4} which, if correct, would be even better (but also non-constructive). - Hugues Randriambololona, Apr 08 2016 For a(10)=17 a combinatorial search algorithm shows that a cubic acute 10-set 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(11-15) are 24, 32, 33, 64 and 128. a(11-14) 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 Eyal Ackerman and Oren Ben-Zwi, On sets of points that determine only acute angles, European Journal of Combinatorics 30 (2009) 908-910. 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) 95-99. P. Erdős and Z. Füredi, The greatest angle among n points in the d-dimensional Euclidean space, Annals of Discrete Math. 17 (1983) 275-283. Viktor Harangi, Acute Sets In Euclidean Spaces, Journal on Discrete Mathematics, volume 25, issue 3, (2011) 1212-1229. Dmitry Kamenetsky, Lower bounds and their solutions for a(11-15) Math StackExchange, Tight Acute Sets Hugues Randriambololona, (2,1)-Separating systems beyond the probabilistic bound, Israel Journal of Mathematics, 195 (2013), 171-186; DOI: 10.1007/s11856-012-0126-9. Hugues Randriambololona, (2,1)-Separating systems beyond the probabilistic bound, arXiv:1010.5764 [math.CO], 2010-2012. 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_{j-i 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: A341468 A071528 A056902 * A334653 A230059 A340445 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 24 11:42 EST 2022. Contains 350536 sequences. (Running on oeis4.)