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

0, 1, 2, 4, 7, 13, 24

Offset: 0

Author

Jukka Kohonen, Sep 29 2021

Keywords

• nonn
• hard
• more

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

Examples

			a(4) = 7: an example of such a family is {{1},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}.
		

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

Programs

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

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

Extensions

a(6) from Jinyuan Wang, Apr 19 2022