cp's OEIS Frontend

A347025 Maximum size of a family of nonempty sets on n elements such that no set is a union of some others.

%I A347025 #96 Jun 02 2022 10:23:13
%S A347025 0,1,2,4,7,13,24
%N A347025 Maximum size of a family of nonempty sets on n elements such that no set is a union of some others.
%C A347025 The upper bounds of Loo (table on pp. 11-13; formula below) may be improved given the term a(5). Specifically, using h = 1 and a(5) in Loo's upper bound formula yields a(6) <= 27 (versus the published 30). The lower and upper bounds may be used to distinguish this sequence from others in the OEIS. - _Michael S. Branicky_, Mar 16 2022
%C A347025 a(7) >= 44, a(8) >= 79, a(9) >= 144, a(10) >= 270; see the Apr 05 2022 entry in the Formula section. - _Jon E. Schoenfield_, Apr 04 2022
%C A347025 a(7) <= 45. - _Jinyuan Wang_, Apr 23 2022
%H A347025 Michael S. Branicky, <a href="/A347025/a347025_1.py.txt">Python program</a>
%H A347025 Andy Loo, <a href="https://arxiv.org/abs/1511.00170">Union-Free Families of Subsets</a>, arXiv:1511.00170 [math.CO], 2015.
%H A347025 Augusto Perez, <a href="https://math.stackexchange.com/questions/4262598/maximum-size-of-antichain-like-collection">Maximum size of antichain-like collection</a>, Math.SE question (2021).
%F A347025 From _Michael S. Branicky_, Mar 16 2022: (Start)
%F A347025 Bounds from Loo (p. 10):
%F A347025   a(n) >= binomial(n, ceiling(n/2)),
%F A347025   a(n) >= max_{h=1..n-1} a(h) + a(n-h) + 1,
%F A347025   a(n) <= min_{h=1..n-1} a(h) + 2^h*a(n-h). (End)
%F A347025 For n > 2, a(n) >= max_{m=3..n} 2*floor(m/3) + binomial(m,3) + [n < 6] + Sum_{j=m..n-1} binomial(j,m-3) where [n < 6] is an Iverson bracket. - _Jon E. Schoenfield_, Apr 05 2022
%e A347025 a(4) = 7: an example of such a family is {{1},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}.
%o A347025 (Python)
%o A347025 from itertools import combinations
%o A347025 def anysetunion(family):
%o A347025     for s in family:
%o A347025         allrest = 0
%o A347025         for r in family:
%o A347025             if r != s and r&s == r:
%o A347025                 allrest |= r
%o A347025                 if allrest == s:
%o A347025                     return True
%o A347025     return False
%o A347025 def a(n):
%o A347025     if n < 2: return n
%o A347025     m = 2
%o A347025     while True:
%o A347025         allfailed = True
%o A347025         for family in combinations(range(1, 2**n), m):
%o A347025             unionfound = anysetunion(family)
%o A347025             allfailed &= unionfound
%o A347025             if not unionfound: break
%o A347025         if allfailed: return m - 1
%o A347025         m += 1
%o A347025 print([a(n) for n in range(5)]) # _Michael S. Branicky_, Nov 09 2021
%K A347025 nonn,hard,more
%O A347025 0,3
%A A347025 _Jukka Kohonen_, Sep 29 2021
%E A347025 a(6) from _Jinyuan Wang_, Apr 19 2022