login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Table of n, a(n) for n=0..10.

Eyal Ackerman and Oren Ben-Zwi, On sets of points that determine only acute angles, European Journal of Combinatorics 30 (2009) 908-910.

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) 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: 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

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 26 00:20 EDT 2019. Contains 321478 sequences. (Running on oeis4.)