Proof. The inclusion in (4) is equivalent to \[u\ge \max\bigl(\{\lambda(x):x\notin A\}\cup\{0\}\bigr).\] The remaining inequality is closed in \(u\), since its two sides are continuous. Thus the nonempty set of admissible cutoffs is compact and has a largest element \(\varepsilon\).

Put \(R=\{x:\lambda(x)>\varepsilon\}\). If \(\varepsilon=1\), then \(R=\varnothing\) and the assertion holds. Otherwise, consider \[f(u)=\sum_{x\in X}\min\{\lambda(x),u\} \bigl(\mathbf 1_A(x)-(1-d)\bigr)-mu.\] On a sufficiently short interval to the right of \(\varepsilon\), the only unsaturated terms are those indexed by \(R\). Each of these points belongs to \(A\), so the slope on that interval is \(d|R|-m\). This statement also holds when \(\varepsilon=0\) or when \(\varepsilon\) equals one of the weights: weights equal to the cutoff remain constant when the cutoff increases. An increase of the cutoff preserves the inclusion in (4). If \(d|R|-m\) were positive, it would also preserve \(f(u)\ge 0\) for a small increase, contradicting maximality. Hence \(d|R|\le m\). ◻

Proof of Theorem 3. If \(s=0\), the only color is \(1\), and both conclusions are immediate. Assume henceforth that \(s\ge 1\), and put \(d_i=2^{-i}\) for \(1\le i\le s\). Call a coloring \(a\) bad if no \(H\in\mathcal F\) satisfies (2). We will prove \(\mathbb P(a\text{ is bad})\le 1/10\).

Feasible moves and a cover. We may move vertices to earlier colors, obtaining a coloring \(z\le a\) pointwise. Write \[U(a,z)=\{x:z(x)<a(x)\}, \qquad m_i(a,z)=|A_i(z)\setminus A_i(a)|.\] Call such a move feasible if there are \(H\in\mathcal F\) and \(\varepsilon_1,\ldots,\varepsilon_s\in[0,1]\) such that, for every \(i\), \[ \begin{split} R_i:=\{x:\lambda_H(x)>\varepsilon_i\}&\subseteq A_i(z),\\ \sum_{x\in X}\min\{\lambda_H(x),\varepsilon_i\} \bigl(\mathbf 1_{A_i(z)}(x)-(1-d_i)\bigr) &\ge m_i(a,z)\varepsilon_i. \end{split} \tag{5}\] The right side charges \(\varepsilon_i\) for each vertex in \(A_i(z)\setminus A_i(a)\). Removing one of these vertices lowers the truncated sum by at most \(\varepsilon_i\) while reducing that charge by exactly \(\varepsilon_i\); hence the inequality survives. If the vertex has mass at most \(\varepsilon_i\), it lies outside \(R_i\), so the inclusion survives as well. We will apply this balance when delaying a vertex from color \(i\) to color \(i+1\).

If the unchanged move \(z=a\) is feasible, then \(a\) is not bad. Indeed, in this case \(m_i(a,a)=0\). Replacing each truncated weight by its original value adds only nonnegative terms to the left side of (5): any excess weight lies in \(R_i\subseteq A_i(a)\) and has coefficient \(d_i\). The resulting inequality is \(\lambda_H(A_i(a))-(1-d_i)\ge0\), for the same \(H\) at every \(i\).

Fix orders on the finite sets of colorings and members of \(\mathcal F\). For every \(a\) and \(H_0\in\mathcal F\), choose a feasible coloring \(z\) with \(U(a,z)\subseteq H_0\) minimizing \[L(a,z)=\sum_{x\in X}(a(x)-z(x)),\] breaking ties by the fixed order. This minimum exists: the move that sets \(z(x)=1\) on \(H_0\) and leaves other colors unchanged is feasible with \(H=H_0\) and all cutoffs zero. Notice that the witness \(H\) in the minimization is otherwise unrestricted; it need not equal \(H_0\).

Let \(\mathcal Z(a)\) be the set of chosen colorings, with repetitions removed. The changed sets \(U(a,z)\), \(z\in\mathcal Z(a)\), cover \(\mathcal F\), because each \(H_0\) contains its chosen changed set. Failure of \(p\)-smallness therefore implies \[\sum_{z\in\mathcal Z(a)}p^{|U(a,z)|}>\frac12.\] This remains true if distinct colorings have the same changed set: the displayed sum is then at least the cost of the cover with its repeated sets removed. Define \(P(v)=\prod_{x\in X}\pi_{v(x)}\) for every coloring \(v\). It follows that \[ \frac12\mathbb P(a\text{ is bad}) \le \sum_{a\text{ bad}}P(a) \sum_{z\in\mathcal Z(a)}p^{|U(a,z)|}. \tag{6}\] Every changed set appearing on the right is nonempty, since a bad coloring has no feasible unchanged move.

A witness determined by the final coloring and the counts. Group the pairs \((a,z)\) on the right of (6) by \(z\) and the array of counts \[n_{ih}=|\{x:z(x)=i,\ a(x)=h\}| \qquad(1\le i<h\le s+1).\] We call this array the profile. Put \[t_i=\sum_{h>i}n_{ih}, \qquad t=\sum_{i=1}^s t_i=|U(a,z)|.\] The profile also determines every quantity in the feasibility tests that depends on \(a\), because \[ m_i(a,z)=\sum_{j\le i<h}n_{jh}. \tag{7}\]

Fix \(z\) and a profile occurring in the sum. Choose the first \(H\in\mathcal F\) that can witness (5) with these data. Such a witness exists, and this choice uses only \(z\) and the profile. For this fixed \(H\), choose at every \(i\) the largest admissible cutoff in (5). The choices for the different indices impose no restrictions on one another. Lemma 4 gives \[ |R_i|\le \frac{m_i(a,z)}{d_i}\le 2^i t. \tag{8}\] The resulting \(H\), cutoffs, and sets \(R_i\) are fixed for the entire group. In particular, they witness feasibility for every original coloring \(a\) in that group, irrespective of the member \(H_0\) that led to the choice of \(z\).

For each such original coloring we claim that \[ \{x:z(x)=i<a(x)\}\subseteq R_i \qquad(1\le i\le s). \tag{9}\] Suppose instead that a vertex \(x\) on the left lies outside \(R_i\). Delay its color in \(z\) from \(i\) to \(i+1\), obtaining \(z'\). Since \(a(x)>i\), we still have \(z'\le a\). Choose an \(H_0\) for which \(z\) was a minimum. The changed set of \(z'\) is contained in that of \(z\), so it is still contained in \(H_0\).

Only \(A_i(z)\) changes under this delay: it loses \(x\), while all other \(A_j(z)\) remain unchanged. Correspondingly, \(m_i(a,z)\) decreases by one and all other \(m_j(a,z)\) remain unchanged. The inclusion in test \(i\) stays true because \(x\notin R_i\). The left side of that test decreases by \(\min\{\lambda_H(x),\varepsilon_i\}\le\varepsilon_i\), whereas its right side decreases by exactly \(\varepsilon_i\). Thus the same \(H\) and cutoffs witness feasibility of \(z'\). But \(L(a,z')=L(a,z)-1\), contradicting the defining minimum. This proves (9) for every \(a\) in the group. Figure 1 illustrates why moving one vertex back by one level changes only one of the feasibility tests.

Counting the original colorings. Given \(z\) and the profile, an original coloring \(a\) is determined by its changed vertices of each color \(i\) in \(z\), together with their original colors \(h>i\). By (9), the number of possibilities is at most \[ \prod_{i=1}^s \binom{|R_i|}{t_i} \binom{t_i}{(n_{ih})_{h>i}}, \tag{10}\] where the second factor is a multinomial coefficient. The sets \(R_i\) may overlap and may contain vertices of other colors in \(z\). Counting arbitrary subsets of them only adds possibilities to (10); every actual coloring has a unique encoding of the indicated form.

For \(t>0\), (8) and \(\binom{n}{k}\le(en/k)^k\) give \[ \prod_{i=1}^s\binom{|R_i|}{t_i} \le \prod_{i:t_i>0}\left(\frac{e\,2^i t}{t_i}\right)^{t_i} \le \prod_{i=1}^s(e\,4^i)^{t_i}. \tag{11}\] To see the last inequality, apply weighted AM–GM with weights \(\alpha_i=t_i/t\) on the positive rows: \[\prod_{i:t_i>0} \left(\frac{2^{-i}}{\alpha_i}\right)^{\alpha_i} \le \sum_{i:t_i>0}2^{-i}\le1.\] Raising this inequality to the power \(t\) yields exactly the second inequality in (11). Rows with \(t_i=0\) contribute a factor of one.

For each pair in the group, its probability and cost satisfy the exact identity \[ p^tP(a)=P(z) \prod_{i=1}^s\left(\frac p{\pi_i}\right)^{t_i} \prod_{i<h}\pi_h^{n_{ih}}. \tag{12}\] All color probabilities are positive. Combining (10)–(12), the contribution of a fixed \(z\) and profile to the right side of (6) is at most \[ P(z)\prod_{i=1}^s \left[ \left(\frac{e\,4^i p}{\pi_i}\right)^{t_i} \binom{t_i}{(n_{ih})_{h>i}} \prod_{h>i}\pi_h^{n_{ih}} \right]. \tag{13}\] The witness and the sets \(R_i\) can depend on the full profile, but none of that dependence remains in this bound.

For fixed row sums \(t_1,\ldots,t_s\), we can consequently sum (13) over all nonnegative integer profiles with those row sums, including profiles that do not occur. The multinomial theorem gives, for each row, \[\sum_{\substack{(n_{ih})_{h>i}\ge0\\ \sum_{h>i}n_{ih}=t_i}} \binom{t_i}{(n_{ih})_{h>i}} \prod_{h>i}\pi_h^{n_{ih}} =\left(\sum_{h>i}\pi_h\right)^{t_i}\le1.\] Finally, summing over all colorings \(z\) uses \(\sum_zP(z)=1\). Thus the right side of (6) is at most \[ \sum_{\substack{t_1,\ldots,t_s\ge0\\ t_1+\cdots+t_s>0}} \prod_{i=1}^s \left(\frac{e\,4^i p}{\pi_i}\right)^{t_i} = \sum_{\substack{t_1,\ldots,t_s\ge0\\ t_1+\cdots+t_s>0}} \prod_{i=1}^s\left(\frac e{64^i}\right)^{t_i}, \tag{14}\] where both sums run over integer tuples. Put \(\rho=\sum_{i=1}^s e/64^i\). For a fixed total \(\ell=t_1+\cdots+t_s\), each monomial in (14) occurs in the expansion of \(\rho^\ell\) with a multinomial coefficient at least one. Since \[\rho<\frac e{63}<\frac1{21},\] we obtain \[\text{right side of \eqref{sel:cover-cost}} \le\sum_{\ell\ge1}\rho^\ell =\frac{\rho}{1-\rho}<\frac1{20}.\] Together with (6), this proves that the bad probability is at most \(1/10\).

For every nonbad coloring the same \(H\) satisfies all inequalities in (2). Since the colors are integers, \[\sum_{x\in X}a(x)\lambda_H(x) =1+\sum_{i=1}^s\bigl(1-\lambda_H(A_i(a))\bigr) \le1+\sum_{i=1}^s2^{-i}\le2.\] This proves (3) and completes the proof. ◻

Proof of Theorem 1. Put \[D=256,\qquad B=512,\qquad C=25B^4.\] Let \(r\in(0,1]\) and suppose that \(g:2^X\to[0,1]\) satisfies \[ \sum_{S\subseteq H}g(S)\ge1\quad(H\in\mathcal F), \qquad \sum_{S\subseteq X}g(S)r^{|S|}\le\frac12. \tag{15}\] Set \(p=r/C\). We prove that \(\mathcal F\) is \(p\)-small.

First observe that \(g(\varnothing)\le1/2\), since its contribution to the second sum in (15) is \(g(\varnothing)\). For each \(H\in\mathcal F\), define \[ M_H=\sum_{\varnothing\ne S\subseteq H}g(S) \ge1-g(\varnothing)\ge\frac12, \qquad \lambda_H(x)=\frac1{M_H} \sum_{\substack{\varnothing\ne S\subseteq H\\x\in S}} \frac{g(S)}{|S|}\quad(x\in X). \tag{16}\] The function \(\lambda_H\) vanishes off \(H\) and is a probability mass function: summing over \(x\) counts each nonempty \(S\) exactly \(|S|\) times.

Suppose, for a contradiction, that \(\mathcal F\) is not \(p\)-small. Let \(s\) be the largest nonnegative integer for which \[ p\sum_{i=1}^sD^i\le\frac12. \tag{17}\] Such an integer exists: zero satisfies the restriction, and \(p>0\) makes the geometric sums unbounded. Apply Theorem 3 to these probability masses and this choice of \(s\). Thus the colors \(a(x)\) are independent, with \[\mathbb P(a(x)=i)=\pi_i=D^ip\quad(1\le i\le s), \qquad \mathbb P(a(x)=s+1)=\pi_{s+1}=1-p\sum_{i=1}^sD^i.\] With probability at least \(9/10\), there is an \(H\in\mathcal F\) such that \(\sum_x a(x)\lambda_H(x)\le2\). Denote this event by \(\mathcal E\), and set \[ Y_x=B^{4-a(x)},\qquad Z=\sum_{\varnothing\ne S\subseteq X}g(S)\prod_{x\in S}Y_x. \tag{18}\]

Fix an outcome in \(\mathcal E\) and a corresponding member \(H\). Writing \(\overline a(S)=|S|^{-1}\sum_{x\in S}a(x)\) for nonempty \(S\), we have \[\frac1{M_H}\sum_{\varnothing\ne S\subseteq H} g(S)\overline a(S) =\sum_x a(x)\lambda_H(x)\le2.\] Apply Markov’s inequality to the probability distribution \(g(S)/M_H\) on the nonempty subsets of \(H\). It gives \[\sum_{\substack{\varnothing\ne S\subseteq H\\ \overline a(S)\le4}}g(S)\ge\frac{M_H}{2}.\] For every set in this sum, \[\prod_{x\in S}Y_x =B^{\,|S|(4-\overline a(S))}\ge1.\] Consequently \(Z\ge M_H/2\ge1/4\) on \(\mathcal E\). This holds for each outcome, although the corresponding \(H\) may depend on the coloring. Since \(Z\) is nonnegative everywhere, \[ \mathbb EZ\ge\frac14\mathbb P(\mathcal E)\ge\frac9{40}. \tag{19}\]

For the upper bound, maximality of \(s\) gives \[\frac12<p\sum_{i=1}^{s+1}D^i\le2pD^{s+1}.\] As \(B\ge D\), it follows that \[ B^{-(s+1)}\le D^{-(s+1)}<4p. \tag{20}\] The variables \(Y_x\) are independent and identically distributed, and their common mean \(\mu\) satisfies \[\begin{align*} \mu &=B^4\left(p\sum_{i=1}^s(D/B)^i +\pi_{s+1}B^{-(s+1)}\right)\\ &\le B^4\left(p\sum_{i=1}^s2^{-i}+4p\right) \le5B^4p=\frac r5. \tag{21}\end{align*}\] The same estimates hold when \(s=0\), with the first sums empty. Independence now yields \[\begin{align*} \mathbb EZ &=\sum_{\varnothing\ne S\subseteq X}g(S)\mu^{|S|}\\ &\le\sum_{\varnothing\ne S\subseteq X}g(S)(r/5)^{|S|} \le\frac15\sum_{\varnothing\ne S\subseteq X}g(S)r^{|S|} \le\frac1{10}. \tag{22}\end{align*}\] Here the factor \(1/5\) is valid because every set in the sum is nonempty. The bounds (19) and (22) contradict one another.

Thus \(\mathcal F\) is \(r/C\)-small for every admissible \(r>0\). At \(r=0\), the family \(\mathcal F\) itself is a cover of cost zero, since \(\varnothing\notin\mathcal F\). Taking \(r=q_f(\mathcal F)\), with this last observation covering the case \(q_f(\mathcal F)=0\), proves \[q_f(\mathcal F)\le25\cdot512^4\,q(\mathcal F).\] ◻

Proof. If \(\operatorname{Bad}_2(\mathcal A)\) is empty, take \(\mathcal G=\varnothing\). Otherwise this is a nonempty increasing family. It is proper because \(\mathcal A\) is nonempty and hence \(\varnothing\notin\operatorname{Bad}_2(\mathcal A)\). Li’s theorem, in the covering formulation given by Park [12], supplies a fractional cover of \(\operatorname{Bad}_2(\mathcal A)\) of cost at most \(1/2\) at parameter \(p/2\). Its coefficients may be capped at one without affecting coverage or increasing cost. Theorem 1 therefore yields an integral cover of cost at most \(1/2\) at parameter \(p/(2C)\). ◻