OFFSET
0,3
COMMENTS
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
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
a(7) <= 45. - Jinyuan Wang, Apr 23 2022
LINKS
Michael S. Branicky, Python program
Andy Loo, Union-Free Families of Subsets, arXiv:1511.00170 [math.CO], 2015.
Augusto Perez, Maximum size of antichain-like collection, Math.SE question (2021).
FORMULA
From Michael S. Branicky, Mar 16 2022: (Start)
Bounds from Loo (p. 10):
a(n) >= binomial(n, ceiling(n/2)),
a(n) >= max_{h=1..n-1} a(h) + a(n-h) + 1,
a(n) <= min_{h=1..n-1} a(h) + 2^h*a(n-h). (End)
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
EXAMPLE
a(4) = 7: an example of such a family is {{1},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}.
PROG
(Python)
from itertools import combinations
def anysetunion(family):
for s in family:
allrest = 0
for r in family:
if r != s and r&s == r:
allrest |= r
if allrest == s:
return True
return False
def a(n):
if n < 2: return n
m = 2
while True:
allfailed = True
for family in combinations(range(1, 2**n), m):
unionfound = anysetunion(family)
allfailed &= unionfound
if not unionfound: break
if allfailed: return m - 1
m += 1
print([a(n) for n in range(5)]) # Michael S. Branicky, Nov 09 2021
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Jukka Kohonen, Sep 29 2021
EXTENSIONS
a(6) from Jinyuan Wang, Apr 19 2022
STATUS
approved