Lower bound on union of finite sets (inclusion-exclusion principle)

Question

I have the following problem emerged. Let's say we have $l$ finite sets $A_1, A_2, \ldots, A_l$ with cardinality of $n_1, n_2, \ldots\, n_l$, respectively. We know that $| A_i \cap A_j | \le a_{ij}$ (ibvously, $a_{ij}=a_{ji}$).

What could be a lower bound on $\left|\bigcup_{k=1}^l A_k \right|$?

The bound I would be satisfied with should be easy (polynomial) to compute and thus could be rough (but better than just maximum of $n_i$).

Some notes

From inclusion-exclusion principle we know exact expresion for that: $$ \left|\bigcup_{k=1}^l A_k\right| = \sum_{k=1}^l (-1)^{k+1} \left( \sum_{1 \le i_1 < i_2 < \ldots < i_k \le l} \left| A_{i_1} \cap A_{i_2} \cap \ldots \cap A_{i_k} \right| \right) $$ but it is an exponintioal computation and we don't know all the intersections anyway.

In the real problem I am facing,there are the following values $$ n_i = w_i \binom{n-w_i}{k-1}, \\ a_{ij} = \delta \binom{n-w_i-w_j+\delta}{k-1}, \\ w_i, n, k, \delta \mbox{ are some natural numbers.} $$ But it's getting more messy to work with these expressions.

UPD. The question could be re-phrased like the following.

Find an easy computable function $\beta(l; a_{ij})$ such that for every $l$, $A_j$ and $a_{ij} = a_{ji}$ it holds $$ \left|\bigcup_{k=1}^l A_k\right| \ge \beta(l; a_{ij}) $$

Answer 1

By Bonferroni's inequalities, the terms in the inclusion-exclusion sum alternately under- and over-estimate the final value. You should be fine with just: $$ \lvert A_1 \cup A_2 \cup \ldots \cup A_n \rvert \ge \sum_i \lvert A_i \rvert - \sum_{i < j} \lvert A_i \cap A_j \rvert \ge \sum_i \lvert A_i \rvert - \sum_{i < j} a_{ij} $$ This bound can be attained, when the intersections in threes are empty.

Answer 2

A greedy estimate:

Supposing for $1<k\le l$, $$ \left| A_{i_1} \cap A_{i_2} \cap \ldots \cap A_{i_k} \right|= \begin{cases} 0 & \text{if k is odd}\\ b_{(k,\{i_1,i_2,\dots i_k\})}:=\min\{a_{i_pi_q} | p,q \in \{1,2,\dots k\}\} & \text{if k is even} \end{cases} $$

By inclusion-exclusion,$$\left|\bigcup_{i=1}^l A_j\right|=\sum_{i=1}^{l}n_{l}-\sum_{j=1}^{\lfloor \frac{l}{2}\rfloor}\left( \sum_{S_{2j}\subset [l]}b_{(2j,S_{2j})}\right)$$

This makes sense only if the RHS$>0$.