48 Communication Complexity — Rectangle
48.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.
48.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 subset \(R \subseteq X \times Y\) is a rectangle — that is, \(R = A \times B\) for some \(A \subseteq X\) and \(B \subseteq Y\) — if and only if it is closed under crossing: for all \(x, x' \in X\) and \(y, y' \in Y\), whenever \((x, y) \in R\) and \((x', y') \in R\), both mixed pairs \((x', y)\) and \((x, y')\) also lie in \(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.
Let \(g : X \times Y \to \alpha \) and let \(\mathcal{P}\) be a monochromatic rectangle partition for \(g\). Then every point \(p \in X \times Y\) belongs to at least one member \(R \in \mathcal{P}\).
Let \(\mathcal{P}\) be a monochromatic rectangle partition for a function \(g : X \to Y \to \alpha \), and let \(R, S \in \mathcal{P}\). If some point \(p \in X \times Y\) lies in both \(R\) and \(S\), then \(R = S\).
Let \(\mathcal{P}\) be a monochromatic rectangle partition for a function \(g : X \to Y \to \alpha \), and let \(R \in \mathcal{P}\). If \((x,y)\) and \((x',y')\) both belong to \(R\), then the two "crossed" pairs \((x',y)\) and \((x,y')\) also belong to \(R\).
Let \(\mathcal{P}\) be a monochromatic rectangle partition for a function \(g : X \to Y \to \alpha \), and let \(R \in \mathcal{P}\). Then \(g\) is constant on \(R\): for any \((x,y), (x',y') \in R\) we have \(g\, x\, y = g\, x'\, y'\).
Let \(X\), \(Y\), and \(\alpha \) be sets and let \(g : X \times Y \to \alpha \). If \(S \subseteq X \times Y\) is a fooling set for \(g\) and \(\mathcal{P}\) is a monochromatic rectangle partition for \(g\), then the cardinality of \(S\) is at most the cardinality of \(\mathcal{P}\), that is \(\left\lvert S\right\rvert \le \left\lvert \mathcal{P}\right\rvert \), where cardinalities are compared as extended natural numbers (allowing the value \(\infty \)).
Let \(g : X \times Y \to \alpha \), let \(S \subseteq X \times Y\) be a fooling set for \(g\), and let \(\mathcal{P}\) be a monochromatic rectangle partition for \(g\). If \(\mathcal{P}\) is finite, then the number of points of \(S\) is at most the number of members of \(\mathcal{P}\); that is, \(\left\lvert S\right\rvert \le \left\lvert \mathcal{P}\right\rvert \).