[Crossposted at math.stackexchange].
Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$.
I have written and solved iteratively a mixed integer linear program for $q = 3, \ldots, 12$ and $n = 1, \ldots, 2^q$ with binary indicator variables $x_A=1$ iff $A \in \mathcal{F}$, and minimized $\sum_{1 \in A} x_A$ subject to $\sum_{A \in \mathcal{F}} x_A = n$ and $\sum_{1 \in A} x_A \ge \sum_{u \in A} x_A$ for any $u \not= 1$ (one constraint for each $u$). I have forced also that for any element in the universe, there must exist at least a set containing it. Therefore I have computed the minimum frequency of the element $1$ subject to the condition that $1$ has maximum frequency, over all possible families of size $n$ and with $q$ elements. Let $f(n, q)$ be the optimal objective value. The relaxation of the program seems to give basically the same results, in other words $f(n, q) = \min_{MILP} = \lceil \min_{LP} \rceil$.
The maximum values of $n/2-f(n,q)$ for fixed $q = 3, \ldots, 12$ and over $n = 1, \ldots, 2^q$, are $1, 2, 3, 5, 10, 18, 35, 63, 126, 231$. They seem to be reached in roughly all the interval $2^{q-4} \le n \le 2^{q-2}$. Apparently, these are "least integers having Radon random number $q-2$" (OEIS A002661), and therefore it can be conjectured that:
$$f(n,q) \ge \frac{n}{2} - \Bigg\lceil \frac{\binom{q - 1}{\lfloor (q - 1)/2 \rfloor}}{2} \Bigg\rceil$$
If I remove the constraint $\sum_{A \in \mathcal{F}} x_A = n$ and modify the objective function from $\sum_{1 \in A} x_A$ into $\sum_{1 \in A} x_A - \sum_{1 \not\in A} x_A$ then it is possible to run just one program for each $q$ and in this way it can be verified that for $2 \le q \le 20$ the minimum is:
$$-\binom{q-1}{\lfloor (q-1)/2 \rfloor}$$
and some solutions are:
- for $q = 2, 3$ all singleton sets and the empty set;
- for $q = 4$ all singleton sets, the empty set and $\{1,2\}$, $\{2,3\}$, $\{3,4\}$, $\{1,4\}$;
- for $q = 5$ all sets of size $0$, $1$ and $2$;
- fot $q = 6$ all sets of size $0$, $1$, $2$ and $\{1,2,3\},\{1,3,4\},\{1,2,5\},\{1,4,5\},\{2,4,6\},\{3,4,6\},\{2,5,6\},\{3,5,6\}$;
- for $q = 7$ all sets of size $0, 1, 2, 3$;
- apparently for $q$ odd all sets of size from $0$ to $(q-1)/2$.
Is it possible to justify the conjecture analytically?
