Definitions: Given a graph $G$ and $S$, $T \subseteq V(G)$, let $e_G(S, T)$ denote the number of edges of $G$ with one endpoint in $S$ and the other in $T$ and let $$d_G(S, T) := \frac{e_G(S, T)}{\lvert S \rvert \lvert T \rvert}$$ denote the density of edges between $S$ and $T$. $\newcommand{\partition}{\mathcal{P}}$
If $G_1$ and $G_2$ are two (unweighted) graphs with vertex set $[n]$, their cut distance is $$\lVert G_1 - G_2 \rVert_{\square} := \max_{S, T \subseteq [n]} \frac{\lvert e_{G_1}(S, T) - e_{G_2}(S, T)\rvert}{n^2}.$$ We will also need to define the cut distance of edge-weighted graphs. This is more complicated than the unweighted version, but only slightly. If $G$ is an edge-weighted graph, let $\beta_{uv}(G)$ denote the weight of the edge $uv$ in $G$. If $G_1$ and $G_2$ are two edge-weighted graphs with vertex set $[n]$, then $$\lVert G_1 - G_2 \rVert_{\square} := \max_{S, T \subseteq [n]} \frac{\bigl\lvert \sum_{u \in S, v \in T} \bigl(\beta_{uv}(G_1) - \beta_{uv}(G_2)\bigr)\bigr\rvert}{n^2}.$$
Finally, given a graph $G$ with vertex set $V$ and a partition $\partition = \{V_1, \ldots, V_k\}$ of $V$, we define a weighted complete graph $G_{\partition}$ on $V$, where the edge $uv$ has weight $d_G(V_1, V_j)$ if $u \in V_i$ and $v \in V_j$.
Background: The Weak Regularity Lemma of Frieze and Kannan states that any graph $G$ can be approximated by a graph of the form $G_{\partition}$, where $\partition$ has a relatively small number of parts. Specifically, if $G$ is a graph and $\varepsilon > 0$, then there is a partition $\partition$ of $V(G)$ (into $2^{\Theta(1/\varepsilon^2)}$ parts; note that the size of $\partition$ does not depend on $G$) such that $$\lVert G - G_{\partition} \rVert_{\square} < \varepsilon.$$ As the name may suggest, this result is similar to Szemeredi's Regularity Lemma, but with a weaker conclusion. (Note that the assertion above that a partition with $2^{\Theta(1/\varepsilon^2)}$ parts is "relatively small" is only in comparison to the number of parts that are typically necessary for an application of Szemeredi's Regularity Lemma.)
There is also an analytic version of the Weak Regularity Lemma, and this is the version that I'm primarily interested in. A kernel is a symmetric, measurable, bounded function $W : [0, 1]^2 \to \mathbb{R}$. The cut distance of two kernels $W_1$ and $W_2$ is $$\lVert W_1 - W_2 \rVert_{\square} := \sup_{S, T \subseteq [0,1]} \biggl\lvert \iint_{S \times T} \bigl(W_1(x, y) - W_2(x, y)\bigr)\,dxdy\biggr\rvert,$$ where the supremum is taken over all pairs of measurable subsets of $[0,1]$.
The Weak Regularity Lemma for kernels states that for any $\varepsilon > 0$ and any kernel $W$, there exists a partition $\partition$ (whose size depends only on $\varepsilon$) and a stepfunction $W_{\partition}$ that is constant on the blocks $P_i \times P_j$ induced by $\partition$ such that $$\lVert W - W_{\partition} \rVert_{\square} < \varepsilon.$$
If one is willing to live with a modest increase in the number of parts (though the number is still $2^{\Theta(1/\varepsilon^2)}$), one can impose additional conditions on the approximating stepfunction $W_{\partition}$. First, one can require that $W_{\partition}$ be obtained by averaging $W$ over the blocks induced by $\partition$. (Note that a priori, the step-function $W_{\partition}$ guaranteed by the statement above need not have any particular connection to $W$.) In the language of probability theory, this condition says that $W_{\partition}$ is the conditional expectation $\mathbb{E}(W \mid \mathcal{B}_{\partition})$, where $\mathcal{B}_{\partition}$ is the $\sigma$-algebra induced by $\partition$. Second, one can require that $\partition$ be an equipartition of $[0, 1]$, i.e., a partition into sets of equal measure.
For much more about all of this, see Sections 9.1 and 9.2 of Lovasz's book Large Networks and Graph Limits.
Question: I would like to approximate a kernel $W$ by a stepfunction $W_{\partition}$ with the following properties:
- $\partition$ is an equipartition of $[0,1]$;
- $W_{\partition} \geq W$ pointwise.
Can the second condition be achieved? That is, for every kernel $W$, must there exist a partition $\partition$ with a bounded number of parts such that $W$ can be well-approximated by a stepfunction $W_{\partition}$ that satisfies both of the conditions above?
