51 Communication Complexity — Rectangle
51.1 Overview
This module develops the combinatorial theory of rectangles in the product set \(X \times Y\) as used in deterministic communication complexity. It introduces rectangles, monochromatic rectangles, fooling sets, and monochromatic rectangle partitions, and proves the fundamental bound that the number of parts in any monochromatic rectangle partition is at least the size of any fooling set.
51.2 Declarations
A subset \(S \subseteq X \times Y\) is a rectangle if it factors as a product \(A \times B\) for some \(A \subseteq X\) and \(B \subseteq Y\).
A set \(R \subseteq X \times Y\) is a rectangle if and only if it satisfies the cross property: whenever \((x, y) \in R\) and \((x', y') \in R\), the mixed pairs \((x', y)\) and \((x, y')\) also belong to \(R\).
A set \(S \subseteq X \times Y\) is monochromatic for a function \(g : X \to Y \to \alpha \) if \(g\) is constant on \(S\), i.e., \(g\, x\, y = g\, x'\, y'\) for all \((x,y), (x',y') \in S\).
A set \(S \subseteq X \times Y\) is a fooling set for \(g : X \to Y \to \alpha \) if every monochromatic rectangle with respect to \(g\) contains at most one point of \(S\), i.e., \(S \cap R\) is a subsingleton for every rectangle \(R\) that is monochromatic for \(g\).
A collection \(\mathcal{P}\) of subsets of \(X \times Y\) is a monochromatic rectangle partition for \(g : X \to Y \to \alpha \) if every member of \(\mathcal{P}\) is a rectangle, every member is monochromatic for \(g\), the members cover all of \(X \times Y\), and distinct members are disjoint.
If \(\mathcal{P}\) is a monochromatic rectangle partition for \(g\), then for every point \(p \in X \times Y\) there exists some \(R \in \mathcal{P}\) with \(p \in R\).
If \(\mathcal{P}\) is a monochromatic rectangle partition for \(g\) and a point \(p \in X \times Y\) belongs to two parts \(R, S \in \mathcal{P}\), then \(R = S\).
If \(\mathcal{P}\) is a monochromatic rectangle partition for \(g\), \(R \in \mathcal{P}\), and \((x,y), (x',y') \in R\), then the mixed pairs \((x',y)\) and \((x,y')\) both belong to \(R\).
If \(\mathcal{P}\) is a monochromatic rectangle partition for \(g\), \(R \in \mathcal{P}\), and \((x,y), (x',y') \in R\), then \(g\, x\, y = g\, x'\, y'\).
If \(S\) is a fooling set for \(g\) and \(\mathcal{P}\) is a monochromatic rectangle partition for \(g\), then \(\# S \le \# \mathcal{P}\) in the sense of extended natural number cardinality (Set.encard).
If \(S\) is a fooling set for \(g\), \(\mathcal{P}\) is a monochromatic rectangle partition for \(g\), and \(\mathcal{P}\) is finite, then \(|S| \le |\mathcal{P}|\) as natural numbers (Set.ncard).