February 05, 2024
Chvátal conjectured that amongst the largest intersecting subfamiles of a finite subset-closed family of sets is a star. Kleitman later strengthened Chvátal’s conjecture, defining a partial ordering on the vector space freely generated by \(2^{[n]}\) and suggesting that the vector of every maximal intersecting subfamily of \(2^{[n]}\) is bigger than a convex combination of stars. We restate Kleitman’s conjecture using the cohomology of the discrete cube, studying it with techniques from convex optimization.
We say a family of sets \(\mathcal{F} \subseteq 2^{[n]}\) is intersecting if \(A \cap B \ne \emptyset\) for all \(A, B \in \mathcal{F}\) and a family of sets \(\mathcal{F} \subseteq 2^{[n]}\) is a star if \(a \in A\) for all \(A \in \mathcal{F}\) for some \(a \in [n]\).
In 1961, Erdős, Ko, and Rado published their seminal theorem [1], that for any family \(\mathcal{F} = \binom{[n]}{k}\) such that \(2k \le n\), amongst the largest intersecting subfamilies of \(\mathcal{F}\) is a star, known as the Erdős-Ko-Rado theorem. In 1972, Chvátal conjectured the following variant of the Erdős-Ko-Rado theorem.
Conjecture 1. [2] Let \(\mathcal{F} \subseteq 2^{[n]}\) be subset-closed. Then amongst the largest intersecting subfamilies of \(\mathcal{F}\) is a star.
Chvátal [2] first proved his own conjecture for all left-compressed, subset-closed families. This result was later generalized by Wang and Wang [3], then by Snevily [4], and most recently by Borg [5]. Sterboul [6] proved Chvátal’s conjecture for all subset-closed families of sets of size at most 3, which was recently reproved by Czabarka, Hurlbert, and Kamat [7] via the sunflower lemma, and again by Olarte, Santos, and Spreer [8] with a short combinatorial argument. On the computational side, Eifler, Gleixner, and Pulaj [9] verified the conjecture for all subset-closed families of \(2^{[7]}\) via integer programming.
Taking an alternative approach, fixing collections of intersecting families instead, Kleitman and Magnanti [10] proved the conjecture for intersecting families contained in the union of two stars. Kleitman later proposed a conjecture in 1979, providing a general line of attack for all intersecting families.
Conjecture 2. [11] We first define a partial ordering on the vector space freely generated by \(2^{[n]}\), and given \(A \subseteq [n]\), we denote by \(\tilde{A}\), the vector corresponding to \(A\). Given \(f, g \in \mathbb{R}^{2^{[n]}}\), we say that \(f\) is bigger than \(g\) if \(f = g + \lambda (\tilde{B} - \tilde{A})\) for some \(\lambda > 0\) and \(A \subset B \subseteq [n]\).
Kleitman’s conjecture can then be stated as follows. Let \(\mathcal{F}\) be a maximal intersecting subfamily of \(2^{[n]}\). Then \(\sum_{A \in \mathcal{F}} \tilde{A}\) is bigger than some convex combination of stars, i.e. some vector of the form \(\sum_{a \in [n]} c_a \sum_{a \in A \subseteq [n]} \tilde{A}\) for some \(c \in \Delta^{[n]}\).
Relatively little progress has been made on Kleitman’s conjecture, or even on Chvátal’s conjecture in the approach taken by Kleitman and Magnanti, with a recent paper by Frankl and Kupavskii [12] providing another proof of Kleitman and Magnanti’s result by generalizing a theorem of Berge. Friedgut, et al. [13] also recently suggested an approach for Chvátal’s conjecture in terms of correlation inequalities, with Kleitman’s conjecture and several of its strengthenings being brought up in this context.
We first give preliminary definitions and propositions for real-valued Boolean functions. Throughout, we identify subsets of \([n]\) with elements of \(\{-1, 1\}^n\) in the natural way.
We equip the space of real-valued Boolean functions \(f \colon 2^{[n]} \to \mathbb{R}\) with the inner product \[\langle f, g \rangle = \frac{1}{2^n} \sum_{A \subseteq [n]} f(A) g(A).\]
For each subset \(A \subseteq [n]\), define the Walsh function \(x^A \colon 2^{[n]} \to \mathbb{R}\) by \[x^A(B) = (-1)^{|A \setminus B|}, \quad \text{for all } B \subseteq [n],\] and in the case of singletons \(\{a\} \subseteq [n]\), we write \(x_a\) to denote \(x^{\{a\}}\).
The Walsh functions form an orthonormal basis with respect to the inner product above. Consequently, any real-valued Boolean function \(f \colon 2^{[n]} \to \mathbb{R}\) admits a unique expansion \[f = \sum_{A \subseteq [n]} \hat{f}(A) x^A,\] where the coefficients \(\hat{f}(A) = \langle f, x^A \rangle\) are called the Fourier-Walsh coefficients of \(f\), and the map \(\hat{f} \colon 2^{[n]} \to \mathbb{R}\) is called the Fourier-Walsh transform of \(f\).
The partial derivative with respect to coordinate \(k \in [n]\) is defined by \[\frac{\partial}{\partial x_k} f \colon 2^{[n] \setminus \{k\}} \to \mathbb{R}, \quad \left( \frac{\partial}{\partial x_k} f \right)(A) = \frac{f(A \cup \{k\}) - f(A)}{2}.\]
The restriction to \(x_k = a\) for \(k \in [n]\) is defined by \[f \big|_{x_k = a} \colon 2^{[n] \setminus \{k\}} \to \mathbb{R}, \quad \left( f \big|_{x_k = a} \right)(A) = \frac{(1 - a)f(A) + (1 + a)f(A \cup \{k\})}{2}.\]
We define the convolution of real-valued Boolean functions by \[(f * g)(A) = \frac{1}{2^n} \sum_{B \odot C = A} f(B) g(C), \text{ for all } A \subseteq [n].\]
Finally, for \(f \colon 2^{[n]} \to \mathbb{R}\), we say \(f\) is monotone if \(A \subseteq B\) implies \(f(A) \le f(B)\).
Proposition 1. The partial derivative satisfies \[\frac{\partial}{\partial x_k} f = \sum_{k \in A \subseteq [n]} \hat{f}(A) x^{A \setminus \{k\}}.\]
Proposition 2. The restriction satisfies \[f \big|_{\{ x_k = a_k \}_{k \in B}} = \sum_{A \subseteq [n]} \hat{f}(A) \left( \prod_{k \in A \cap B} a_k \right) x^{A \setminus B}.\]
Proposition 3. The convolution satisfies \[f * g = \sum_{A \subseteq [n]} \hat{f}(A) \hat{g}(A) x^A.\]
We develop cochain machinery specializing the cubical cohomology framework of [14], [15], adapting it to a Fourier-Walsh basis for real-valued Boolean functions.
We define \(3^{[n]}\) to be the discrete cubical complex of dimension \(n\), consisting of the set of all products \(\prod_{i \in [n]} I_i\), where each \(I_i\) is either the closed interval \([-1, 1]\) or one of its boundary points. We will identify elements \(\sigma \in 3^{[n]}\) with tuples \((A, B) \in 2^{[n]}\) such that \(A \cap B = \emptyset\), where \(A\) is the set of non-degenerate axes of \(\sigma\) and \(B\) corresponds to the coordinates of the degenerate axes of \(\sigma\) in the natural way.
Let \(\binom{[n]}{k} \times 2^{[n] - k}\) for \(k \in [n]\) denote the set of all \(k\)-faces of \(3^{[n]}\), that is, all such products in which exactly \(k\) coordinates are non-degenerate intervals, and for \(A \subseteq [n]\), we write \(\{A\} \times 2^{[n] \setminus A}\) for the set of all \(\lvert A \rvert\)-faces of \(3^{[n]}\) that are non-degenerate precisely along the axes indexed by \(A\).
We define the face maps \(\delta_a^{\epsilon}\), which map \(k\)-cubes of \(3^{[n]}\) to their \((k - 1)\)-faces by setting the \(a\)th coordinate to \(\epsilon \in \{-1, 1\}\), where \(a\) must be non-degenerate.
Additionally, we define the cubical product \(\diamond\) on \(3^{[n]}\), such that for any \(f, g \in 3^{[n]}\) intersecting at a single point, \(f \diamond g\) is the unique face such that each interval is the common degenerate interval if \(f\) and \(g\) agree there, and otherwise is the unique non-degenerate interval from either \(f\) or \(g\).
We define the chain complex \(C_{\bullet}(3^{[n]})\) to be the graded vector space freely generated by the elements of \(3^{[n]}\). For each \(k \in [n]\), the space of \(k\)-chains, denoted \(C_k(3^{[n]})\), is the subspace generated by \(\binom{[n]}{k} \times 2^{[n] - k}\).
We define the boundary operator \(\partial_k \colon C_k(3^{[n]}) \to C_{k-1}(3^{[n]})\) such that \[\partial_k(\tilde{\sigma}) = \sum_{a \in A} (-1)^{\varepsilon_A(a) + k + 1} \left( \widetilde{\delta_a^{1}(\sigma)} - \widetilde{\delta_a^{-1}(\sigma)} \right),\] where \(A\) is the set of non-degenerate axes of \(\sigma\) and \(\varepsilon_A(a) = \lvert \{ b \in A \mid b < a \} \rvert\).
The cochain complex \(C^{\bullet}(3^{[n]})\) is defined as the graded dual of the chain complex: \[C^k(3^{[n]}) = \mathrm{Hom}(C_k(3^{[n]}), \mathbb{R}),\] the space of real-valued linear functionals on \(k\)-chains.
We define the natural pairing between cochains and chains by \[\langle \phi, \tilde{\sigma} \rangle = \frac{1}{2^{n - k}} \phi(\tilde{\sigma}) \quad \text{for } \phi \in C^k(3^{[n]}),\;\sigma \in \binom{[n]}{k} \times 2^{[n] - k}.\]
The exterior derivative \(d \colon C^k(3^{[n]}) \to C^{k+1}(3^{[n]})\) is defined as the adjoint of the boundary operator: \[(df)(\sigma) = \frac{1}{2} f(\partial \sigma).\]
We equip \(C^k(3^{[n]})\) with an inner product given by \[\langle \phi, \psi \rangle = \frac{1}{2^{n - k}} \sum_{\sigma \in \binom{[n]}{k} \times 2^{[n] - k}} \phi(\tilde{\sigma}) \psi(\tilde{\sigma}),\] for all \(\phi, \psi \in C^k(3^{[n]})\).
The codifferential \(\delta \colon C^{k+1}(3^{[n]}) \to C^k(3^{[n]})\) is defined as the adjoint of \(d\) with respect to this inner product: \[\langle d\phi, \psi \rangle = \langle \phi, \delta \psi \rangle \quad \text{for all } \phi \in C^k(3^{[n]}),\;\psi \in C^{k+1}(3^{[n]}).\]
We now define the exterior product on chains and on cochains by \[\begin{align} \tilde{\sigma} \wedge \tilde{\tau} & = (-1)^{\epsilon_\tau(\sigma)} \frac{1}{2^{a+b}} \, \widetilde{\sigma \diamond \tau} \quad \text{for } \sigma \in \binom{[n]}{a} \times 2^{[n]\setminus a}, \tau \in \binom{[n]}{b} \times 2^{[n]\setminus b}, \\ (\phi \wedge \psi)(\tilde{\sigma}) & = \frac{1}{2^{a+b}} \sum_{\alpha \diamond \beta = \sigma} (-1)^{\epsilon_\beta(\alpha)} \phi(\tilde{\alpha}) \psi(\tilde{\beta}) \quad \text{for } \phi \in C^a(3^{[n]}), \psi \in C^b(3^{[n]}), \end{align}\] where \(\epsilon_\tau(\sigma) = \lvert \{ (a,b) \in A \times B \colon b < a \} \rvert\), where \(A\) and \(B\) are the non-degenerate axes of \(\sigma\) and \(\tau\), respectively.
For each subset \(A \subseteq [n]\), we define the chain \(\frac{\partial}{\partial x^A} \in C_{\lvert A \rvert}(3^{[n]})\) and cochain \(dx^A \in C^{\lvert A \rvert}(3^{[n]})\) by \[\begin{align} \frac{\partial}{\partial x^A} & = \sum_{\sigma \in \{A\} \times 2^{[n] \setminus A}} \tilde{\sigma}, \\ dx^A(\tilde{\sigma}) & = \begin{cases} 1, & \text{if } \sigma \in \{A\} \times 2^{[n] \setminus A}, \\ 0, & \text{otherwise}, \end{cases} \end{align}\] and in the case of singletons \(\{a\} \subseteq [n]\), we write \(\frac{\partial}{\partial x_a}\) and \(dx_a\) to denote \(\frac{\partial}{\partial x^{\{a\}}}\) and \(dx^{\{a\}}\) respectively.
Every cochain \(\phi \in C^{\bullet}(3^{[n]})\) then admits a multilinear representation of the form \[\phi = \sum_{A \subseteq [n]} \sum_{B \subseteq [n] \setminus A} \widehat{\phi_A}(B) x^B dx^A,\] where \(\phi_A \colon 2^{[n] \setminus A} \to \mathbb{R}\) denotes the real-valued Boolean function corresponding to the \(dx^A\)-component of \(\phi\). Here again, we write \(\phi_a\) in place of \(\phi_{\{a\}}\) for singletons \(\{a\} \subseteq [n]\).
Finally, we define the interior \(\iota\) product by \[\begin{align} \iota_X \phi & = \langle \phi, X \rangle \quad \text{for } \phi \in C^1(3^{[n]}), X \in C_1(3^{[n]}), \\ \langle \iota_X \phi, Y \rangle & = \langle \phi, X \wedge Y \rangle \quad \text{for } \phi \in C^k(3^{[n]}), X \in C_1(3^{[n]}), Y \in C_{k - 1}(3^{[n]}), \end{align}\] the Laplace-de Rham operator \(\Delta\) by \[\Delta = d \delta + \delta d,\] and the convolution of cochains by \[\phi * \psi = \sum_{A \subseteq [n]} (\phi_A * \psi_A) dx^A.\]
Proposition 4. The exterior derivative \(d\phi\) satisfies \[\begin{align} d\phi & = \sum_{A \subseteq [n]} \sum_{a \in [n] \setminus A} \frac{\partial}{\partial x_a} \phi_A \, dx_a \wedge dx^A \\ & = \sum_{A \subseteq [n]} \sum_{B \subseteq [n] \setminus A} \sum_{a \in [n] \setminus A} (-1)^{\varepsilon_A(a)} \widehat{\phi_A}(B) \, x^{B \setminus \{a\}} dx^{A \cup \{a\}}. \end{align}\]
Proposition 5. The codifferential \(\delta \phi\) satisfies \[\begin{align} \delta \phi & = \sum_{A \subseteq [n]} \sum_{a \in A} x_a \iota_{\frac{\partial}{\partial x_a}} \phi_A dx^A \\ & = \sum_{A \subseteq [n]} \sum_{B \subseteq [n] \setminus A} \sum_{a \in A} (-1)^{\varepsilon_A(a)} \widehat{\phi_A}(B) x^{B \cup \{a\}} dx^{A \setminus \{a\}}. \end{align}\]
Proposition 6. The wedge product satisfies \[\phi \wedge \psi = \sum_{A \cap B = \emptyset} (-1)^{\sum_{a \in A} \varepsilon_B(a)} \left. \phi_A \psi_B \right|_{\{ x_a = 0 \}_{a \in A \cup B}} dx^{A \cup B}.\]
Theorem 1. The Laplace-de Rham operator satisfies \[\Delta \phi = \sum_{A \subseteq [n]} \sum_{B \subseteq [n] \setminus A} (\lvert A \rvert + \lvert B \rvert) \widehat{\phi_A}(B) x^B dx^A.\]
Corollary 1. Every closed cochain is exact, and every coclosed cochain is coexact, except for constant \(0\)-cochains.
Theorem 2. The pseudoinverse of \(\delta \colon C^1(3^{[n]}) \to C^0(3^{[n]})\) satisfies \[\delta^\dagger f = \sum_{a \in [n]} \sum_{A \subseteq [n] \setminus \{a\}} \frac{1}{\lvert A \rvert + 1} \hat{f}(A \cup \{a\}) x^{A} dx_a.\] Equivalently, \[\delta^\dagger f = (\delta^\dagger \delta_e) * df,\] where \(\delta_e = \sum_{A \subseteq [n]} x^A\) is the identity with respect to convolution, and \[\delta^\dagger \delta_e = \sum_{a \in [n]} \sum_{A \subseteq [n] \setminus \{a\}} \frac{1}{\lvert A \rvert + 1} x^{A} dx_a = \sum_{A \subseteq [n]} \frac{1}{\lvert A \rvert!} \sum_{\phi \in \Phi(A)} \phi,\] where \(\Phi(A)\) denotes the set of all \(1\)-cochains of directed paths in the discrete cube from \(A\) to \([n]\). Equality of the two expressions follows from observing that they are both closed.
Corollary 2. Let \(f \colon 2^{[n]} \to \mathbb{R}\) be monotone. Then \(\delta^\dagger f\) is nonnegative.
From Corollary 2, the Harris-Kleitman inequality and a generalization of a theorem of Frankl and Kupavskii follow.
Theorem 3 (Harris-Kleitman inequality [16], [17]). Let \(\mathcal{F}, \mathcal{G} \subseteq 2^{[n]}\) be superset-closed. Then \(\frac{\lvert \mathcal{F} \cap \mathcal{G} \rvert}{2^n} \ge \frac{\lvert \mathcal{F} \rvert}{2^n} \frac{\lvert \mathcal{G} \rvert}{2^n}\), with equality if and only if \(\mathcal{F}\) and \(\mathcal{G}\) are determined by disjoint sets of elements.
Proof. Let \(f = \sum_{F \in \mathcal{F}} \tilde{F}\) and \(g = \sum_{G \in \mathcal{G}} \tilde{G}\). Then \[\begin{align} \frac{\lvert \mathcal{F} \cap \mathcal{G} \rvert}{2^n} & = \langle f, g \rangle \\ & = \langle df, \delta^\dagger g \rangle + \hat{f}(\emptyset)\hat{g}(\emptyset) \\ & \ge \hat{f}(\emptyset)\hat{g}(\emptyset) \\ & = \frac{\lvert \mathcal{F} \rvert}{2^n} \frac{\lvert \mathcal{G} \rvert}{2^n}, \end{align}\] where \(\langle df, \delta^\dagger g \rangle \ge 0\) since \(df \ge 0\) by monotonicity and \(\delta^\dagger g \ge 0\) by Corollary 2. Moreover, we have \(\langle df, \delta^\dagger g \rangle = 0\) if and only if for each \(k \in [n]\), at least one of the partials, \(\frac{\partial}{\partial x_k} f\) and \(\frac{\partial}{\partial x_k} g\), is \(0\). ◻
Remark 1. In fact, any nonnegative \(\phi \in C^1(3^{[n]})\) satisfying \(\delta \phi = g - \hat{g}(\emptyset)\) suffices for Theorem 3. Taking instead \(\phi = \big(\sum_{a \in [n]} \sum_{a \notin A \subseteq [a]} x^A dx_a\big) * dg\), we morally recover Kleitman’s inductive proof [17], where we proceed via the identity \[\langle f, g \rangle = \left\langle \tfrac{\partial}{\partial x_k} f, \tfrac{\partial}{\partial x_k} g \right\rangle + \left\langle f \big|_{x_k = 0}, g \big|_{x_k = 0} \right\rangle.\]
Lemma 1. Let \(\phi \in C^1(3^{[n]})\) be a nonnegative, integer-valued \(1\)-cochain. Then \(\phi\) decomposes into a sum of monotone paths in the discrete cube, each running from a vertex \(A \subseteq [n]\) with \(\delta \phi(A) < 0\) to a vertex \(B \subseteq [n]\) with \(\delta \phi(B) > 0\) such that \(A \subset B\).
Proof. We proceed by induction. If \(\phi = 0\), the decomposition is empty. Otherwise, some vertex has nonzero codifferential. Pick \(A \subseteq [n]\) with \(\delta \phi(A) < 0\); the outflow at \(A\) exceeds the inflow, so by integrality some outgoing edge has weight at least \(1\). Follow such an edge to a successor; at any intermediate vertex \(B \subseteq [n]\), if \(\delta\phi(B) \le 0\), the inflow is at least balanced by outgoing edges, ensuring we can arrive at some \(B\) such that \(\delta \phi(B) > 0\). Subtracting this path produces a nonnegative integer \(1\)-cochain of strictly smaller weight, which decomposes by the inductive hypothesis; adjoining the removed path gives the decomposition of \(\phi\). ◻
Theorem 4 (Generalization of [12]). We first define a \((p, q)\)-matching in a relation \(R \subseteq A \times B\) to be a multiset \(M\) of pairs in \(R\) such that each \(a \in A\) appears in exactly \(p\) pairs of \(M\) and each \(b \in B\) appears in exactly \(q\) pairs of \(M\).
Then for \(\mathcal{F}, \mathcal{G} \subseteq 2^{[n]}\), superset-closed families, there exists a \((p, q)\)-matching between the pairs \((F, G) \in \mathcal{F} \times \mathcal{G}\) with \(F \cup G = [n]\), for \(p = \lvert \mathcal{G} \rvert / \gcd(\lvert \mathcal{F} \rvert, \lvert \mathcal{G} \rvert)\) and \(q = \lvert \mathcal{F} \rvert / \gcd(\lvert \mathcal{F} \rvert, \lvert \mathcal{G} \rvert)\).
Proof. Let \(f = \sum_{F \in \mathcal{F}} \tilde{F}\) and \(g = \sum_{G \in \mathcal{G}} \widetilde{G^c}\).
Set \(p = \lvert \mathcal{G} \rvert / \gcd(\lvert \mathcal{F} \rvert, \lvert \mathcal{G} \rvert)\) and \(q = \lvert \mathcal{F} \rvert / \gcd(\lvert \mathcal{F} \rvert, \lvert \mathcal{G} \rvert)\), and let \[h = p f - q g.\] Then \(h\) is monotone and integer-valued with \(\hat{h}(\emptyset) = 0\), and by Corollary 2, the pseudoinverse \(\delta^\dagger h\) is nonnegative.
Set \(\phi = \delta^\dagger h\). We modify \(\phi\) to be integer-valued without changing its codifferential or losing nonnegativity. While the non-integral edges of \(\phi\) contain a directed cycle \(\psi\), replace \(\phi\) with \(\phi + t\psi\), where \(t > 0\) is minimal such that some edge of \(\psi\) becomes integral. Nonnegativity is preserved, since \(t\) is at most the minimum value of \(\phi\) on edges where \(\psi\) is negative (in the worst case, \(t\) equals that minimum and the corresponding edge becomes zero). Since \(\delta \psi = 0\), this preserves \(\delta \phi = h\), and the count of non-integral edges strictly decreases, so the process terminates.
If on termination non-integral edges remain, they form a forest. At a leaf \(A\) of any component, exactly one incident edge has non-integral \(\phi\)-value and the remaining incident edges have integer \(\phi\)-values. Hence \(\delta \phi(A)\) is the signed sum of an integer and a non-integer, and so non-integer; but \(\delta \phi(A) = h(A) \in \mathbb{Z}\), a contradiction.
Thus \(\phi\) is a nonnegative integer \(1\)-cochain with \(\delta \phi = h\). By Lemma 1, \(\phi\) decomposes into a multiset of monotone paths, each running from a vertex \(G^c\) to a vertex \(F \in \mathcal{F}\).
Each such path corresponds to a pair \((F, G) \in \mathcal{F} \times \mathcal{G}\) with \(G^c \subseteq F\), equivalently \(F \cup G = [n]\). Each \(F\) appears in exactly \(p\) such pairs and each \(G\) in exactly \(q\), yielding the desired \((p, q)\)-matching. ◻
Given \(f \colon 2^{[n]} \to \mathbb{R}\) such that \(\hat{f}(\emptyset) = 0\) and weights \(\alpha \in \mathbb{R}_{\ge 0}^{[n]}\), we consider the optimization problem of finding \(\phi^* \in C^1(3^{[n]})\) that maximizes \[\sum_{k \in [n]} \alpha_k \min(\phi_k)\] among all \(\phi \in C^1(3^{[n]})\) subject to the affine constraint \(\delta \phi = f\).
To analyze this problem, we recall the Karush-Kuhn-Tucker (KKT) conditions, which give necessary and sufficient conditions for optimality in convex optimization problems with affine equality constraints.
Theorem 5 (Karush-Kuhn-Tucker conditions [18]). Consider the optimization problem \[\begin{align} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & g(x) = 0, \end{align}\] where \(f \colon \mathbb{R}^n \to \mathbb{R}\) is convex (not necessarily differentiable) and \(g \colon \mathbb{R}^n \to \mathbb{R}^m\) is affine.
A point \(x^* \in \mathbb{R}^n\) is a global minimizer if and only if there exists \(\lambda \in \mathbb{R}^m\) such that
\(g(x^*) = 0\), and
\(0 \in \partial f(x^*) + \nabla g(x^*)^\top \lambda\).
Here \(\partial f\) denotes the subdifferential of \(f\), and \(\nabla g\) denotes the Jacobian of \(g\).
Applying the KKT conditions to the optimization problem above, we obtain the following primal, dual, and strong duality statements.
Lemma 2. Given \(f \colon 2^{[n]} \to \mathbb{R}\) such that \(\hat{f}(\emptyset) = 0\) and weights \(\alpha \in \mathbb{R}_{\ge 0}^{[n]}\), then \(\phi^* \in C^1(3^{[n]})\) such that \(\delta \phi^* = f\) is a maximizer of \[\sum_{k \in [n]} \alpha_k \min(\phi_k)\] for \(\phi \in C^1(3^{[n]})\) subject to the constraint \(\delta \phi = f\) if and only if there exists \[\lambda = \sum_{i \in I} c_i \lambda_i\] for some \(c_i > 0\) and monotone \(\lambda_i : 2^{[n]} \to \{-1,1\}\) such that:
for each \(i \in I\), the support of \(d\lambda_i\) is contained in the minima of \(\phi^*\), and
for each \(k \in [n]\), \(\sum_{i \in I} c_i \widehat{\lambda_i}(\{k\}) = \frac{1}{2^{n - 1}} \alpha_k\).
Lemma 3. Given \(f \colon 2^{[n]} \to \mathbb{R}\) such that \(\hat{f}(\emptyset) = 0\) and weights \(\alpha \in \mathbb{R}_{\ge 0}^{[n]}\), then \(\lambda^*\) minimizes \(\langle \lambda, f \rangle\) among all \(\lambda \colon 2^{[n]} \to \mathbb{R}\) such that \[\lambda = \sum_{i \in I} c_i \lambda_i\] for some \(c_i > 0\) and monotone \(\lambda_i : 2^{[n]} \to \{-1,1\}\) such that for each \(k \in [n]\), \[\sum_{i \in I} c_i \widehat{\lambda_i}(\{k\}) = \frac{1}{2^{n - 1}} \alpha_k\] if and only if there exists some \(\phi \in C^1(3^{[n]})\) such that for each \(i \in I\), the support of \(d\lambda_i\) is contained in the minima of \(\phi\).
Lemma 4. Given \(f \colon 2^{[n]} \to \mathbb{R}\) such that \(\hat{f}(\emptyset) = 0\) and weights \(\alpha \in \mathbb{R}_{\ge 0}^{[n]}\), let \(\phi^* \in C^1(3^{[n]})\) such that \(\delta \phi^* = f\) be a maximizer of \(\sum_{k \in [n]} \alpha_k \min(\phi_k)\), and let \(\lambda^* \colon 2^{[n]} \to \mathbb{R}\) monotone such that \(\hat{\lambda}^*(\{k\}) = \frac{1}{2^{n-1}} \alpha_k\) be a minimizer of \(\langle \lambda, f \rangle\). Then \[\sum_{k \in [n]} \alpha_k \min(\phi_k^*) = \langle \lambda^*, f \rangle.\]
Remark 2. Each maximizer \(\phi \in C^1(3^{[n]})\) for a given weight \(\alpha \in \Delta^{[n]}\) determines a convex region of weights \(A \subseteq \Delta^{[n]}\) for which \(\phi\) is a maximizer. Moreover, for any such region \(A\), let \(\Phi \subseteq C^1(3^{[n]})\) be the convex region of \(\phi\) that are maximizers at every \(\alpha \in A\), and let \(B\) be the set of all \((\min(\phi_k))_{k \in [n]}\) for all \(\phi \in \Phi\). Then \(\Delta^{[n]}\) uniquely decomposes into the set of maximal regions \(A\).
Vertices of the decomposition are given by \[\frac{1}{\sum_{k \in [n]} \hat{\lambda}(\{k\})} (\hat{\lambda}(\{k\}))_{k \in [n]},\] where \(\lambda \colon 2^{[n]} \to \{-1, 1\}\) is monotone and the support of \(d\lambda\) is contained in the minima of every \(\phi\) that is a maximizer at this vertex.
All non-maximal regions of \(\operatorname{relint}(\Delta^{[n]})\) are given by the intersection of maximal regions containing them, which corresponds to convex combinations of corresponding \(\Phi\) and \(B\). And finally, for all regions of \(\operatorname{relint}(\Delta^{[n]})\), we have \(\dim(A) + \dim(B) = n - 1\).
Theorem 6. Let \(f \colon 2^{[n]} \to \mathbb{R}\) be monotone. Then if \(\phi \in C^1(3^{[n]})\) is a maximizer for \(\alpha \in \mathbb{R}_{\ge 0}^{[n]}\), we have \(\min(\phi_k) \ge 0\) whenever \(\alpha_k > 0\) for all \(k \in [n]\).
Proof. Let \(\lambda \colon 2^{[n]} \to \{-1, 1\}\) be monotone and such that the support of \(d\lambda\) is contained in the minima of \(\phi\) with \((d\lambda)_k\) being nonzero for some \(k \in [n]\). Then \[\begin{align} & \sum_{\mathclap{(d\lambda)_k(A) = 1}} f(A \cup \{k\}) - f(A) \\ = & \sum_{\mathclap{(d(\lambda |_{x_k = 1}))_a(A) = 1}} \phi_a(A \cup \{k\}) \quad - \quad \sum_{\mathclap{(d(\lambda |_{x_k = -1}))_a(A) = 1}} \phi_a(A \cup \{k\}) \quad + \quad \sum_{\mathclap{(d\lambda)_k(A) = 1}} \phi_k(A) \\ & - \sum_{\mathclap{(d(\lambda |_{x_k = 1}))_a(A) = 1}} \phi_a(A) \quad + \quad \sum_{\mathclap{(d(\lambda |_{x_k = -1}))_a(A) = 1}} \phi_a(A) \quad + \quad \sum_{\mathclap{(d\lambda)_k(A) = 1}} \phi_k(A) \\ = & \sum_{\mathclap{(d(\lambda |_{x_k = 1}))_a(A) = 1}} \min(\phi_a) - \phi_a(A) \quad + \quad \sum_{\mathclap{(d(\lambda |_{x_k = -1}))_a(A) = 1}} \min(\phi_a) - \phi_a(A \cup \{k\}) \\ & + \sum_{\mathclap{(d\lambda)_k(A) = 1}} 2 \min(\phi_k). \end{align}\] Thus we have \(\min(\phi_k) \ge 0\) by monotonicity. ◻
Theorem 7. Let \(f, g \colon 2^{[n]} \rightarrow \{-1, 1\}\) be monotone with \(g^{-1}(1) \subseteq f^{-1}(1)\) and \(g\) non-constant. Define \(h \colon 2^{[n]} \rightarrow \{-1, 1\}\) such that \(h\) is \(1\) at \([n]\) and \(-1\) otherwise. Then \[\frac{\langle f - \hat{f}(\emptyset), g \rangle}{\sum_{k \in [n]} \hat{g}(\{k\})} \ge \frac{\langle f - \hat{f}(\emptyset), h \rangle}{\sum_{k \in [n]} \hat{h}(\{k\})}.\]
Proof. We first calculate, \[\langle f - \hat{f}(\emptyset), g \rangle = \langle f - \hat{f}(\emptyset), g + 1 \rangle = \frac{1 - \hat{f}(\emptyset)}{2^{n - 1}} |g^{-1}(1)|.\] Each \(A \in g^{-1}(1)\) has at most \(n\) incoming boundary edges, so \[\sum_{k \in [n]} \hat{g}(\{k\}) \le \frac{n}{2^{n - 1}} |g^{-1}(1)|.\] The ratio is thus at least \((1 - \hat{f}(\emptyset))/n\), with equality achieved by \(h\). ◻
Remark 3. Theorem 7 follows similarly for \(f, g \colon 2^{[n]} \rightarrow \{-1, 1\}\) monotone with \(g^{-1}(-1) \subseteq f^{-1}(-1)\) and \(g\) non-constant, with \(h \colon 2^{[n]} \rightarrow \{-1, 1\}\) such that \(h\) is \(-1\) at \(\emptyset\) and \(1\) otherwise.
We now give a generalization of Kleitman’s conjecture, as mentioned in [13]. By Theorem 6, the nonnegativity condition \(\min(\phi_k) \ge 0\) is automatic for monotone \(f\) and need not be imposed separately.
Conjecture 3. We first say that a general \(f \colon 2^{[n]} \to \mathbb{R}\) is polar if there exists \(\phi \in C^1(3^{[n]})\) with \(\delta \phi = f - \hat{f}(\emptyset)\) such that either:
every \(\emptyset\)-adjacent edge is minimal: \(\phi_k(\emptyset) = \min(\phi_k)\) for all \(k \in [n]\), or
every \([n]\)-adjacent edge is minimal: \(\phi_k([n] \setminus \{k\}) = \min(\phi_k)\) for all \(k \in [n]\).
Equivalently, \(\sum_{k \in [n]} \min(\phi_k) = \min\left(1 + \hat{f}(\emptyset),\, 1 - \hat{f}(\emptyset)\right)\).
The conjecture can then be stated as follows. Let \(f \colon 2^{[n]} \to \{-1, 1\}\) be monotone. Then \(f\) is polar.
Theorem 8. Let \(f \colon 2^{[n]} \to \{-1, 1\}\) be monotone such that, for some \(k \in [n]\):
\(f(A) = -1\) for all \(A \subseteq [n]\) with \(\lvert A \rvert < k\), and
\(f(A) = 1\) for all \(A \subseteq [n]\) with \(\lvert A \rvert \ge k\).
Then \(f\) is polar.
Proof. We consider \(\delta^\dagger f\), and for each \(i \in [n]\), define \(g_i \colon 2^{[n]} \to \{-1, 1\}\) such that \(g_i(A) = 1\) if and only if \(|A| \ge i\).
By permutational symmetry of \(f\), the value \((\delta^\dagger f)_a(A)\) depends only on \(|A|\). Applying Theorem 7 to each \(g_i\), the value of \((\delta^\dagger f)_a\) along any boundary edge of \(g_i\) is at least \(\frac{1}{n} \min(1 + \hat{f}(\emptyset), 1 - \hat{f}(\emptyset))\). ◻
Theorem 9. Let \(f \colon 2^{[n]} \to \{-1, 1\}\) be monotone and \(\phi \in C^1(3^A)\) for some \(A \sqcup B = [n]\) such that \(\delta \phi = f \big|_{\{x_b = 0\}_{b \in B}} - \hat{f}(\emptyset)\) and \[\sum_{k \in A} \min(\phi_k) = \min\left(1 + \hat{f}(\emptyset), 1 - \hat{f}(\emptyset)\right).\] Then \(f\) is polar.
Proof. We construct \[\psi = \sum_{a \in \{-1, 1\}^A} 1_a \wedge \delta^\dagger \left( f \big|_{\{x_k = a_k\}_{k \in A}} \right),\] where \(1_a \colon 2^A \to \{0, 1\}\) is the indicator of \(a\).
By direct calculation, we have \[\begin{align} \delta(\phi + \psi)(C) & = \left( f \big|_{\{x_b = 0\}_{b \in B}} - \hat{f}(\emptyset) \right)(A \cap C) + \delta \delta^\dagger \left( f \big|_{\{x_k = c_k\}_{k \in A}} \right)(B \cap C) \\ & = \left( \frac{1}{2^{\lvert B \rvert}} \sum_{D \subseteq B} f(A \cap C \cup D) - \hat{f}(\emptyset) \right) + \left( f(C) - \frac{1}{2^{\lvert B \rvert}} \sum_{D \subseteq B} f(A \cap C \cup D) \right) \\ & = f(C) - \hat{f}(\emptyset), \end{align}\] where \(c \in \{-1, 1\}^{[n]}\) is the vertex corresponding to \(C\).
Moreover, by nonnegativity of \(\psi\) by Corollary 2, we have \[\sum_{k \in A} \min(\phi_k + \psi_k) \ge \min\left(1 + \hat{f}(\emptyset), 1 - \hat{f}(\emptyset)\right),\] which is also an upper bound by Lemma 4, thus giving equality. ◻
Corollary 3. Let \(f \colon 2^{[n]} \to \{-1, 1\}\) be monotone such that \(\hat{f}(\emptyset) \le 0\) and \(f^{-1}(1)\) is contained in the union of two stars. Then \(f\) is polar.
Remark 4. Theorem 9 provides a natural generalization of the 2-edge and 3-edge cases mentioned by Kleitman in [11]. Regarding Corollary 3, Chvátal’s conjecture in this case was proved by Kleitman and Magnanti [10] and later re-proved by Frankl and Kupavskii [12], but to our knowledge no proof of Kleitman’s conjecture in this case has appeared in the literature.
Lemma 5. Let \(f \colon 2^{[n]} \to \mathbb{R}\) and \(\phi \in C^1(3^{[n]})\) be arbitrary. Then \[\delta (f \wedge \phi) = f \delta \phi - \iota_{\nabla f} \phi.\]
Theorem 10. Let \(f \colon 2^{[m]} \to \{-1, 1\}\) and \(g_1, \dots, g_m \colon 2^{[n]} \to \{-1, 1\}\) be monotone such that:
\(\widehat{g_i}(\emptyset) = 0\) for all \(i \in [m]\),
\(\langle g_i, g_j \rangle = 0\) for all \(i \ne j\), and
each \(f, g_1, \dots, g_m\) is polar.
Define their composition \(f \circ g \colon 2^{[n]} \to \{-1, 1\}\) by \[(f \circ g)(A) = f(g_1(A), \dots, g_m(A)).\] Then \(f \circ g\) is polar.
Proof. Construct \(\phi \in C^1(3^{[m]})\) and \(\psi_1, \dots, \psi_m \in C^1(3^{[n]})\) such that \(\delta \phi = f - \hat{f}(\emptyset)\) and \(\delta \psi_i = g_i\) for all \(i \in [m]\) satisfying Conjecture 3. We then construct \[\omega = \sum_{i \in [m]} (\phi_i \circ g) \wedge \psi_i.\] For each \(i \in [m]\) and \(A \subseteq [m] \setminus \{i\}\), the function \(\prod_{j \in A} g_j\) depends on variables disjoint from those of \(g_i\) by our assumptions on \(g_1, \dots, g_m\) and the equality case of Theorem 3. Thus \(\iota_{\nabla(\prod_{j \in A} g_j)} \psi_i = 0\). Combined with Lemma 5, it follows that \[\begin{align} \delta \omega & = \sum_{i \in [m]} \sum_{A \subseteq [m] \setminus \{i\}} \delta \left( \widehat{\phi_i}(A) \left( \prod_{j \in A} g_j \right) \wedge \psi_i \right) \\ & = \sum_{i \in [m]} \sum_{A \subseteq [m] \setminus \{i\}} \widehat{\phi_i}(A) \left( \prod_{j \in A} g_j \right) g_i \\ & = \sum_{A \subseteq [m]} \sum_{i \in A} \widehat{\phi_i}(A \setminus \{i\}) \prod_{i \in A} g_i \\ & = \sum_{\emptyset \subset A \subseteq [m]} \widehat{\phi}(A) \prod_{i \in A} g_i \\ & = f \circ g - \hat{f}(\emptyset). \end{align}\]
Moreover, each term \[(\phi_i \circ g) \wedge \psi_i = \sum_{j \in [n]} (\phi_i \circ g) \big|_{x_j = 0} \, (\psi_i)_j \, dx_j\] is independently polar at the same vertex as \(\phi\): both \(\phi_i \circ g\) and \((\psi_i)_j\) are nonnegative (Theorem 6) and attain their minima at that vertex, so the product is minimal on each adjacent edge. ◻
The following strengthens Conjecture 3, extending the edge condition to all strictly positive weights \(\alpha\).
Conjecture 4. Let \(f \colon 2^{[n]} \to \{-1, 1\}\) be monotone and \(\alpha \in \mathbb{R}_{>0}^{[n]}\). For any maximizer \(\phi \in C^1(3^{[n]})\) of \(\sum_{k \in [n]} \alpha_k \min(\phi_k)\) subject to \(\delta \phi = f - \hat{f}(\emptyset)\), either:
every \(\emptyset\)-adjacent edge is minimal: \(\phi_k(\emptyset) = \min(\phi_k)\) for all \(k \in [n]\), or
every \([n]\)-adjacent edge is minimal: \(\phi_k([n] \setminus \{k\}) = \min(\phi_k)\) for all \(k \in [n]\).
Equivalently, Conjecture 3 is strengthened by requiring all maximal regions of weights \(A \subseteq \Delta^{[n]}\) touch the center.
We close with the following natural conjecture.
Conjecture 5. Let \(f \colon 2^{[n]} \to \{-1, 1\}\) be monotone. Then there exists \(\phi \in C^1(3^{[n]})\) with \(\delta \phi = f - \hat{f}(\emptyset)\) such that the support of \(df\) is contained in the maxima of \(\phi\); that is, for every \(k \in [n]\) and \(A \subseteq [n] \setminus \{k\}\) with \((df)_k(A) = 1\), we have \(\phi_k(A) = \max(\phi_k)\).