Proof. Consider any coloring \(f : E(K_{n,n}) \rightarrow [r]\). It has a coloring square with corresponding values \(a_i,b_i\) for \(i \in [r]\) and \(a(R),b(R)\) for \(R \subseteq [r]\) which satisfies constraints (1), (2), (3), (5), where we set \(a_i^* = a_i, b_i^* = b_i, a(R)^* = a(R)\) and \(b(R)^* = b(R)\). Furthermore, if we set \(m = \max_{i \in [r]} a_i + b_i\), then we also satisfy constraint (4). Thus,

\[\max_{i \in [r]} |\{v \in V(K_{n,n}) : i \text{ touches } v\}| = \max_{i \in [r]} (a_i + b_i)n = m \cdot n \geq g^*(r) \cdot n.\]

Note that this holds for all colorings \(f : E(K_{n,n}) \rightarrow [r]\), so in particular

\[\min_{f \in [r]^{E(K_{n,n})}} \;\max_{i \in [r]} |\{v \in V(K_{n,n}) : i \text{ touches } v \}| \geq g^*(r) \cdot n\]

and therefore \(g(n,r) \geq g^*(r) \cdot n\), as required. ◻

Proof. Note there exists rational solutions to \(m = g^*(r)\), \(a_i^*,b_i^*\) for \(i \in [r]\), and \(a(R)^*,b(R)^*\) for \(R \subseteq [r]\) to the coloring problem. This is because the coefficients of the variables in the linear constraints in (1), (2), (3), (4) and linear objective in (6) are all rational. It is a fact that a feasible linear program with rational coefficients has a rational optimal solution [3]. Thus for all \((P_1,P_2) \in \mathcal{P}(\mathcal{P}([r])) \times \mathcal{P}(\mathcal{P}([r]))\), there exists a solution \(m=h(P_1,P_2),a(R)^*,b(R)^*,a_i^*,b_i^*\) satisfying the constraints (1), (2), (3) and (4), where all the variables are rational. Recall \(g^*(r)\) is the minimum of \(h_r(P_1,P_2)\) over all \((P_1,P_2) \in \mathcal{P}(\mathcal{P}([r])) \times \mathcal{P}(\mathcal{P}([r]))\), and thus there exists \((P_1,P_2) \in \mathcal{P}(\mathcal{P}([r])) \times \mathcal{P}(\mathcal{P}([r]))\) such that \(m=g^*(r)=h(P_1,P_2),a(R)^*,b(R)^*,a_i^*,b_i^*\) is a solution to the coloring problem where all the variables are rational.
So let \(m\), \(a_i^*,b_i^*\) for \(i \in [r]\), and \(a(R)^*,b(R)^*\) for \(R \subseteq [r]\) be a rational solution to the coloring problem. Let \(N\) be the least common multiple of all the denominators of \(a(R)^*\) and \(b(R)^*\) for \(R \subseteq [r]\). For \(t \in \mathbb{Z}^{+}\), we can construct a coloring \(f : E(K_{tN,tN}) \rightarrow [r]\) such that

\[\max_{i \in [r]} |\{v \in V(K_{tN,tN}) : i \text{ touches } v\}| \leq m \cdot n.\]

Because \(N\) was chosen to be the least common multiple of the denominators of \(a(R)^*\) and \(b(R)^*\) for \(R \subseteq [r]\) and because of constraints (1) and (2), we can partition the \(tN\) vertices in \(A_{tN}\) into \(A_{tN} = \bigsqcup_{R \subseteq [r]} A_R\) (here \(\sqcup\) means disjoint union) where for \(R \subseteq [r]\) we have \(|A_R| = a(R)^* \cdot tN\), and likewise we can partition the \(tN\) vertices in \(B_{tN}\) into \(B_{tN} = \bigsqcup_{R \subseteq [r]} B_R\) where for \(R \subseteq [r]\) we have \(|B_R| = b(R)^* \cdot tN\). For vertex \(u \in A_{R_1}\) and vertex \(v \in B_{R_2}\) where \(R_1,R_2 \subseteq [r]\), we define \(f(u,v) = i\) where \(i\) can be anything in \(R_1 \cap R_2\). Note \(R_1 \cap R_2 \neq \{\}\) because of constraint (5).
We claim that \(a_i \leq a_i^*\). This inequality is easier to see in the form \(a_i \cdot tN \leq a_i^* \cdot tN\). First note that if for some \(u \in A_{tN}\) we had \(i \in F(\{u\} \times B_{tN})\), i.e. \(u\) touches \(i\), this must mean \(u \in A_R\) for some \(R \subseteq [r], i \in R\) by the definition of \(f\). Thus we have

\[\{u \in A_{tN} : u \text{ touches } i \} \subseteq \bigsqcup_{R \subseteq [r], \;i \in R} A_R\]

and so

\[a_i \cdot n = |\{u \in A_{tN} : u \text{ touches } i \}| \leq |\bigsqcup_{R \subseteq [r], \;i \in R} A_R| = \sum_{R \subseteq [r], \;i \in R} a(R)^* \cdot tN= a_i^* \cdot tN,\]

where the last equality comes from constraint (3). Likewise \(b_i \leq b_i^*\). Thus

\[\max_{i \in [r]} |\{v \in V(K_{tN,tN}) : i \text{ touches } v\}| \leq \max_{i \in [r]} (a_i+b_i)tN \leq \max_{i \in [r]} (a_i^*+b_i^*)tN \leq mtN\]

and so \(g(tN,r) \leq mtN = g^*(r) \cdot tN\). But by Theorem 1 we also had \(g(tN,r) \geq g^*(r) \cdot tN\) and so \(g(tN,r) = g^*(r) \cdot tN\), as required. ◻

Proof. As in Theorem 2, let \(m=g^*(r),a_i^*,b_i^*,a(R)^*,b(R)^*\) where \(i \in [r]\) and \(R \subseteq [r]\) be a rational solution to the coloring problem and let \(N\) be the least common multiple of all the denominators of \(a(R)^*,b(R)^*\) for all \(R \subseteq [r]\). Let \(C_r = 2N-2\). Let \(t = \lfloor \frac{n}{N} \rfloor\). As in Theorem 2, construct the coloring square \(F : A_{tN} \times B_{tN} \rightarrow [r]\) satisfying \(a_i \cdot tN +b_i \cdot tN \leq g^*(r) \cdot tN\) for all \(i \in [r]\).
We extend \(F : A_{tN} \times B_{tN} \rightarrow [r]\) to \(F' : A_{n} \times B_{n} \rightarrow [r]\) as follows. For \((i,j) \in [tN] \times [tN]\), define \(F'(u_i,v_j) = F(u_i,v_j)\). Then for \((i,j) \in ([n] \setminus [tN]) \times [tN]\), define \(F'(u_i,v_j) = F(u_{tN},v_j)\). Then for \((i,j) \in [n] \times ([n] \setminus [tN])\), define \(F'(u_i,v_j) = F'(u_i,v_{tN})\). Visually, what we did was we first copied column \(u_{tN}\) for \(n-tN\) number of times to extend \(F\) to the right, and then we copied the extended row \(v_{tN}\) for \(n-tN\) number of times to extend \(F\) upwards.
Note when we extended \(F\) to the right no color \(i \in [r]\) touched any new row, so color \(i\) can only touch more columns, namely the \(n-tN \leq N-1\) columns we just added. Likewise, when we extended \(F\) upwards no color \(i \in [r]\) touched any new column, so color \(i\) can only touch more rows, namely the \(n-tN \leq N-1\) rows we just added. Thus for any color \(i \in [r]\), the number of columns and rows it touches in \(F'\) is upper bounded by

\[a_i \cdot tN +b_i \cdot tN + 2(N-1)\leq g^*(r) \cdot tN + C_r \leq g^*(r) \cdot n + C_r.\]

Thus \(F'\) is a construction showing \(g(n,r) \leq g^*(r) \cdot n + C_r\), as required. ◻

Proof. By constraint (3), we have

\[\begin{align} \sum_{i \in [r]} a_ib_i &= \sum_{i \in [r]} \left( \sum_{R \subseteq [r], \;i \in R} a(R) \right) \left( \sum_{R \subseteq [r], \;i \in R} b(R) \right) \\ &= \sum_{i \in [r]} \left( \sum_{R_1, R_2 \subseteq [r], \;i \in R_1 \cap R_2} a(R_1)a(R_2) \right). \end{align}\]

By constraint (5), we have

\[\begin{align} \sum_{i \in [r]} \left( \sum_{R_1, R_2 \subseteq [r], \;i \in R_1 \cap R_2} a(R_1)a(R_2) \right) &\geq \sum_{R_1, R_2 \subseteq [r] , \;R_1 \cap R_2 \neq \{\}} a(R_1) \cdot b(R_2) \\ &= \sum_{R_1, R_2 \subseteq [r]} a(R_1) \cdot b(R_2). \end{align}\]

By constraint (2), we have

\[\sum_{R_1, R_2 \subseteq [r]} a(R_1) \cdot b(R_2) = \left( \sum_{R \subseteq [r]} a(R) \right) \left( \sum_{R \subseteq [r]} b(R) \right) = 1\]

and thus \(\sum_{i \in [r]} a_ib_i \geq 1\) as required. ◻

Proof. Consider any solution \(a,b : \mathcal{P}([r]) \rightarrow [0,1]\) satisfying constraints (1), (2), (3), and (5). Since \(\sum_{i \in [r]} a_ib_i \geq 1\), for some \(i \in [r]\) we have \(a_ib_i \geq \frac{1}{r}\). This implies \(a_i+b_i \geq \frac{2}{\sqrt{r}}\) by the AM-GM inequality, as required. ◻

Proof. To see that \(g^*(t^2) \leq \frac{2}{t}\), consider analogous constructions shown in Figure \(4\), where we have \(t^2\) squares arranged in a \(t\) by \(t\) grid, and each square gets a different color. Formally, for all \(i \in [t]\) we have

\[a(\{j \cdot r + i \in [t^2] : j \in \{0\} \cup [t-1]\}) = \frac{1}{t}\]

and for all \(i \in \{0\} \cup [t-1]\)

\[b(\{ i \cdot t + j \in [t^2] : j \in [t]\}) = \frac{1}{t}.\]

And finally, \(a(R) = b(R) = 0\) for other \(R \subseteq [t^2]\). One can check that \(a_i = b_i = \frac{2}{t}\) for all \(i \in [t^2]\).
To see that \(g^*(t^2) \geq \frac{2}{t}\), see Theorem 4. ◻

Proof. To see that \(g^*(2) \leq \frac{3}{2}\), consider

Now we show \(g^*(2) \geq \frac{3}{2}\). Consider any solution \(a,b : \mathcal{P}([2]) \rightarrow [0,1]\) satisfying constraints (1), (2), (3), and (5). Without loss of generality, assume \(a_1+b_1 \leq \frac{3}{2}\). We want to show \(a_2+b_2 \geq \frac{3}{2}\). Note that \(1-a_1 = a(\{2\})\) and \(1-b_1 = b(\{2\})\) by constraint (5). Since \(a_1+b_1 \leq \frac{3}{2}\), we have \(a(\{2\}) + b(\{2\}) \geq \frac{1}{2}\). We consider two cases.
Case 1: \(a(\{2\}),b(\{2\}) > 0\). Note \(a(\{2\}) > 0\) implies that \(b_2 = 1\) by constraint (5), and \(b(\{2\}) > 0\) implies \(a_2 = 1\) by constraint (5). Thus \(a_2 + b_2 = 2 \geq \frac{3}{2}\).
Case 2: Without loss of generality assume \(a(\{2\}) = 0\). Thus \(b(\{2\}) \geq \frac{1}{2}\), which implies \(a_2 = 1\). Thus \(a_2 + b_2 \geq a_2 + b(\{2\}) \geq \frac{3}{2}\), as required. ◻

Proof. Observe that

\[\sum_{i \in [r]} a_i = \sum_{i \in [r]} \sum_{R \subseteq [r], i \in R} a(R) = \sum_{R \subseteq [r]} \sum_{i \in R} a(R) = \sum_{R \subseteq [r]} |R| \cdot a(R).\]

The proof for \(\sum_{i \in [r]} b_i = \sum_{R \subseteq [r]} |R| \cdot b(R)\) is analogous. ◻

Proof. To see that \(g^*(3) \leq \frac{5}{4}\), consider

Now we show \(g^*(3) \geq \frac{5}{4}\). Consider any solution \(a,b : \mathcal{P}([3]) \rightarrow [0,1]\) satisfying constraints (1), (2), (3), and (5). We consider two cases.
Case 1: For \(R \subseteq [3]\), if \(|R| \leq 1\), then \(a(R) = b(R) = 0\). In other words if \(a(R) > 0\) then \(|R| \geq 2\) and if \(b(R) > 0\) then \(|R| \geq 2\). We note

\[\sum_{i \in [3]} a_i + b_i = \sum_{R \subseteq [3]} |R|(a(R) + b(R)) \geq \sum_{R \subseteq [3]} 2(a(R) + b(R)) = 4\]

where the last equality comes from constraint (2). Thus for some \(i \in [3]\) we have \(a_i + b_i \geq \frac{4}{3} \geq \frac{5}{4}\), and so we are done with this case.
Case 2: Without loss of generality assume \(a(\{1\}) > 0\). This implies \(b_1 = 1\) by constraint (5). Since we may assume \(a_1 + b_1 \leq \frac{5}{4}\), we have that \(a_1 \leq \frac{1}{4}\). This gives us

\[\sum_{R \subseteq \{2,3\}} a(R) = 1-a_1 \geq \frac{3}{4}\]

and

\[\sum_{R \in \{2\}^{\uparrow} \cup \{3\}^{\uparrow}} b(R) = 1.\]

Assume \(a_2 + b_2 \leq \frac{5}{4}\). This implies then that

\[a(\{3\}) + b'(\{3\}^{\uparrow} \setminus \{2\}^{\uparrow}) \geq \frac{3}{4} + 1 - \frac{5}{4} = \frac{1}{2}.\]

We consider three subcases. One should visualize the rest of the proof as finding an optimal coloring of a \(1-a_1\) by \(1\) rectangle using the two colors \(2,3\). We use an argument similar to the proof used in showing \(g^*(2) = \frac{3}{2}\).
Case 2.1: \(a(\{3\}), b'(\{3\}^{\uparrow} \setminus \{2\}^{\uparrow}) > 0\). Note \(a(\{3\}) > 0\) implies that \(b_3 = 1\) and \(b'(\{3\}^{\uparrow} \setminus \{2\}^{\uparrow}) > 0\) implies that \(a_3 \geq 1 - a_1 \geq \frac{3}{4}\) and so \(a_3+b_3 \geq 1 + \frac{3}{4} \geq \frac{5}{4}\).
Case 2.2: \(a(\{3\}) = 0\). In this case we have \(b'(\{3\}^{\uparrow} \setminus \{2\}^{\uparrow}) \geq \frac{1}{2}\). Note that this also implies \(a_3 \geq 1-a_1 \geq \frac{3}{4}\) and thus \(a_3 + b_3 \geq \frac{3}{4} + \frac{1}{2} = \frac{5}{4}\).
Case 2.3: \(b'(\{3\}^{\uparrow} \setminus \{2\}^{\uparrow}) = 0\). In this case we have that \(a(\{3\}) \geq \frac{1}{2}\), and thus \(b_3 = 1\). So we have \(a_3 + b_3 \geq \frac{1}{2} + 1 \geq \frac{5}{4}\), as required. ◻

Proof. We will find an upper bound on the maximum of \(\sum_{i \in [s]} c_id_i\) under the constraints above; the maximum of \(\sum_{i \in [s]} c_id_i\) exists because the constrained space is compact and \(\sum_{i \in [s]} c_id_i\) is continuous with respect to \(c_i,d_i\). Note we may assume \(c_i+d_i = k\) for all \(i \in [s]\), since if \(c_j + d_j < k\) for some \(j \in [s]\) we can increase both of \(c_j,d_j\) by a small amount, which will give us a larger value of \(\sum_{i \in [s]} c_id_i\). Thus we now just need to find the maximum of \(\sum_{i \in [s]} c_i(k-c_i)\) under the given constraints.
We now show we may also assume that \(\sum_{i \in [s]} c_i = 1\). If we had \(\sum_{i \in [s]} c_i > 1\), then for some \(j \in [s]\) we have \(c_j > \frac{1}{s} \geq \frac{k}{2}\). We may decrease \(c_j\) by a small amount so that \(c_j(k-c_j)\) increases which then would increase \(f(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i(k-c_i)\); the function \(g(x) = x(k-x)\) has derivative \(g'(x) = k - 2x\) and thus achieves a maximum at \(\frac{k}{2}\), and furthermore is concave as \(g''(x) = -2\), so moving \(x\) closer to \(\frac{k}{2}\) always increases \(x(k-x)\). Under the constraint \(\sum_{i \in [s]} c_i = 1\) the quantity we’re trying to maximize \(\sum_{i \in [s]} c_i(k-c_i)\) becomes

\[\sum_{i \in [s]} c_i(k-c_i)= k \left( \sum_{i \in [s]} c_i \right) - \sum_{i \in [s]} c_i^2 = k - \sum_{i \in [s]} c_i^2.\]

We use Lagrange multipliers to find the maximum of \(f(c_1,c_2,\ldots,c_s) = k - \sum_{i \in [s]} c_i^2\) under the constraint \(g_1(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i = 1\). But first we argue that the maximum exists. Note we may assume that \(c_i \geq 0\) for all \(i \in [s]\), since \(f(c_1,c_2,\ldots,c_s) = f(|c_1|,|c_2|,\ldots,|c_s|)\). The assumption \(c_i \geq 0\) for all \(i \in [s]\) along with the constraint \(\sum_{i \in [s]} c_i = 1\) gives rise to a compact space, and since \(f\) is continuous we know \(f\) has a maximum in this compact space, and thus has a maximum without the assumption \(c_i \geq 0\) for all \(i \in [s]\). So \(f(c_1,c_2,\ldots,c_s) = k - \sum_{i \in [s]} c_i^2\) has a maximum under the constraint \(g_1(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i = 1\). We now use Lagrange multipliers.
We note \(\frac{\partial f}{\partial c_i} = - 2c_i\) for \(i \in [s]\), and \(\frac{\partial g_1}{\partial i} = 1\) for \(i \in [s]\). Thus for some \(\lambda \in \mathbb{R}\) we get

\[\begin{pmatrix} -2c_1 \\ -2c_2 \\ \vdots \\ -2c_s \end{pmatrix} = \lambda \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix}\]

and so for all \(i \in [s]\), we have \(-2c_i = \lambda\). Thus we get for all \(i,j \in [s]\), we have \(-2c_i = -2c_j\), which implies \(c_i = c_j\). Note

\[1 = \sum_{i \in [s]} c_i = \sum_{i \in [s]} c_1 = sc_1\]

and so \(c_1 = \frac{1}{s}\), which implies \(c_i = \frac{1}{s}\) for all \(i \in [s]\). Note

\[f(\frac{1}{s},\frac{1}{s},\ldots,\frac{1}{s}) = \sum_{i \in [s]} \frac{1}{s}(k-\frac{1}{s}) = s \cdot \frac{1}{s}(k-\frac{1}{s}) = k-\frac{1}{s}\]

as required. ◻

Proof. We first show \(\sum_{i \in [s]} \max\{c_i,d_i\} \leq s(\frac{k}{2} + \sqrt{\frac{k^2}{4}-\frac{A}{s}})\). Without loss of generality assume \(c_i = \max\{c_i,d_i\}\) for all \(i \in [s]\), so we need to show \(\sum_{i \in [s]} c_i \leq s(\frac{k}{2} + \sqrt{\frac{k^2}{4}-\frac{A}{s}})\). We find an upper bound on the maximum of \(f(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i\) under the above constraints; the maximum exists because the constrained space is compact and \(f\) is continuous with respect to \(c_i\) and \(d_i\). First note we may replace the constraint \(c_i + d_i \leq k\) with \(c_i + d_i = k\) for all \(i \in [s]\). If \(c_i+d_i < k\), we can increase \(c_i\) so that \(f(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i\) attains a larger value while still maintaining the constraints. Thus the constraint \(\sum_{i \in [s]} c_id_i \geq A\) becomes \(\sum_{i \in [s]} c_i(k-c_i) \geq A\).
Next, we show that we may assume \(\sum_{i \in [s]} c_i(k-c_i) = A\). If \(\sum_{i \in [s]} c_i(k-c_i) > A\), for any \(i \in [s]\) we may increase \(c_i\) so that \(f(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i\) attains a larger value while still maintaining the constraints, unless \(c_i = k\) for all \(i \in [s]\), in which case the inequality \(\sum_{i \in [s]} c_i(k-c_i) > A\) becomes \(0 > A\), contradicting \(A \in [0,1]\). Note under the constraint \(\sum_{i \in [s]} c_i(k-c_i) = A\), we have

\[\sum_{i \in [s]} c_i(k-c_i) = k(\sum_{i \in [s]} c_i) - \sum_{i \in [s]} c_i^2 = k \cdot f(c_1,c_2,\ldots,c_s) - \sum_{i \in [s]} c_i^2 = A\]

so that \(f(c_1,c_2,\ldots,c_s) = \frac{A}{k} + \frac{1}{k}(\sum_{i \in [s]} c_i^2)\).
We argue that under the constraint \(\sum_{i \in [s]} c_i(k-c_i) = A\), the function \(f(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i = \frac{A}{k} + \frac{1}{k}(\sum_{i \in [s]} c_i^2)\) has a maximum. Note that

\[f(c_1,c_2,\ldots,c_s) = f(|c_1|,|c_2|,\ldots,|c_s|)\]

so that we may assume \(c_i \geq 0\) for all \(i \in [s]\). The assumption \(c_i \geq 0\) for all \(i \in [s]\) along with the constraint \(\sum_{i \in [s]} c_i(k-c_i) = A\) give rise to a compact space; since \(c_i(k-c_i) \leq \frac{k^2}{4}\) for all \(i \in [s]\), if for any \(j \in [s]\) we have \(c_j\) becomes large enough so that \(c_j(k-c_j) < -(s-1)\frac{k^2}{4}\), then \(\sum_{i \in [s]} c_i(k-c_i) < 0 \leq A\). Since \(f\) is continuous, it has a maximum in the compact space defined by \(c_i \geq 0\) for all \(i \in [s]\) and \(\sum_{i \in [s]} c_i(k-c_i) = A\), and thus has a maximum with only the constraint \(\sum_{i \in [s]} c_i(k-c_i) = A\).
We now use Lagrange multipliers to find the maximum of \(f(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i\) under the constraint \(\sum_{i \in [s]} c_i(k-c_i) = A\). We note \(\frac{\partial f}{\partial c_i} = 1\) for all \(i \in [s]\). Define \(g(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i(k-c_i)\), and so \(\frac{\partial g}{\partial c_i} = k - 2c_i\) for all \(i \in [s]\). Thus for some \(\lambda \in \mathbb{R}\) we have

\[\begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix} = \lambda \begin{pmatrix} k-2c_1 \\ k-2c_2 \\ \vdots \\ k-2c_s \end{pmatrix}\]

and so \(1 = \lambda(k-2c_i)\) for all \(i \in [s]\). Note we cannot have \(\lambda = 0\), otherwise \(1 = 0\), and so \(k-2c_i = \frac{1}{\lambda}\) for all \(i \in [s]\), which implies for all \(i,j \in [s]\) we have \(k-2c_i = k-2c_j\) so that \(c_i = c_j\). Note

\[A = \sum_{i \in [s]} c_i(k-c_i) = \sum_{i \in [s]} c_1(k-c_1) = sc_1(k-c_1)\]

so that \(c_1(k-c_1) = \frac{A}{s}\), which implies \(c_1^2 - kc_1 = -\frac{A}{s}\), and thus \((c_1 - \frac{k}{2})^2 = \frac{k^2}{4} - \frac{A}{s}\) and so \(c_1 = \frac{k}{2} \pm \sqrt{\frac{k^2}{4}-\frac{A}{s}}\). Note \(c_1 = \frac{k}{2} + \sqrt{\frac{k^2}{4}-\frac{A}{s}}\) is the larger of the two, and therefore

\[\sum_{i \in [s]} c_i = \sum_{i \in [s]} c_1 = s(\frac{k}{2} + \sqrt{\frac{k^2}{4}-\frac{A}{s}}).\]

Now we show \(s(\frac{k}{2} - \sqrt{\frac{k^2}{4}-\frac{A}{s}}) \leq \sum_{i \in [s]} \min\{c_i,d_i\}\). Without loss of generality assume \(c_i = \min\{c_i,d_i\}\) for all \(i \in [s]\), so we need to show \(\sum_{i \in [s]} c_i \geq s(\frac{k}{2} - \sqrt{\frac{k^2}{4}-\frac{A}{s}})\). We find a lower bound on the minimum of \(f(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i\) under the above constraints; the minimum exists because the constrained space is compact and \(f\) is continuous with respect to \(c_i\) and \(d_i\). First note we may replace the constraint \(c_i + d_i \leq k\) with \(c_i + d_i = k\) for all \(i \in [s]\). If for some \(j \in [s]\) we had \(c_j+d_j < k\), then we can increase \(d_j\) so that \(c_j + d_j = k\) without affecting the value of \(f(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i\) while still maintaining the constraints. Thus the constraint \(\sum_{i \in [s]} c_id_i \geq A\) becomes \(\sum_{i \in [s]} c_i(k-c_i) \geq A\).
Next, we show that we may assume \(\sum_{i \in [s]} c_i(k-c_i) = A\). If \(\sum_{i \in [s]} c_i(k-c_i) > A\), for any \(i \in [s]\) we may decrease \(c_i\) so that \(f(c_1,c_2,\ldots,c_s) = \sum_{i \in [s]} c_i\) attains a smaller value while still maintaining the constraints, unless \(c_i = 0\) for all \(i \in [s]\) in which case the inequality \(\sum_{i \in [s]} c_i(k-c_i) > A\) becomes \(0 > A\), a contradiction. From this point on, the argument is analogous to the one showing \(\sum_{i \in [s]} \max\{c_i,d_i\} \leq s(\frac{k}{2} + \sqrt{\frac{k^2}{4}-\frac{A}{s}})\). ◻

Proof. From the constraint \(c_i+d_i \leq k\) for all \(i \in [r]\), we have that \(c_id_i \leq \frac{k^2}{4}\). Thus

\[\begin{align} 1 \leq \sum_{i \in [r]} c_id_i = \sum_{i \in [s]} c_id_i + \sum_{i \in [r] \setminus [s]} c_id_i &\leq \sum_{i \in [s]} c_id_i + \sum_{i \in [r] \setminus [s]} \frac{k^2}{4} \\ &= \sum_{i \in [s]} c_id_i +(r-s)\frac{k^2}{4} \end{align}\]

so that \(\sum_{i \in [s]} c_id_i \geq 1 - (r-s)\frac{k^2}{4}\). Apply Lemma 4 with \(A = 1 - (r-s)\frac{k^2}{4}\), and we see that

\[\sqrt{\frac{k^2}{4}-\frac{A}{s}} = \sqrt{\frac{k^2}{4}-\frac{1}{s}(1 - (r-s)\frac{k^2}{4})} = \sqrt{\frac{rk^2}{4s}-\frac{1}{s}}.\] ◻

Proof. Let \(|R| \leq t\). Without loss of generality, if \(a(R) > 0\), by constraint (5) this would imply

\[\sum_{i \in R} b_i \geq 1.\]

Thus for some \(i \in R\) we have \(b_i \geq \frac{1}{|R|} = \frac{1}{t}\), and so \(a_i + b_i \geq \frac{1}{t}\), a contradiction.
 ◻

Proof. To see that \(g^*(5) \leq \frac{11}{12}\), consider

We now show \(g^*(5) \geq \frac{11}{12}\). Consider any solution \(a,b : \mathcal{P}([5]) \rightarrow [0,1]\) satisfying constraints (1), (2), (3), and (5). We may assume \(a_i + b_i \leq \frac{11}{12}\) for all \(i \in [5]\). By Lemma 5, we note for \(R \subseteq [5]\), if \(|R| \leq 1\) then \(a(R) = b(R) = 0\), since \(a_i + b_i \leq \frac{11}{12} < \frac{1}{1}\) for all \(i \in [5]\). We have

\[\sum_{R \subseteq [5]} |R| \cdot a(R) + |R| \cdot b(R) = \sum_{i \in [5]} a_i + b_i \leq 5 \cdot \frac{11}{12} = \frac{55}{12}.\]

Without loss of generality we may thus assume \(\sum_{R \subseteq [5]} |R| \cdot a(R) \leq \frac{1}{2} \cdot \frac{55}{12} = \frac{55}{24}\). This gives us

\[\begin{align} \frac{55}{24} \geq \sum_{R \subseteq [5]} |R| \cdot a(R) &= \left( \sum_{R \subseteq [5], |R| = 2} |R| \cdot a(R) \right) + \left( \sum_{R \subseteq [5], |R| \geq 3} |R| \cdot a(R) \right) \\ &\geq \left( \sum_{R \subseteq [5], |R| = 2} 2 \cdot a(R) \right) + \left( \sum_{R \subseteq [5], |R| \geq 3} 3 \cdot a(R) \right) \\ &= 2 \left( \sum_{R \subseteq [5], |R| = 2} a(R) \right) + 3 \left( \sum_{R \subseteq [5], |R| \geq 3} a(R) \right) \\ &= 2 \left( \sum_{R \subseteq [5], |R| = 2} a(R) + \sum_{R \subseteq [5], |R| \geq 3} a(R) \right) + \left( \sum_{R \subseteq [5], |R| \geq 3} a(R) \right) \\ &= 2 + \left( \sum_{R \subseteq [5], |R| \geq 3} a(R) \right). \end{align}\]

So we get \(\frac{55}{24} \geq 2 + \sum_{R \subseteq [5], |R| \geq 3} a(R)\), which implies

\[\sum_{R \subseteq [5], |R| \geq 3} a(R) \leq \frac{55}{24} - 2 = \frac{7}{24}.\]

This implies

\[\sum_{R \subseteq [5], |R| = 2} a(R) \geq 1- \frac{7}{24} = \frac{17}{24}\]

Recall we have that \(\sum_{R \subseteq [5]} |R| \cdot a(R) + |R| \cdot b(R) \leq \frac{55}{12}\) and we also have

\[\sum_{R \subseteq [5]} |R| \cdot a(R) = \sum_{R \subseteq [5], |R| \geq 2} |R| \cdot a(R) \geq 2\]

thus

\[\sum_{R \subseteq [5]} |R| \cdot b(R) \leq \frac{55}{12} - 2 = \frac{31}{12}.\]

Thus we have

\[\begin{align} \frac{31}{12} \geq \sum_{R \subseteq [5]} |R| \cdot b(R) &= \left( \sum_{R \subseteq [5], |R| = 2} |R| \cdot b(R) \right) + \left( \sum_{R \subseteq [5], |R| \geq 3} |R| \cdot b(R) \right) \\ &\geq 2 \left( \sum_{R \subseteq [5], |R| = 2} b(R) \right) + 3 \left( \sum_{R \subseteq [5], |R| \geq 3} b(R) \right) \\ &= 2 + \left( \sum_{R \subseteq [5], \;|R| \geq 3} b(R) \right) \end{align}\]

and so \(\frac{31}{12} \geq 2 + \sum_{R \subseteq [5], |R| \geq 3} b(R)\), thus

\[\sum_{R \subseteq [5], \;|R| \geq 3} b(R) \leq \frac{31}{12} - 2 = \frac{7}{12}\]

which in turn implies

\[\sum_{R \subseteq [5],|R| = 2} b(R) \geq \frac{5}{12}.\]

Claim 1: For \(i,j,k,l\) distinct, we can’t have both \(b(\{i,j\}) >0\) and \(b(\{k,l\}) > 0\). Assume for the sake of contradiction otherwise, and without loss of generality assume \(i = 1, j = 2, k = 3, l = 4\) so that \(b(\{1,2\}) > 0\) and \(b(\{3,4\}) > 0\). This implies that \(a_1 + a_2 \geq 1\) and \(a_3 + a_4 \geq 1\) respectively. Without loss of generality, assume \(a_1 \geq \frac{1}{2}\), so that since \(\sum_{R \subseteq [5], |R| = 2} a(R) \geq \frac{17}{24} > 1 - \frac{1}{2}\) from (7), we must have \(a(\{1,i\}) > 0\) for some \(i \in [5] \setminus \{1\}\). Furthermore since \(b(\{3,4\}) > 0\) and so \(a'(\{3\}^{\uparrow} \cup \{4\}^{\uparrow}) = 1\), we may assume without loss of generality \(i = 3\) so that \(a(\{1,3\}) > 0\). This implies that \(b_1 + b_3 \geq 1\). Since \(a_i + b_i \leq \frac{11}{12}\) for all \(i \in [5]\) and \(a_1 \geq \frac{1}{2}\), we must have that \(b_1 \leq \frac{5}{12}\) so that \(b_3 \geq \frac{7}{12}\), which in turn implies \(a_3 \leq \frac{1}{3}\). Since \(a_3 \leq \frac{1}{3}\) and \(a_3 + a_4 \geq 1\), we must have \(a_4 \geq \frac{2}{3}\) and so \(b_4 \leq \frac{1}{4}\).
Now we note with the constraints \(a_1 + a_2 \geq 1\) and \(a_i+b_i \leq \frac{11}{12}\) for \(i \in [2]\), we have \(a_1b_1 + a_2b_2 \leq \frac{5}{12}\) by Lemma 3 as \(\frac{11}{12} \leq \frac{2}{2} = 1\). Since \(a_3 \leq \frac{1}{3}, b_3 \geq \frac{7}{12}\) we have \(a_3b_3 \leq \frac{7}{36}\). Since \(a_4 \geq \frac{2}{3}\) and \(b_4 \leq \frac{1}{4}\), we have \(a_4b_4 \leq \frac{1}{6}\). Thus we have

\[a_1b_1 + a_2b_2 + a_3b_3 + a_4b_4 \leq \frac{5}{12} + \frac{7}{36} + \frac{1}{6} = \frac{28}{36} = \frac{7}{9}.\]

This implies \(a_5b_5 \geq 1 - \frac{7}{9} = \frac{2}{9}\). But since \(a_5 + b_5 \leq \frac{11}{12}\), we have \(a_5b_5 \leq (\frac{1}{2} \cdot \frac{11}{12})^2 < \frac{2}{9}\), a contradiction.
Claim 2: We show we cannot have both \(b(\{i,j\}) > 0\) and \(b(\{i,k\}) > 0\) for \(i,j,k \in [5]\) distinct. Assume otherwise for the sake of contradiction, and without loss of generality assume \(i=1,j=2,k=3\), so that \(b(\{1,2\}) > 0\) and \(b(\{1,3\}) > 0\). This implies that \(a_1 + a_2 \geq 1\) and \(a_1 + a_3 \geq 1\) respectively. By Corollary 1, \(a_1 \leq 0.69\). This implies \(a'(\{2,3\}^{\uparrow} \setminus \{1\}^{\uparrow}) \geq 1-0.69 = 0.31\) because \(b(\{1,2\}) > 0\) and \(b(\{1,3\}) > 0\) which implies if \(a(R) > 0\) and \(1 \not \in R\) then \(2,3 \in R\). Recall \(\sum_{R \subseteq [5], |R| = 2} a(R) \geq \frac{17}{24}\) from (7), and we note that \(\frac{17}{24} > 1 - 0.31\), so that \(a(\{2,3\}) > 0\), and so \(b_2 + b_3 \geq 1\).
We now show that \(\{1,2\}, \{1,3\}\) are the only two subsets \(R \subseteq [5]\) that satisfy \(|R| = 2\) and and \(b(R) > 0\). Consider some \(R \subseteq [5]\) such that \(b(R) > 0\) and \(|R| = 2\). Without loss of generality, we can assume \(2 \in R\) because \(a(\{2,3\}) > 0\). If \(1 \in R\) we just have \(R = \{1,2\}\), so we are done. If \(3 \in R\), then we have \(b(\{2,3\}) > 0\) and so \(a_2 + a_3 \geq 1\). But recall we also have \(b_2 + b_3 \geq 1\), so that \((a_2 + b_2) + (a_3 + b_3) \geq 2\), so that either \(a_2 + b_2 \geq 1\) or \(a_3 + b_3 \geq 1\), contradicting \(a_i + b_i \leq \frac{11}{12}\) for all \(i \in [5]\). Thus without loss of generality let \(4 \in R\), so \(R = \{2,4\}\). So we have \(b(\{2,4\}) > 0\), but we also have \(b(\{1,3\}) > 0\) by assumption, contradicting Claim 1.
The previous paragraph shows that if \(R \neq \{1,2\}, \{1,3\}\) and \(b(R) > 0\), then \(|R| \geq 3\). Recall equation (8)

\[\sum_{R \subseteq [5], |R| = 2} b(R) = b(\{1,2\}) + b(\{1,3\}) \geq \frac{5}{12}.\]

This gives us \(b_1 \geq \frac{5}{12}\) so that \(a_1 \leq \frac{1}{2}\). Since \(a_1 + a_2 \geq 1\) and \(a_1 + a_3 \geq 1\), this implies \(a_2,a_3 \geq \frac{1}{2}\), and so \(b_2,b_3 \leq \frac{5}{12}\) and thus \(b_2 + b_3 \leq \frac{5}{6}\), contradicting \(b_2 + b_3 \geq 1\).
We now finally show \(g^*(5) \geq \frac{11}{12}\). From (8), we know there exists \(|R| = 2\) such that \(b(R) > 0\), so without loss of generality assume \(b(\{1,2\}) > 0\). This implies \(a_1 + a_2 \geq 1\). This in turn implies \(b_1 + b_2 \leq 2 \cdot \frac{11}{12} - 1 = \frac{5}{6}\). In particular, \(b'(\{1\}^{\uparrow} \cup \{2\}^{\uparrow}) \leq \frac{5}{6}\), which implies \(\sum_{R \subseteq [5] \setminus [2]} b(R) \geq \frac{1}{6}\). We claim \(\sum_{R \subseteq [5] \setminus [2]} b(R) = b(\{3,4,5\})\) so that \(b(\{3,4,5\}) \geq \frac{1}{6}\). Note \(b(R) > 0\) implies \(|R| \geq 2\), and if \(|R| = 2\) and \(R \subseteq [5] \setminus [2]\), this would contradict Claim 1 as we also have \(b(\{1,2\}) > 0\). Thus \(|R| = 3\) and so \(R = \{3,4,5\}\).
We claim that if \(b(R) > 0\) and \(|R| = 2\), then \(R = \{1,2\}\). So assume \(b(R) > 0\) and \(|R| = 2\). First assume \(1 \in R\). If \(2 \in R\) we are done. If \(3 \in R\), we’d have \(R = \{1,3\}\), contradicting claim 2 because \(b(\{1,2\}) > 0\) as well. Likewise if \(4,5 \in R\). If we start off with the assumption \(2 \in R\), we get a symmetric argument. Thus \(R\) cannot contain \(1,2\). This means \(R \subseteq [5] \setminus [2]\), so by the preceding paragraph we have \(R = \{3,4,5\}\), and so \(|R| \neq 2\).
Recall equation (8) that \(\sum_{R \subseteq [5], |R| = 2} b(R) = b(\{1,2\}) \geq \frac{5}{12}\). So \(b_1, b_2 \geq \frac{5}{12}\). Recall we also had \(a_1+a_2 \geq 1\). Thus \((a_1+b_1)+(a_2+b_2) \geq 1 + 2 \cdot \frac{5}{12} = \frac{11}{6}\), so for some \(i \in [2]\) we have \(a_i+b_i \geq \frac{11}{12}\), as required. ◻

Proof. We find an upper bound on the maximum of \(\sum_{i \in [s]} c_id_i\) under the constraints above. The maximum exists because \(\sum_{i \in [s]} c_id_i\) is continuous and the constrained space is compact with respect to \(c_i,d_i\). We may assume \(c_i + d_i = k\) for all \(i \in [s]\), because if \(c_j + d_j < k\) for some \(j \in [s]\), then we may increase both \(c_j,d_j\) so that \(\sum_{i \in [s]} c_id_i\) increases. Thus we can just consider maximizing

\[f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\]

and the constraint \(\sum_{i \in I \sqcup O_2} d_i \geq 1\) becomes

\[\sum_{i \in I \sqcup O_2} k-c_i \geq 1.\]

We now show we can assume \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2} k-c_i = 1\). We first note that the derivative of \(g(x) = x(k-x)\) is \(g'(x) = k-2x\), and so \(g(x)\) is maximized at \(x = \frac{k}{2}\). Furthermore, \(g''(x) = -2\) so that if \(x\) approaches \(\frac{k}{2}\) we know \(g(x)\) increases. If we had \(\sum_{i \in I \sqcup O_1} c_i > 1\), this would imply for some \(j \in I \sqcup O_1\) we had \(c_j > \frac{1}{|I| + |O_1|} > \frac{k}{2}\), where the last inequality comes from \(k < \frac{2}{|I|+|O_1|}\). Thus we may decrease \(c_j\) so that \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) attains a larger value while still maintaining the constraints. So let \(\sum_{i \in I \sqcup O_1} c_i = 1\) be the new constraint in place of \(\sum_{i \in I \sqcup O_1} c_i \geq 1\).
Now we show we may assume \(\sum_{i \in I \sqcup O_2} k-c_i = 1\). So assume otherwise that \(\sum_{i \in I \sqcup O_2} k-c_i > 1\). Note if for some \(j \in O_2\) we had \(k - c_j > \frac{k}{2}\), then we may increase \(c_j\) so that \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) attains a larger value while still maintaining the constraints. So assume for all \(i \in O_2\), we have \(k-c_i \leq \frac{k}{2}\). If for some \(j \in O_2\) we had \(k-c_j < \frac{k}{2}\), then we may decrease \(c_j\) so that \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) attains a larger value while still maintaining the constraints. So assume \(k-c_i = \frac{k}{2}\) for all \(i \in O_2\). Thus \(\sum_{i \in O_2} k-c_i = |O_2|\frac{k}{2}\), so along with \(\sum_{i \in I \sqcup O_2} k-c_i > 1\) we get \(\sum_{i \in I} k-c_i > 1 - | O_2|\frac{k}{2}\), and so

\[\sum_{i \in I} c_i < |I|k + |O_2|\frac{k}{2} - 1 = (2|I| + |O_2|)\frac{k}{2}-1.\]

Since \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I} c_i < (2|I| + |O_2|)\frac{k}{2}-1\), we must have

\[\sum_{i \in O_1} c_i = 1-\sum_{i \in I} c_i > 2-(2|I| + |O_2|)\frac{k}{2}\]

and thus for some \(j \in O_1\) we have \(c_j > \frac{2}{|O_1|} - \frac{k(2|I|+|O_1|)}{2|O_1|} > \frac{k}{2}\), where the last inequality can be rearranged into \(\frac{k}{2} < \frac{1}{|I|+|O_1|}\). From \(\sum_{i \in I} c_i < (2|I| + |O_2|)\frac{k}{2}-1\) we also get for some \(l \in I\) we have \(c_l < (2+\frac{|O_2|}{|I|})\frac{k}{2} - \frac{1}{|I|} < \frac{k}{2}\) where the last inequality can also be rearranged into \(\frac{k}{2} < \frac{1}{|I|+|O_1|}\).
Note we can increase \(c_l\) by \(\epsilon > 0\) and decrease \(c_j\) by \(\epsilon\) so that \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) attains a larger value while still maintaining the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } k-c_i \geq 1\). The constraint \(\sum_{i \in I \sqcup O_1} c_i = 1\) is preserved because the \(\epsilon\)’s cancel out. The constraint \(\sum_{i \in I \sqcup O_2 } k-c_i \geq 1\) can be preserved for small enough \(\epsilon\) because by assumption \(\sum_{i \in I \sqcup O_2 } k-c_i > 1\). Thus under the assumption \(\sum_{i \in I \sqcup O_2 } k-c_i > 1\), we can always find a larger value of \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) while maintaining the desired constraints, so we may assume \(\sum_{i \in I \sqcup O_2} k-c_i = 1\).
We claim under the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } k-c_i = 1\), the function \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) has a maximum. From the constraint \(\sum_{i \in I \sqcup O_2 } k-c_i = 1\) we get that \(\sum_{i \in I \sqcup O_2} c_i = (|I| + |O_2|)k-1\). Note we have

\[\begin{align} f(c_1,c_2,\ldots,c_{s}) &= \sum_{i \in [s]} c_i(k-c_i) = k \left( \sum_{i \in [s]} c_i \right) - \sum_{i \in [s]} c_i^2 \\ &= k \left( \sum_{i \in I \sqcup O_1} c_i + \sum_{i \in O_2} c_i \right) - \sum_{i \in [s]} c_i^2 = k \left( 1+ \sum_{i \in O_2} c_i \right) - \sum_{i \in [s]} c_i^2. \end{align}\]

This shows for any \(i \in I \sqcup O_1\), we have

\[f(c_1,c_2, \ldots, c_i, \ldots, c_s) = f(c_1,c_2, \ldots, |c_i|, \ldots, c_s)\]

and analogously

\[\begin{align} f(c_1,c_2,\ldots,c_{s}) &= \sum_{i \in [s]} c_i(k-c_i) = k \left( \sum_{i \in [s]} c_i \right) - \sum_{i \in [s]} c_i^2 \\ &= k \left( \sum_{i \in O_1} c_i + \sum_{i \in I \sqcup O_2} c_i \right) - \sum_{i \in [s]} c_i^2 \\ &= k \left( \left( \sum_{i \in O_1} c_i \right) + (|I| + |O_2|)k-1 \right) - \sum_{i \in [s]} c_i^2 \end{align}\]

which shows for any \(i \in I \sqcup O_2\), we have

\[f(c_1,c_2, \ldots, c_i, \ldots, c_s) = f(c_1,c_2, \ldots, |c_i|, \ldots, c_s).\]

Thus \(f(c_1,c_2,\ldots,c_s) = f(|c_1|,|c_2|,\ldots,|c_s|)\), so we may assume \(c_i \geq 0\) for all \(i \in [s]\). Note along with the assumption \(c_i \geq 0\) for all \(i \in [s]\), the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } k-c_i = 1\) give rise to a compact space, and since \(f\) is continuous we know \(f\) attains a maximum in this compact space defined by the assumption \(c_i \geq 0\) for all \(i \in [s]\) with the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } k-c_i = 1\), and thus \(f\) attains a maximum with the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } k-c_i = 1\) only.
We use Lagrange multipliers to maximize \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) under the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } k-c_i = 1\). We have \(\frac{\partial f}{\partial c_i} = k - 2c_i\) for all \(i \in [s]\). Define \(g_1(c_1,c_2,\ldots,c_s) = \sum_{i \in I \sqcup O_1} c_i\) and \(g_2(c_1,c_2,\ldots,c_s) = -(\sum_{i \in I \sqcup O_2 } k-c_i)\). So \(\frac{\partial g_1}{\partial c_i} = 1\) if \(i \in I \cup O_1\) and \(0\) otherwise, and \(\frac{\partial g_2}{\partial c_i} = 1\) if \(i \in I \cup O_2\) and \(0\) otherwise. Thus for some \(\lambda_1,\lambda_2 \in \mathbb{R}\) we have \(k-2c_i = \lambda_1+\lambda_2\) for all \(i \in I\), and \(k-2c_i = \lambda_1\) for all \(i \in O_1\), and \(k-2c_i = \lambda_2\) for all \(i \in O_2\). This gives us for all \(i,j \in I\) we have \(c_i = c_j\), for all \(i,j \in O_1\) we have \(c_i = c_j\), and for all \(i,j \in O_2\) we have \(c_i = c_j\).
Without loss of generality, let \(c_1 \in O_1, c_2 \in O_2, c_3 \in I\). We get

\[\sum_{i \in I \sqcup O_1} c_i = \sum_{i \in I} c_i + \sum_{i \in O_1} c_i = \sum_{i \in I} c_3 + \sum_{i \in O_1} c_1 = |I|c_3 + |O_1|c_1 = 1.\]

Likewise

\[\sum_{i \in I \sqcup O_2} k-c_i = \sum_{i \in I}k- c_i + \sum_{i \in O_2}k- c_i = |I|(k-c_3) + |O_2|(k-c_2) = 1.\]

Thus we get \(|I|c_3 + |O_1|c_1 =|I|(k-c_3) + |O_2|(k-c_2)\), and so

\[2|I|c_3 = |I|k+|O_1|(k-c_2-c_1)\]

which gives us \(2c_3 = k+ \frac{|O_1|}{|I|}(k-c_2-c_1)\). Recall also that \(k-2c_3 = \lambda_1 + \lambda_2 = k-2c_1+k-2c_2\) and thus \(2c_3 = 2c_1+2c_2-k\). Thus we have

\[2c_1+2c_2-k = 2c_3 = k+\frac{|O_1|}{|I|}(k-c_2-c_1)\]

which rearranges into

\[0 = (\frac{|O_1|}{|I|} + 2)(k-c_2-c_1)\]

and thus \(c_1+c_2 = k\).
Recall \(2c_3 = 2c_1+2c_2 - k\), so along with \(c_1+c_2 = k\) we get \(2c_3 = k\) so that \(c_3 = \frac{k}{2}\). Recall also that \(|I|c_3 + |O_1|c_1 = 1\), so that

\[c_1 = \frac{1}{|O_1|}(1-|I|\frac{k}{2}) = \frac{2-|I|k}{2|O_1|} = e.\]

Note from \(c_1+c_2 = k\) we get \(c_1(k-c_1) = c_2(k-c_2)\) Finally, we compute

\[\begin{align} f(c_1,c_2,\ldots,c_s) &= |I|c_3(k-c_3) + |O_1|c_1(k-c_1)+|O_2|c_2(k-c_2) \\ &= |I|\frac{k^2}{4} + 2|O_1| \cdot e(k-e) \end{align}\]

as required. ◻

Proof. To see that \(g^*(6) \leq \frac{5}{6}\), consider

Now we show \(g^*(6) \geq \frac{5}{6}\). Consider any solution \(a,b : \mathcal{P}([6]) \rightarrow [0,1]\) satisfying constraints (1), (2), (3), and (5). We may assume \(a_i+b_i \leq \frac{5}{6}\) for all \(i \in [6]\). By Lemma 5, if \(|R| \leq 1\) then \(a(R) = b(R) = 0\), as \(a_i + b_i \leq \frac{5}{6} < \frac{1}{1}\) for all \(i \in [6]\).
We claim there do not exist \(R_1,R_2 \subseteq [6]\) such that \(a(R_1), b(R_2) > 0\) and \(|R_1|=|R_2| = 2\). Assume otherwise for the sake of contradiction. By constraint (5), we have \(R_1 \cap R_2 \neq \{\}\), so we may without loss of generality assume \(1 \in R_1 \cap R_2\). If without loss of generality \(R_1 = R_2 = \{1,2\}\), then we have \(a(\{1,2\}),b(\{1,2\}) > 0\) which implies \(b_1+b_2 \geq 1\) and \(a_1+a_2 \geq 1\) respectively, so that \((a_1+b_1) + (a_2+b_2) \geq 2\) and thus for some \(i \in [2]\) we have \(a_i+b_i \geq 1\), contradicting \(a_i+b_i \leq \frac{5}{6}\). Now without loss of generality assume \(R_1 = \{1,2\}\) and \(R_2 = \{1,3\}\) so that \(a(\{1,2\}) > 0\) and \(b(\{1,3\}) > 0\) which implies \(b_1 + b_2 \geq 1\) and \(a_1 + a_3 \geq 1\) respectively. Apply Lemma 6 with \(I = \{1\}, O_1 = \{2\}, O_2 = \{3\}\) and \(k = \frac{5}{6}\). We just need to check \(\frac{5}{6} < \frac{2}{1+1}\), which is true. Thus Lemma 6 says that \(a_1b_1 + a_2b_2 + a_3b_3 \leq 0.47\). Thus we have \(3 \cdot (\frac{1}{2} \cdot \frac{5}{6})^2 \geq a_4b_4 + a_5b_5 + a_6b_6 \geq 1-0.47 = 0.53\), a contradiction.
Thus we may without loss of generality assume if \(a(R) > 0\), then \(|R| \geq 3\). Thus

\[\begin{align} \sum_{i \in [6]} a_i + b_i &= \sum_{R \subseteq [r]} |R| \cdot a(R) + |R| \cdot b(R) \\ &= \left( \sum_{R \subseteq [r], |R| \geq 3} |R| \cdot a(R) \right) + \left( \sum_{R \subseteq [r], |R| \geq 2} |R| \cdot b(R) \right) \\ &\geq \left( \sum_{R \subseteq [r], |R| \geq 3} 3 \cdot a(R) \right) + \left( \sum_{R \subseteq [r], |R| \geq 2} 2 \cdot b(R) \right) = 5. \end{align}\]

This implies \(a_i + b_i \geq \frac{5}{6}\) for some \(i \in [6]\), as required. ◻

Proof. We find an upper bound on the maximum of \(\sum_{i \in [s]} c_id_i\) under the constraints above. The maximum exists because \(\sum_{i \in [s]} c_id_i\) is continuous and the constrained space is compact with respect to \(c_i,d_i\). We may assume \(c_i + d_i = k\) for all \(i \in [s]\), because if \(c_j + d_j < k\) for some \(j \in [s]\), then we may increase both \(c_j,d_j\) so that \(\sum_{i \in [s]} c_id_i\) increases. Thus we can just consider maximizing

\[f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i).\]

We now show we can assume \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2} c_i = 1\). We first note that the derivative of \(g(x) = x(k-x)\) is \(g'(x) = k-2x\), and so \(g(x)\) is maximized at \(x = \frac{k}{2}\). Furthermore, \(g''(x) = -2\) so that if \(x\) approaches \(\frac{k}{2}\) we know \(g(x)\) increases. If we had \(\sum_{i \in I \sqcup O_1} c_i > 1\), this would imply for some \(j \in I \sqcup O_1\) we had \(c_j > \frac{1}{|I| + |O_1|} > \frac{k}{2}\), where the last inequality comes from \(k < \frac{2}{|I| + |O_1|}\). Thus we may decrease \(c_j\) so that \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) attains a larger value while still maintaining the constraints. So let \(\sum_{i \in I \sqcup O_1} c_i = 1\) be the new constraint in place of \(\sum_{i \in I \sqcup O_1} c_i \geq 1\).
Now we show we may assume \(\sum_{i \in I \sqcup O_2} c_i = 1\). So assume otherwise that \(\sum_{i \in I \sqcup O_2} c_i > 1\). Note if for some \(j \in O_2\) we had \(c_j > \frac{k}{2}\), then we may decrease \(c_j\) so that \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) attains a larger value while still maintaining the constraints. So assume for all \(i \in O_2\), we have \(c_i \leq \frac{k}{2}\). If for some \(j \in O_2\) we had \(c_j < \frac{k}{2}\), then we may increase \(c_j\) so that \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) attains a larger value while still maintaining the constraints. So assume \(c_i = \frac{k}{2}\) for all \(i \in O_2\). Thus \(\sum_{i \in O_2} c_i = |O_2|\frac{k}{2}\), so along with \(\sum_{i \in I \sqcup O_2} c_i > 1\) we get \(\sum_{i \in I} c_i > 1 - | O_2|\frac{k}{2}\).
Since \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I} c_i > 1 - | O_2|\frac{k}{2}\), we must have

\[\sum_{i \in O_1} c_i = 1-\sum_{i \in I} c_i < | O_2|\frac{k}{2}\]

and thus for some \(j \in O_1\) we have \(c_j < \frac{|O_2|}{|O_1|} \frac{k}{2} = \frac{k}{2}\). From \(\sum_{i \in I} c_i > 1 - | O_2|\frac{k}{2}\) we also get for some \(l \in I\) we have \(c_l > \frac{1}{|I|} - \frac{|O_2|}{|I|}\frac{k}{2} > \frac{k}{2}\) where the last inequality can also be rearranged into \(\frac{k}{2} < \frac{1}{|I|+|O_1|}\).
Note we can decrease \(c_l\) by \(\epsilon > 0\) and increase \(c_j\) by \(\epsilon\) so that \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) attains a larger value while still maintaining the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } c_i \geq 1\). The constraint \(\sum_{i \in I \sqcup O_1} c_i = 1\) is preserved because the \(\epsilon\)’s cancel out. The constraint \(\sum_{i \in I \sqcup O_2 } c_i \geq 1\) can be preserved for small enough \(\epsilon\) because by assumption \(\sum_{i \in I \sqcup O_2 } c_i > 1\). Thus under the assumption \(\sum_{i \in I \sqcup O_2 } k-c_i > 1\), we can always find a larger value of \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) while maintaining the desired constraints, so we may assume \(\sum_{i \in I \sqcup O_2} c_i = 1\).
We claim under the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } c_i = 1\), the function \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) has a maximum. Note we have

\[\begin{align} f(c_1,c_2,\ldots,c_{s}) &= \sum_{i \in [s]} c_i(k-c_i) = k \left( \sum_{i \in [s]} c_i \right) - \sum_{i \in [s]} c_i^2 \\ &= k \left( \sum_{i \in I \sqcup O_1} c_i + \sum_{i \in O_2} c_i \right) - \sum_{i \in [s]} c_i^2 \\ &= k \left( 1+ \sum_{i \in O_2} c_i \right) - \sum_{i \in [s]} c_i^2. \end{align}\]

This shows for any \(i \in I \sqcup O_1\), we have

\[f(c_1,c_2, \ldots, c_i, \ldots, c_s) = f(c_1,c_2, \ldots, |c_i|, \ldots, c_s)\]

and analogously

\[\begin{align} f(c_1,c_2,\ldots,c_{s}) &= \sum_{i \in [s]} c_i(k-c_i) = k \left( \sum_{i \in [s]} c_i \right) - \sum_{i \in [s]} c_i^2 \\ &= k \left( \sum_{i \in O_1} c_i + \sum_{i \in I \sqcup O_2} c_i \right) - \sum_{i \in [s]} c_i^2 \\ &= k \left(1 + \sum_{i \in O_1} c_i \right) - \sum_{i \in [s]} c_i^2 \end{align}\]

which shows for any \(i \in I \sqcup O_2\), we have

\[f(c_1,c_2, \ldots, c_i, \ldots, c_s) = f(c_1,c_2, \ldots, |c_i|, \ldots, c_s).\]

Thus \(f(c_1,c_2,\ldots,c_s) = f(|c_1|,|c_2|,\ldots,|c_s|)\), so we may assume \(c_i \geq 0\) for all \(i \in [s]\). Note along with the assumption \(c_i \geq 0\) for all \(i \in [s]\), the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } c_i = 1\) give rise to a compact space, and since \(f\) is continuous we know \(f\) attains a maximum in this compact space defined by the assumption \(c_i \geq 0\) for all \(i \in [s]\) with the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } c_i = 1\), and thus \(f\) attains a maximum with the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } c_i = 1\) only.
We use Lagrange multipliers to maximize \(f(c_1,c_2,\ldots,c_{s}) = \sum_{i \in [s]} c_i(k-c_i)\) under the constraints \(\sum_{i \in I \sqcup O_1} c_i = 1\) and \(\sum_{i \in I \sqcup O_2 } c_i = 1\). We have \(\frac{\partial f}{\partial c_i} = k - 2c_i\) for all \(i \in [s]\). Define \(g_1(c_1,c_2,\ldots,c_s) = \sum_{i \in I \sqcup O_1} c_i\) and \(g_2(c_1,c_2,\ldots,c_s) = \sum_{i \in I \sqcup O_2 } c_i\). So \(\frac{\partial g_1}{\partial c_i} = 1\) if \(i \in I \cup O_1\) and \(0\) otherwise, and \(\frac{\partial g_2}{\partial c_i} = 1\) if \(i \in I \cup O_2\) and \(0\) otherwise. Thus for some \(\lambda_1,\lambda_2 \in \mathbb{R}\) we have \(k-2c_i = \lambda_1+\lambda_2\) for all \(i \in I\), and \(k-2c_i = \lambda_1\) for all \(i \in O_1\), and \(k-2c_i = \lambda_2\) for all \(i \in O_2\). This gives us for all \(i,j \in I\) we have \(c_i = c_j\), for all \(i,j \in O_1\) we have \(c_i = c_j\), and for all \(i,j \in O_2\) we have \(c_i = c_j\).
Without loss of generality, let \(c_1 \in O_1, c_2 \in O_2, c_3 \in I\). We get

\[\sum_{i \in I \sqcup O_1} c_i = \sum_{i \in I} c_i + \sum_{i \in O_1} c_i = \sum_{i \in I} c_3 + \sum_{i \in O_1} c_1 = |I|c_3 + |O_1|c_1 = 1.\]

Likewise

\[\sum_{i \in I \sqcup O_2} c_i = \sum_{i \in I}c_i + \sum_{i \in O_2}c_i = |I|c_3 + |O_2|c_2 = 1.\]

Thus we get \(|I|c_3 + |O_1|c_1 =|I|c_3 + |O_2|c_2\), and so \(|O_1|c_1 = |O_2|c_2\) so that \(c_1 = c_2\). Recall also that \(k-2c_3 = \lambda_1 + \lambda_2 = k-2c_1+k-2c_2 = 2k-4c_1\) and thus \(c_3 = 2c_1-\frac{k}{2}\). Recall \(|I|c_3 + |O_1|c_1 = 1\) and so \(c_1 = \frac{1}{|O_1|}(1-|I|c_3)\), which we substitute into \(c_3 = 2c_1-\frac{k}{2}\) to get

\[c_3 = \frac{2}{|O_1|}(1-|I|c_3)-\frac{k}{2}\]

which we re-arrange to get

\[c_3(\frac{2|I|+|O_1|}{|O_1|}) = \frac{2}{|O_1|} - \frac{k}{2}\]

and thus

\[\begin{align} c_3 &= \frac{|O_1|}{2|I|+|O_1|} (\frac{2}{|O_1|} - \frac{k}{2}) = \frac{2}{2|I|+|O_1|} - \frac{|O_1|}{2|I|+|O_1|}\frac{k}{2} \\ &= \frac{2}{2|I|+|O_1|} - \frac{k}{2} + \frac{2|I|}{2|I|+|O_1|}\frac{k}{2} = \frac{2+|I|k}{2|I|+|O_1|} - \frac{k}{2} = e_1. \end{align}\]

We have \(c_1 = \frac{1}{2}(c_3 + \frac{k}{2})\) so that

\[c_1 = \frac{1}{2}( \frac{2+|I|k}{2|I|+|O_1|} - \frac{k}{2} + \frac{k}{2}) = \frac{1+|I|\frac{k}{2}}{2|I|+|O_1|} = e_2.\]

Thus

\[\begin{align} f(c_1,c_2,\ldots,c_s) &= |I|e_1(k-e_1) + |O_1|e_2(k-e_2) + |O_2|e_2(k-e_2) \\ &= |I| \cdot e_1(k-e_1) + 2|O_1| \cdot e_2(k-e_2) \end{align}\]

as required. ◻

Proof. To see that \(g^*(7) \leq \frac{7}{9}\), consider

Now we show \(g^*(7) \geq \frac{7}{9}\). Consider any solution \(a,b : \mathcal{P}([7]) \rightarrow [0,1]\) satisfying constraints (1), (2), (3), and (5). We may assume \(a_i + b_i \leq \frac{7}{9}\) for all \(i \in [7]\). By Lemma 5 we have that if \(|R| \leq 1\) then \(a(R) = b(R) = 0\), since \(a_i + b_i \leq \frac{7}{9} < \frac{1}{1}\) for all \(i \in [7]\).
We claim there do not exist \(R_1,R_2 \subseteq [7]\) such that \(a(R_1), b(R_2) > 0\) and \(|R_1|=|R_2| = 2\). Assume otherwise for the sake of contradiction. By constraint (5), we have \(R_1 \cap R_2 \neq \{\}\), so we may without loss of generality assume \(1 \in R_1 \cap R_2\). If without loss of generality \(R_1 = R_2 = \{1,2\}\), then we have \(a(\{1,2\}),b(\{1,2\}) > 0\) which implies \(b_1+b_2 \geq 1\) and \(a_1+a_2 \geq 1\) respectively, so that \((a_1+b_1) + (a_2+b_2) \geq 2\) and thus for some \(i \in [2]\) we have \(a_i+b_i \geq 1\), contradicting \(a_i+b_i \leq \frac{7}{9}\). Now without loss of generality assume \(R_1 = \{1,2\}\) and \(R_2 = \{1,3\}\) so that \(a(\{1,2\}) > 0\) and \(b(\{1,3\}) > 0\) which implies \(b_1 + b_2 \geq 1\) and \(a_1 + a_3 \geq 1\) respectively. Apply Lemma 6 with \(I = \{1\}, O_1 = \{2\}, O_2 = \{3\}\) and \(k = \frac{7}{9}\). We just need to check \(\frac{7}{9} < \frac{2}{1+1}\) which is true. Thus Lemma 6 says that \(a_1b_1 + a_2b_2 + a_3b_3 \leq 0.36\). Thus we have \(3 \cdot (\frac{1}{2} \cdot \frac{7}{9})^2 \geq a_4b_4 + a_5b_5 + a_6b_6 \geq 1-0.36 = 0.64\), a contradiction.
So without loss of generality assume if \(b(R) > 0\), then \(|R| \geq 3\), so \(\sum_{i \in [7]} b_i = \sum_{R \subseteq [7]} b(R) \geq 3\), and thus since \(\sum_{i \in [7]} a_i + b_i \leq 7 \cdot \frac{7}{9} = \frac{49}{9}\), we must have that

\[\sum_{R \subseteq [7]} |R| \cdot a(R) = \sum_{i \in [7]} a_i \leq \frac{49}{9} - 3 = \frac{22}{9} = 2+ \frac{4}{9}.\]

Thus

\[\begin{align} 2+ \frac{4}{9} \geq \sum_{R \subseteq [7]} |R| \cdot a(R) &= \left( \sum_{R \subseteq [7], |R| = 2} |R| \cdot a(R) \right) + \left( \sum_{R \subseteq [7], |R| \geq 3} |R| \cdot a(R) \right) \\ &\geq 2\left( \sum_{R \subseteq [7], |R| = 2} a(R) \right) + 3\left( \sum_{R \subseteq [7], |R| \geq 3} a(R) \right) \\ &= 2 + \left( \sum_{R \subseteq [7], |R| \geq 3} a(R) \right) \end{align}\]

so that \(\sum_{R \subseteq [7], |R| \geq 3} a(R) \leq \frac{4}{9}\) and so \(\sum_{R \subseteq [7], |R| = 2} a(R) \geq 1- \frac{4}{9} = \frac{5}{9}\). So without loss of generality assume \(a(\{1,2\}) > 0\) so that \(b_1 + b_2 \geq 1\). Since \((a_1 + b_1) + (a_2+b_2) \leq \frac{14}{9}\), we have \(a_1 + a_2 \leq \frac{5}{9}\). Note since \(a(\{1,2\}) > 0\), we have

\[\sum_{R \in \{1\}^{\uparrow} \cup \{2\}^{\uparrow}} a(R) \leq a_1 + a_2 - a(\{1,2\}) < \frac{5}{9}.\]

Recall \(\sum_{R \subseteq [7], |R| = 2} a(R) \geq \frac{5}{9}\), and thus we may without loss of generality assume that \(a(\{3,4\}) > 0\) as well. Thus we get that \(b_3 + b_4 \geq 1\).
Claim 1: There can’t exist \(i,j \in \{5,6,7\}, i \neq j\) such that \(i \in R_1\), \(j \in R_2\), \(a(R_1),a(R_2) > 0\), and \(|R_1| = |R_2| = 2\). Without loss of generality, assume \(i = 5, j = 6\).
Case 1: \(R_1 = R_2 = \{5,6\}\). \(a(\{5,6\}) > 0\) would imply \(b_5 + b_6 \geq 1\). Thus we have \(\sum_{i \in [6]} b_i \geq 3 > 2.93\). This contradicts Corollary 1.
Case 2: \(R_1 = \{1,5\}, R_2 = \{1,6\}\). Let \(P \subseteq \mathcal{P}([7])\) be defined as

\[P = \{R \subseteq [7] : 2,5,6 \in R, \;3 \in R \;\vee \;4 \in R \}.\]

From \(a(\{1,2\}) > 0, a(\{1,5\}) > 0, a(\{1,6\}) > 0\), we have that if \(1 \not \in R\) and \(b(R) > 0\), we must have \(2,5,6 \in R\) by constraint (5). Also since \(a(\{3,4\}) > 0\), we have \(b(R) > 0\) implies \(3 \in R \;\vee \;4 \in R\) by constraint (5) as well. Thus if \(1 \not \in R\) and \(b(R) > 0\), we have \(R \in P\). Also note that by Corollary 1 we have \(b_1 \leq 0.6311\). This implies that

\[\sum_{R \subseteq [7], \;|R| \geq 4} b(R) \geq \sum_{R \in P} b(R) \geq \sum_{R \subseteq [7], \;1 \not\in R} b(R) \geq 1 - 0.6311 = 0.3689.\]

Recall that \(b(R) > 0\) implies \(|R| \geq 3\), thus we get

\[\begin{align} \sum_{i \in [7]} b_i = \sum_{R \subseteq [7]} |R| \cdot b(R) &= \left( \sum_{R \subseteq [7], |R| = 3} |R| \cdot b(R) \right) + \left( \sum_{R \subseteq [7], |R| \geq 4} |R| \cdot b(R) \right) \\ &\geq 3 \left( \sum_{R \subseteq [7], |R| = 3} b(R) \right) + 4\left( \sum_{R \subseteq [7], |R| \geq 4} b(R) \right) \\ &= 3+\left( \sum_{R \subseteq [7], |R| \geq 4} b(R) \right) \\ &\geq 3 + 0.3689 > 3.363 \end{align}\]

which contradicts Corollary 1.
Case 3: \(R_1 = \{1,5\}, R_2 = \{2,6\}\). This implies that if \(b(R) > 0\), and \(1 \not \in R\) we must have \(5 \in R\) by constraint (5). Likewise, \(b(R) > 0, \;2 \not \in R\) implies \(6 \in R\). This implies that \(b_5 + b_6 \geq 1 - b'(\{1,2\}^{\uparrow})\). Furthermore, recall that \(a(\{1,2\}) > 0\) so that \(b(R) > 0, \;2 \not\in R\) implies \(1 \in R\), and thus \(b'(\{1\}^{\uparrow} \setminus \{2\}^{\uparrow}) + b'(\{2\}^{\uparrow}) = 1\). Thus

\[b_1+b_2+b_5+b_6 \geq b'(\{1\}^{\uparrow}) + b'(\{2\}^{\uparrow}) + 1 - b'(\{1,2\}^{\uparrow})\]

\[= b'(\{1\}^{\uparrow} \setminus \{1,2\}^{\uparrow}) + b'(\{2\}^{\uparrow}) + 1 = b'(\{1\}^{\uparrow} \setminus \{2\}^{\uparrow}) + b'(\{2\}^{\uparrow}) + 1 = 2\]

where the second to last equality comes from \(\{1\}^{\uparrow} \setminus \{2\}^{\uparrow} = \{1\}^{\uparrow} \setminus \{1,2\}^{\uparrow}\). Recall we also had \(b_3 + b_4 \geq 1\), and thus \(\sum_{i \in [6]} b_i \geq 3\), contradicting Corollary 1.
Case 4: \(R_1 = \{1,5\}, R_2 = \{3,6\}\). Note \(a(\{1,5\}) > 0\) implies \(b_1 + b_5 \geq 1\). Recall also that \(b_1 + b_2 \geq 1\). We apply Lemma 7 with \(I = \{1\}, O_1 = \{2\}, O_2 = \{5\}\) with \(k = \frac{7}{9} < \frac{2}{1+1}\). Thus we get \(a_1b_1 + a_2b_2 + a_5b_5 \leq \frac{409}{972}\). One can also show \(a_3b_3 + a_4b_4 + a_6b_6 \leq \frac{409}{972}\), because it satisfies similar constraints from \(b(\{3,6\}) > 0\) so that \(b_3 + b_6 \geq 1\) and recall \(b_3 + b_4 \geq 1\). Thus \(\sum_{i \in [6]} a_ib_i \leq \frac{818}{972}\). This implies we must have \(a_7b_7 \geq 1-\frac{818}{972} = \frac{154}{972} > (\frac{1}{2} \cdot \frac{7}{9})^2 \geq a_7b_7\), a contradiction.
Other cases are analogous to the four cases described above, so the claim is proven. We may without loss of generality assume that if \(a(R) > 0\) and \(|R| = 2\), then \(R \subseteq [5]\), so that if \(a(R) > 0\) and \(6 \in R \;\vee \; 7 \in R\) then \(|R| \geq 3\).
Claim 2: there can’t exist \(i \in \{5,6,7\}\) such that \(i \in R\), \(|R| = 2\), and \(a(R) > 0\). Assume otherwise, and without loss of generality let \(i = 5\), and \(R = \{1,5\}\). Thus \(b_1 + b_5 \geq 1\) since \(a(\{1,5\}) > 0\). By Corollary 1, we have \(b_1 \leq 0.64\) so that \(b_5 \geq 0.36\). Recall \(b_1 + b_2 \geq 1, \;b_3 + b_4 \geq 1\), so that we get \(\sum_{i \in [5]} b_i \geq 2.36\). Thus \(\sum_{i \in [5]} a_i \leq 5 \cdot \frac{7}{9} - 2.36\).
By Claim 1, we also have \(a(R) > 0\) and \(|R| = 2\) implies \(R \subseteq [5]\), so that

\[\sum_{R \subseteq [7], \;|R| = 2} a(R) = \sum_{R \subseteq [5], \;|R| = 2} a(R).\]

We note that if \(R \subseteq [7], \;|R| \geq 3\), then for some \(i \in [5]\) we have \(i \in R\). Recall \(\sum_{R \subseteq [7], \;|R| = 2} a(R) \geq \frac{5}{9}\). This means

\[\begin{align} \sum_{i \in [5]} a_i &\geq 2 \left( \sum_{R \subseteq [5], \;|R| = 2} a(R) \right) + \left( \sum_{R \subseteq [7], \;|R| \geq 3} a(R) \right) \\ &= \left( \sum_{R \subseteq [5], \;|R| = 2} a(R) \right) + \left( \sum_{R \subseteq [7], \;|R| = 2} a(R) + \sum_{R \subseteq [7], \;|R| \geq 3} a(R) \right) \\ &= \left( \sum_{R \subseteq [5], \;|R| = 2} a(R) \right) + 1 \geq \frac{5}{9} + 1 =\frac{14}{9}. \end{align}\]

But then we have \(5 \cdot \frac{7}{9} - 2.36 \geq \sum_{i \in [5]} a_i \geq \frac{14}{9}\), a contradiction. Thus Claim 2 is proven. In particular, Claim 2 says that if \(R \subseteq [7], \;a(R) > 0\) and \(|R| = 2\), then \(R \subseteq [4]\). So \(\sum_{R \subseteq [7], \;|R| = 2} a(R) = \sum_{R \subseteq [4], \;|R| = 2} a(R) \geq \frac{5}{9}\). But note that since \(b_1 + b_2 \geq 1, \;b_3 + b_4 \geq 1\), we have that \(\sum_{i \in [4]} a_i \leq 4 \cdot \frac{7}{9} - 2 = \frac{10}{9}\). Note

\[\frac{10}{9} \geq \sum_{i\in [4]} a_i \geq \sum_{R \subseteq [4], \;|R| = 2} 2 \cdot a(R) \geq \frac{10}{9}.\]

In particular, this implies \(\sum_{i\in [4]} a_i = \frac{10}{9}\). Along with the equations \(b_1 + b_2 \geq 1, \;b_3 + b_4 \geq 1\), we get \(\sum_{i \in [4]} a_i + b_i \geq \frac{10}{9} + 2 = \frac{28}{9}\), so that for some \(i \in [4]\) we know \(a_i + b_i \geq \frac{1}{4} \cdot \frac{28}{9} = \frac{7}{9}\), as required. ◻

Proof. To see that \(g^*(8) \leq \frac{13}{18}\), consider

Now we show \(g^*(8) \geq \frac{13}{18}\). Consider any solution \(a,b : \mathcal{P}([8]) \rightarrow [0,1]\) satisfying constraints (1), (2), (3), and (5). We may assume \(a_i + b_i \leq \frac{13}{18}\) for all \(i \in [8]\). By Lemma 5 we have for \(|R| \leq 1\) that \(a(R) = b(R) = 0\), as \(a_i+b_i \leq \frac{13}{18} < \frac{1}{1}\) for all \(i \in [8]\).
We first show there is no \(R_1,R_2 \subseteq [8]\) such that \(|R_1| = |R_2| = 2\) and \(a(R_1) > 0, b(R_2) > 0\). Assume for the sake of contradiction that this is not the case. If without loss of generality \(R_1 = R_2 = \{1,2\}\), then we have from \(a(\{1,2\}) > 0\) that \(b_1 + b_2 \geq 1\), and likewise \(b(\{1,2\}) > 0\) implies \(a_1 + b_1 \geq 1\). This means \((a_1+b_1) + (a_2+b_2) \geq 2\) so that for some \(i \in \{1,2\}\) we have \(a_i+b_i \geq 1\), contradicting \(a_i + b_i \leq \frac{13}{18}\) for all \(i \in [8]\). Now without loss of generality assume \(R_1 = \{1,2\}, R_2 = \{1,3\}\). From \(a(\{1,2\}) > 0\) we have that \(b_1 + b_2 \geq 1\), and from \(b(\{1,3\})\) we have \(a_1 + a_3 \geq 1\). So we have \(a_1 + b_1 + b_2 + a_3 \geq 2\). Since \(a_1 + b_1 \leq \frac{13}{18}\), we have that \(b_2 + a_3 \geq 2 - \frac{13}{18} = \frac{23}{18} > 1.02\), which contradicts Corollary 1.
Thus we may without loss of generality assume that if \(b(R) > 0\), then \(|R| \geq 3\). Note

\[\sum_{R \subseteq [8]} |R|(a(R) + b(R)) = \sum_{i \in [8]} a_i + b_i \leq 8 \cdot \frac{13}{18}\]

so that

\[\begin{align} 8 \cdot \frac{13}{18} &\geq \sum_{R \subseteq [8]} (a(R) + b(R))|R| = \sum_{R \subseteq [8]} |R| \cdot a(R) \;+ \sum_{R \subseteq [8], |R| \geq 3} |R| \cdot b(R) \\ &\geq \sum_{R \subseteq [8]} |R| \cdot a(R) + \sum_{R \subseteq [8], |R| \geq 3} 3 \cdot b(R) = \sum_{R \subseteq [8]} |R| \cdot a(R) + 3 \end{align}\]

and thus \(\sum_{R \subseteq [8]} |R| \cdot a(R) \leq 8 \cdot \frac{13}{18} - 3 = \frac{50}{18} = 2 + \frac{7}{9}\). In particular, this implies that

\[\begin{align} 2 + \frac{7}{9} \geq \sum_{R \subseteq [8]} |R| \cdot a(R) &= \left( \sum_{R \subseteq [8], |R| = 2} |R| \cdot a(R) \right) + \left( \sum_{R \subseteq [8], |R| \geq 3} |R| \cdot a(R) \right) \\ &\geq 2\left( \sum_{R \subseteq [8], |R| = 2} a(R) \right) + 3\left( \sum_{R \subseteq [8], |R| \geq 3} a(R) \right) \\ &= 2 + \left( \sum_{R \subseteq [8], |R| \geq 3} a(R) \right) \end{align}\]

so that \(\sum_{R \subseteq [8], |R| \geq 3} a(R) \leq \frac{7}{9}\) and thus \(\sum_{R \subseteq [8], |R| = 2} a(R) \cdot|R| \geq \frac{2}{9}\). Without loss of generality, let \(a(\{1,2\}) > 0\), so that \(b_1 + b_2 \geq 1\).
We now show we cannot have \(i \in [8] \setminus \{1,2\}\) such that \(i \in R, \;|R| = 2\) and \(a(R) > 0\). Assume otherwise for the sake of contradiction, and without loss of generality let \(i = 3\). The first case is if without loss of generality \(R = \{3,4\}\). From \(a(\{3,4\}) > 0\) we have \(b_3 + b_4 \geq 1\). Thus we get \(b_1 + b_2 + b_3 + b_4 \geq 2 > 1,861\) which contradicts Corollary 1. The second case is if without loss of generality \(R = \{1,3\}\), so that \(a(\{1,3\}) > 0\) and thus \(b_1 + b_3 \geq 1\). Consider the maximum value \(a_1b_1 + a_2b_2 + a_3b_3\) can take on given the constraints \(b_1 + b_2 \geq 1\), \(b_1 + b_3 \geq 1\), and \(a_i+b_i \leq \frac{13}{18}\) for \(i \in [3]\). We apply Lemma 7 with \(I = \{1\}, O_1 = \{2\}, O_2 = \{3\}\) with \(k = \frac{13}{18} < \frac{2}{1+1}\) to get that \(a_1b_1 + a_2b_2 + a_3b_3 \leq \frac{1321}{3888}\). This implies that \(5 (\frac{1}{2} \cdot \frac{13}{18})^2 \geq \sum_{i \in [8] \setminus [3]} a_ib_i \geq 1 - \frac{1321}{3888}\), a contradiction.
Thus \(a(R) > 0\) and \(|R| = 2\) implies \(R = \{1,2\}\). Since

\[\sum_{R \subseteq [8], |R| = 2} |R| \cdot a(R) = a(\{1,2\}) \geq \frac{2}{9}\]

we have \(a_1, a_2 \geq \frac{2}{9}\) so that \(a_1 + a_2 \geq \frac{4}{9}\). Recall also that \(b_1 + b_2 \geq 1\), so that together we have \((a_1+b_1) + (a_2+b_2) \geq \frac{13}{9}\). This implies for some \(i \in [2]\) we have \(a_i+b_i \geq \frac{13}{18}\), as required. ◻

Proof. To see that \(g^*(t^2-1) \leq \frac{1}{t} - \frac{1}{t^2} + \frac{1}{t-1}\), see the construction described above. More formally, define a coloring of the unit square \(\chi : [0,1]^2 \rightarrow [t^2-1]\) where for \(i \in \{0\} \cup [t-2]\) and \(j \in \{0\} \cup [t-1]\), for all

\[(x,y) \in \left( i \cdot (\frac{1}{t-1} - \frac{1}{t^2}), \;(i+1) \cdot(\frac{1}{t-1} - \frac{1}{t^2}) \right) \times \left( j \cdot \frac{1}{t}, \;(j+1) \cdot \frac{1}{t} \right)\]

set \(\chi(x,y) = (t-j-1) \cdot (t-1) + i + 1\). For \(j \in \{0\} \cup [t-2]\), for all

\[(x,y) \in \left( 1- (\frac{1}{t}-\frac{1}{t^2}), \;1 \right) \times \left( j \cdot \frac{1}{t}, \;(j+1) \cdot \frac{1}{t-1} \right)\]

set \(\chi(x,y) = t^2 - j - 1\). For all the other points we haven’t colored yet, we can choose any color we like. It doesn’t matter because their projections onto the \(x\) and \(y\) axes have Lebesgue measure \(0\).
Now we show \(g^*(t^2-1) \geq \frac{1}{t} - \frac{1}{t^2} + \frac{1}{t-1}\). We may assume \(a_i+b_i \leq \frac{1}{t}-\frac{1}{t^2} + \frac{1}{t-1}\) for all \(i \in [t^2-1]\). Let \(k = \frac{1}{t} - \frac{1}{t^2} + \frac{1}{t-1}\).
Claim 1: if \(R \subseteq [t^2-1]\) and \(|R| \leq t-2\), then \(a(R) = b(R) = 0\). Assume for the sake of contradiction otherwise. Note we can’t have that \(a(\{\}) > 0\), because by constraint (5) this would imply that \(b(R) = 0\) for all \(R \subseteq [t^2-1]\), contradicting constraint (2). Likewise, we can’t have \(b(\{\}) > 0\). So we may assume \(|R| \geq 1\). We have \(a(R) > 0\) implies that \(\sum_{i \in R} b_i \geq 1\). We apply Lemma 3 with \(s = |R|\), which we can do because

\[k = \frac{1}{t} - \frac{1}{t^2} + \frac{1}{t-1} \leq \frac{2}{t-2} < \frac{2}{|R|}.\]

The inequality \(\frac{1}{t} - \frac{1}{t^2} + \frac{1}{t-1} \leq \frac{2}{t-2}\) holds when \(t \geq 3\), which can be checked by algebraic manipulations or by mathematical software (we used Mathematica).
Thus Lemma 3 says \(\sum_{i \in R} a_ib_i \leq k - \frac{1}{|R|}\), and so we must have

\[1-k+\frac{1}{|R|} \leq \sum_{i \in [t^2-1] \setminus R} a_ib_i \leq (t^2-1-|R|)\frac{k^2}{4},\]

where the last inequality comes from AM-GM. The inequality \(1-k+\frac{1}{|R|} \leq (t^2-1-|R|)\frac{k^2}{4}\) is a contradiction when \(t \geq 3\) and \(1 \leq |R| \leq t-2\) which can be checked by mathematical software. Thus Claim 1 is proven.
Claim 2: There do not exist \(R_1,R_2 \subseteq [t^2-1]\) such that \(|R_1| = |R_2| = t-1\) and \(a(R_1) > 0, b(R_2) > 0\). Assume otherwise. By constraint (5), we have \(R_1 \cap R_2 \neq \{\}\). First assume \(R_1 \setminus R_2 \neq \{\}\). From \(a(R_1) > 0\), we have \(\sum_{i \in R_1} b_i \geq 1\) and from \(b(R_2) > 0\), we have \(\sum_{i \in R_2} a_i \geq 1\). We wish to apply Lemma 6 with \(I = R_1 \cap R_2\), \(O_1 = R_1 \setminus R_2\), and \(O_2 = R_2 \setminus R_1\). The inequality \(k < \frac{2}{t-1} = \frac{2}{|I|+|O_1|}\) holds for \(t \geq 3\) which can be checked by mathematical software. Thus by Lemma 6 for \(e = \frac{2-|I|k}{2|O_1|}\) we get

\[\sum_{i \in R_1 \cup R_2} a_ib_i \leq |I|\frac{k^2}{4} + 2|O_1| \cdot e(k-e)\]

so that

\[\begin{align} 1-(|I|\frac{k^2}{4} + 2|O_1| \cdot e(k-e)) &\leq \sum_{i \in [t^2-1] \setminus (R_1 \cup R_2)} a_ib_i \\ &\leq (t^2 - 1 - |I| -|O_1|-|O_2|)\frac{k^2}{4}. \end{align}\]

The inequality

\[1-(|I|\frac{k^2}{4} + 2|O_1| \cdot e(k-e)) \leq (t^2 - 1 - |I| -2|O_1|)\frac{k^2}{4}\]

reduces to

\[1-(|I|\frac{k^2}{4} + 2(t-1-|I|) \cdot e(k-e)) \leq (t^2 - 1 - |I| -2(t-1-|I|))\frac{k^2}{4}\]

where \(e = \frac{2-|I|k}{2(t-1-|I|)}\) because \(|I| + |O_1| = t-1\). This last inequality is a contradiction for \(t \geq 3\) and \(1 \leq |I| \leq t-2\) which can be checked by mathematical software.
Now we consider the case when \(O_1 = O_2 = \{\}\), and thus \(R_1 = R_2\). From \(a(R_1) > 0\) we get \(\sum_{i \in R_1} b_i \geq 1\) and from \(b(R_1) > 0\) we get \(\sum_{i \in R_1} a_i \geq 1\). We sum these two equations to get \(\sum_{i \in R_1} a_i+b_i \geq 2\), so that for some \(i \in R_1\) we have \(a_i+b_i \geq \frac{2}{|R_1|} = \frac{2}{t-1} > k\), a contradiction. Thus Claim 2 is proven.
Claim 3: There do not exist \(R_1,R_2 \subseteq [t^2-1]\) such that \(|R_1| = |R_2| = t-1\), \(R_1 \neq R_2\), and \(a(R_1), a(R_2) > 0\) or \(b(R_1), b(R_2) > 0\). Assume otherwise, we show it for \(a(R_1), a(R_2) > 0\). From \(a(R_1) > 0\), we have \(\sum_{i \in R_1} b_i \geq 1\) and from \(a(R_2) > 0\) we have \(\sum_{i \in R_2} b_i \geq 1\). We wish to apply Lemma 7 with \(I = R_1 \cap R_2\), \(O_1 = R_1 \setminus R_2\), and \(O_2 = R_2 \setminus R_1\). We can do this because \(k < \frac{2}{|I|+|O_1|} = \frac{2}{t-1}\). Thus Lemma 7 gives us for \(e_1 = \frac{2+|I|k}{2|I|+|O_1|} - \frac{k}{2}\) and \(e_2 = \frac{1+|I|\frac{k}{2}}{2|I| + |O_1|}\) that

\[\sum_{i \in R_1 \cup R_2} a_ib_i \leq |I| \cdot e_1(k-e_1) + 2|O_1| \cdot e_2(k - e_2)\]

and thus

\[\begin{align} 1 - (|I| \cdot e_1(k-e_1) + 2|O_1| \cdot e_2(k - e_2)) &\leq \sum_{i \in [t^2-1] \setminus R_1 \cup R_2} a_ib_i \\ &\leq (t^2 - 1 - |I| -2|O_1|)\frac{k^2}{4}. \end{align}\]

The inequality

\[1 - (|I| \cdot e_1(k-e_1) + 2|O_1| \cdot e_2(k - e_2)) \leq (t^2 - 1 - |I| -2|O_1|)\frac{k^2}{4}\]

reduces to

\[1 - (|I| \cdot e_1(k-e_1) + 2(t-1-|I|) \cdot e_2(k - e_2)) \leq (t^2 - 1 - |I| -2(t-1-|I|))\frac{k^2}{4}\]

where \(e_1 = \frac{2+|I|k}{t-1+|I|} - \frac{k}{2}\) and \(e_2 = \frac{1+|I|\frac{k}{2}}{t-1+|I|}\) because \(|I| + |O_1| = t-1\). This last inequality is a contradiction for \(t \geq 3\) and \(0 \leq |I| \leq t-2\) which can be checked by mathematical software. Thus Claim 3 is proven.
By Claims 1 and 2, we must have either \(a(R) > 0\) implies \(|R| \geq t\) for all \(R \subseteq [t^2-1]\), or \(b(R) > 0\) implies \(|R| \geq t\) for all \(R \subseteq [t^2-1]\), since we know there can’t exist \(R_1,R_2 \subseteq [t^2-1]\) such that \(|R_1|,|R_2| \leq t-1\) and \(a(R_1) > 0\) and \(b(R_2) > 0\). Without loss of generality assume that if \(b(R) > 0\), then \(|R| \geq t\) for all \(R \subseteq [t^2-1]\). Since \(a_i + b_i \leq k\) for all \(i \in [t^2-1]\), we have that

\[\sum_{R \subseteq [t^2-1]} |R|(a(R) + b(R)) = \sum_{i \in [t^2-1]} a_i + b_i \leq (t^2-1)k\]

so that

\[\begin{align} (t^2-1)k &\geq \sum_{R \subseteq [t^2-1]} (a(R) + b(R))|R| = \sum_{R \subseteq [t^2-1]} |R| \cdot a(R) \;+ \sum_{R \subseteq [t^2-1], |R| \geq t} |R| \cdot b(R) \\ &\geq \sum_{R \subseteq [t^2-1]} |R| \cdot a(R) + \sum_{R \subseteq [t^2-1], |R| \geq t} |R| \cdot b(R) = \sum_{R \subseteq [t^2-1]} |R| \cdot a(R) + t \end{align}\]

and thus \(\sum_{R \subseteq [t^2-1]} |R| \cdot a(R) \leq (t^2-1)k - t\). In particular, this implies that

\[\begin{align} (t^2-1)k - t &\geq \sum_{R \subseteq [t^2-1]} |R| \cdot a(R) \\ &= \left( \sum_{R \subseteq [t^2-1], |R| = t-1} |R| \cdot a(R) \right) + \left( \sum_{R \subseteq [t^2-1], |R| \geq t-1} |R| \cdot a(R) \right) \\ &\geq (t-1)\left( \sum_{R \subseteq [t^2-1], |R| = t-1} a(R) \right) + t\left( \sum_{R \subseteq [t^2-1], |R| \geq t} a(R) \right) \\ &= t-1+ \left( \sum_{R \subseteq [t^2-1], |R| \geq t} a(R) \right) \end{align}\]

so that \(\sum_{R \subseteq [t^2-1], |R| \geq t} a(R) \leq (t^2-1)k-2t+1\) and thus

\[\begin{align} \sum_{R \subseteq [t^2-1], |R| = t-1} a(R) \cdot |R| &\geq 1-((t^2-1)k-2t+1) \\ &= 1-((t^2-1)(\frac{1}{t} - \frac{1}{t^2} + \frac{1}{t-1})-2t+1) \\ &= 1-(\frac{t^2-1}{t} - \frac{t^2-1}{t^2} + t+1-2t+1) \\ &= 1 - (\frac{t^3-t-t^2+1 - t^3 + 2t^2}{t^2}) \\ &= 1 - (\frac{-t+1 + t^2}{t^2}) = \frac{1}{t} - \frac{1}{t^2} > 0. \end{align}\]

Thus there exists \(R \subseteq [t^2-1]\) where \(|R| = t-1\) and \(a(R) > 0\). Without loss of generality, let \(R = [t-1]\). By Claim 3 \(R\) is a unique such subset. Thus

\[\sum_{R \subseteq [t^2-1], |R| = t-1} a(R) = a([t-1]) \geq \frac{1}{t} - \frac{1}{t^2}.\]

From \(a([t-1]) \geq \frac{1}{t} - \frac{1}{t^2}\) we get \(a_i \geq \frac{1}{t} - \frac{1}{t^2}\) for all \(i \in [t-1]\), and thus \(\sum_{i \in [t-1]} a_i \geq (t-1)(\frac{1}{t} - \frac{1}{t^2})\). From \(a([t-1]) > 0\) we get \(\sum_{i \in [t-1]} b_i \geq 1\). Summing these two inequalities together we get \(\sum_{i \in [t-1]} a_i+b_i \geq (t-1)(\frac{1}{t} - \frac{1}{t^2}) + 1\), and thus for some \(j \in [t-1]\) we have

\[a_j+b_j \geq \frac{1}{t} - \frac{1}{t^2} + \frac{1}{t-1}\]

as required. ◻

Proof. We define a coloring \(\chi : [0,1]^2 \rightarrow [r]\) which satisfies

\[a_i + b_i = \frac{2}{t} + \frac{1}{t+1} + \frac{r}{t(t+1)} - \frac{r}{t^2}\]

for all \(i \in [r]\); it will be the construction described above. Let \(p = t(t+1)-r\) and \(p+q = t\). Set \(x = \frac{p}{t^2}+\frac{q}{t(t+1)}\). Define \([0] = \{\}\). For \(i \in \{0\} \cup [p-1]\) and \(j \in \{0\} \cup [t-1]\), for all

\[(x,y) \in \biggl( i \cdot x, \;(i+1) \cdot x \biggl) \times \left( j \cdot \frac{1}{t}, \;(j+1) \cdot \frac{1}{t} \right)\]

set \(\chi(x,y) = (t-j-1) \cdot p + i + 1\). If \(p = 0\), then we skip this step. For \(i \in \{0\} \cup [q-1]\) and \(j \in \{0\} \cup [t]\), for all

\[(x,y) \in \biggl(i \cdot \frac{1-px}{q} + px, \;(i+1) \cdot \frac{1-px}{q} + px \biggl) \times \biggl(j \cdot \frac{1}{t+1}, \;(j+1) \cdot \frac{1}{t+1} \biggl)\]

set \(\chi(x,y) = (t-j) \cdot q + i + 1 + pt\). If \(q = 0\) we skip this step. For all the points we haven’t colored yet, we can choose any color we want. Their projections on the \(x\) and \(y\) axes have Lebesgue measure 0. One can check \(a_i + b_i = \frac{2}{t} + \frac{1}{t+1} + \frac{r}{t(t+1)} - \frac{r}{t^2}\) for all \(i \in [r]\). ◻

Proof. We define a coloring \(\chi : [0,1]^2 \rightarrow [r]\) which satisfies

\[a_i + b_i = \frac{2}{t+1}+\frac{1}{t}+\frac{r}{(t+1)^2}-\frac{r}{t(t+1)}\]

for all \(i \in [r]\); it will be the construction described above. Let \(p = r-t(t+1)\) and \(p+q = t+1\). Set \(x = \frac{p}{(t+1)^2}+\frac{q}{t(t+1)}\). Define \([0] = \{\}\). For \(i \in \{0\} \cup [p-1]\) and \(j \in \{0\} \cup [t]\), for all

\[(x,y) \in \biggl( i \cdot x, \;(i+1) \cdot x \biggl) \times \left( j \cdot \frac{1}{t+1}, \;(j+1) \cdot \frac{1}{t+1} \right)\]

set \(\chi(x,y) = (t-j) \cdot p + i + 1\). If \(p = 0\), then we skip this step. For \(i \in \{0\} \cup [q-1]\) and \(j \in \{0\} \cup [t-1]\), for all

\[(x,y) \in \biggl(i \cdot \frac{1-px}{q} + px, \;(i+1) \cdot \frac{1-px}{q} + px \biggl) \times \biggl(j \cdot \frac{1}{t}, \;(j+1) \cdot \frac{1}{t} \biggl)\]

set \(\chi(x,y) = (t-j-1) \cdot q + i + 1 + p(t+1)\). If \(q = 0\) we skip this step. For all the points we haven’t colored yet, we can choose any color we want. Their projections on the \(x\) and \(y\) axes have Lebesgue measure 0. One can check \(a_i + b_i = \frac{2}{t+1}+\frac{1}{t}+\frac{r}{(t+1)^2}-\frac{r}{t(t+1)}\) for all \(i \in [r]\). ◻

Proof. Assume for the sake of contradiction otherwise. Since \(a_i+b_i > a_j+b_j \geq 0\) for all \(j \in [r] \setminus \{i\}\) where \(r \geq 2\), we have that there exists some \(R \subseteq [r]\) such that \(i \in R\) and \(a(R) > 0\) or \(b(R) > 0\). Without loss of generality, assume \(a(R) > 0\). We redefine the function \(a : \mathcal{P}([r]) \rightarrow [0,1]\) to get a better coloring. Let this function be \(\alpha : \mathcal{P}([r]) \rightarrow [0,1]\). For some \(0 < \epsilon < a(R)\), define \(\alpha(R) = \frac{a(R)-\epsilon}{1-\epsilon}\) (column deletion and rescaling) and \(\alpha(R') = \frac{a(R')}{1-\epsilon}\) (rescaling) for \(R' \in \mathcal{P}([r]) \setminus \{R\}\). We can make \(\epsilon\) small enough so that we still maintain \(\alpha_i+b_i > \alpha_j + b_j\) for all \(j \in [r] \setminus \{i\}\) under the coloring \(\alpha, b : \mathcal{P}([r]) \rightarrow [0,1]\). But if \(a_i < 1\), note that \(\alpha_i+b_i < a_i + b_i\) because \(\alpha_i = \frac{a_i-\epsilon}{1-\epsilon} < a_i\) , and thus \(\alpha, b\) is a strictly better coloring than \(a,b\). If \(a_i = 1\), then we may perform row deletions instead, because we must have \(0 < b_i < 1\), otherwise \(a_i+b_i = 2\) but \(g^*(r) < 2\) for \(r > 1\). Then the rest of the argument follows by an analogous one given above, except for row deletions.
 ◻