Boolean Lattice Implementation


Let $ X = \{1,2,\dots n\}$ , and $ Y= \{ S\subset X: |S|\le 2\}$ . I am interested in "avoidance sets" $ A \subset Y$ which logically are supposed to correspond to $ f(A):=\bigwedge_{a\in A} \lnot a$ in the Boolean lattice defined over $ \mathcal{P}(X)$ . (if $ A = \{\}$ it shall correspond to $ X$ , the maximal element of our lattice)

Given a list of avoidance sets $ A_1,A_2,\dots A_k$ , I want to return an avoidance set $ A’$ such that $ f(A’)$ is the least upper bound of $ \bigvee_{1\le i \le k} f(A_i)$ . (by least upper bound I mean the least upper bound which can be represented by an avoidance set)

Can this be done in time linear to $ \sum_{1\le i \le k} |A_i|$ ? (you may assume that all the sets $ A_i$ are simplified, i.e. if $ \{a\}\in A_i$ and $ \{b\}\in A_i$ then $ \{a,b\} \not \in A_i$ )