Minimum number of elements needed to satisfy a property for all choices of $c \le \binom{n}{2}$ couples from $n$ sets. Consider $n$ finite distinct sets $A_1,\ldots,A_n \subset [q] = \{1, \ldots, q\}, A_1,\ldots,A_n \not= \emptyset$ and $c \le \binom{n}{2}$ unordered couples of them chosen arbitrarily among the $\binom{n}{2}$ possible, provided that the intersection of the two sets in the couple is empty.
$A_1,\ldots,A_n$ are not given, but can be chosen at will. They will be chosen with the goal of minimizing $q$ given $n$ and $c$, for all possible choices of the $c$ couples. Maybe it is more clear to ask that $q$ be the minimum over all choices of $A_1,\ldots,A_n$ and the $c$ couples, given $n$ and $c$.
If for example $c = \binom{n}{2}$ we can take $q = n$ singleton sets each with a different element and we cannot do less than that, but I find it difficult to figure out how to proceed in the general case $c \lt \binom{n}{2}$.
Another example is $n=5$ and $c \le 5$. In this case we have a minimum $q = 3$ that we can obtain for $1 \le c \le 5$ using e.g. $A_1 = \{1\}$, $A_2 = \{2\}$, $A_3 = \{3\}$, $A_4 = \{1,2\}$, $A_5 = \{1,3\}$. But with $n=5$ and $c = 6$ the minimum is $q = 4$ obtained with e.g. $A_1 = \{1\}$, $A_2 = \{2\}$, $A_3 = \{3\}$, $A_4 = \{4\}$, $A_5 = \{1,2\}$. Choose the disjoint couples as you want.
We can always take the lowest value of $q$ such that $\binom{q}{2} \ge c$, then make $q$ singleton sets and build the other $n-q$ easily without the need for them to be disjoint, but the actual minimum of $q$ is lower.
Any hint for a general lower bound for $q$?
I am particularly interested in the case $n=39$ and $c=113$.
 A: A valid set-couple combo for $n$ and $c$ with $A_i\subseteq[q]$ corresponds to a subgraph with $n$ vertices and $c$ edges of $G_q$, a graph on $2^q-1$ vertices representing the nonempty subsets of $[q]$ where edges link any and all disjoint subset pairs. The number of edges in $G_q$ is
$$\frac12\sum_{i=1}^q\binom qi(2^{q-i}-1)=S(q+1,3)$$
where $S$ is the second-kind Stirling number. Therefore $n\le2^q-1$ and $c\le S(q+1,3)$.
$G_q$ may be approximately tested for a subgraph of the given order and size through a greedy algorithm: add vertices for subsets of increasing size to the putative subgraph until $n$ vertices have been added. If the induced subgraph has at least $c$ edges, return YES, else NO. The algorithm is not exact since for larger $q$ the highest-degree vertices in $G_q$ correspond to non-singleton subsets, but it should be a good approximation.
For $n=39,c=113$ we need $q\ge6$, but the first two "levels" of $G_6$ with all the singetons and pairs provide a subgraph with $21$ vertices and $120$ edges, more than enough:

*

*$15$ edges between singletons

*$45$ edges between pairs

*$60$ edges from singletons to pairs

Thus $q(n=39,c=113)=6$, with $21$ of the $A_i$ being all the singletons and pairs and the remaining $A_i$ being arbitrary.
A: A setup like $n=39$ and $c=113$ is sparse: there are $\binom{39}{2} = 741$ pairs of subsets, and we only want a small fraction of them to be disjoint.
In this case, the following strategy seems to be a good idea. First, $q=5$ will not be enough, since there are at most $2^5-1 = 31$ sets to pick in that case. So we must take $q \ge 6$. With $q=6$, just list all the nonempty subsets of $\{1,\dots,q\}$ in order first by size (since we prefer to pick smaller sets) and then arbitrarily, and pick the first $39$ of them.
According to Mathematica, if we pick all the $1$-element and $2$-element sets, all the $3$-element sets containing $1$ or $2$ (which brings us up to $37$), and finally the sets $\{3,4,5\}$ and $\{3,4,6\}$, then $236$ of these are disjoint, which is comfortably over the threshold of $c=113$. So $q=6$ is the optimal solution.

In the dense case, where $c$ is a majority of $\binom n2$, Alon and Frankl's paper The maximum number of disjoint pairs in a family of subsets suggests the following strategy, which they prove to be asymptotically optimal.
Choose the least $k\ge2$ such that $(1 - \frac1k)\binom n2 \ge c$. Then, we take $q = k \lceil \log_2 (\frac nk+1) \rceil$. Now, the set $\{1, 2, \dots, q\}$ can be divided into $k$ disjoint subsets $X_1, \dots, X_k$ such that $2^{|X_i|}-1 \ge \frac nk$ for all $i$.
To choose our family, we take $\lfloor \frac nk\rfloor$ or $\lceil\frac nk\rceil$ subsets of each $X_i$. We'll get approximately $(1 - \frac1k) \binom n2$ disjoint pairs just from the fact that any subset of $X_i$ is disjoint from any subset of $X_j$ with $i\ne j$. Maybe we'll lose a few because of rounding up or down, but on the other hand we'll gain a few because of disjoint pairs within each $X_i$. In the end, we should get at least $c$ disjoint pairs.
