login
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
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-Füredi, 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-Füredi, 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-Füredi 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.
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
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