Combinatorial Rectangle

A combinatorial rectangle is a Cartesian product (A\times B) contained in a product space (X\times Y), where (A\subseteq X) and (B\subseteq Y). The term refers to the independence of the two coordinates: membership of (x) in (A) places no condition on membership of (y) in (B), and every permitted first coordinate occurs with every permitted second coordinate. Combinatorial rectangles form a basic structural class in communication complexity, where they describe sets of inputs that produce the same communication transcript.

When a relation on (X\times Y) is represented by a matrix whose rows are indexed by (X) and whose columns are indexed by (Y), a rectangle corresponds to a submatrix obtained by selecting an arbitrary set of rows and an arbitrary set of columns. The selected rows and columns need not be consecutive. This distinguishes a combinatorial rectangle from a geometric rectangle in an ordered grid, whose definition ordinarily depends on contiguity or convexity.

Definition and elementary structure

For sets (X) and (Y), a subset (R\subseteq X\times Y) is a combinatorial rectangle precisely when there exist (A\subseteq X) and (B\subseteq Y) such that

[ R=A\times B. ]

Equivalently, a nonempty set (R) is rectangular when it satisfies the mixing property

[ (x,y),(x',y')\in R \quad\Longrightarrow\quad (x,y'),(x',y)\in R. ]

The implication expresses closure under exchanging second coordinates between pairs already in the set. For a nonempty rectangular relation, its factors are uniquely determined by the coordinate projections:

[ A={x\in X:\exists y\in Y,\ (x,y)\in R}, ]

[ B={y\in Y:\exists x\in X,\ (x,y)\in R}. ]

The empty set also has rectangular representations, including (\varnothing\times B) and (A\times\varnothing), so its factors are not unique.

The intersection of two rectangles is again a rectangle, since

[ (A_1\times B_1)\cap(A_2\times B_2) =(A_1\cap A_2)\times(B_1\cap B_2). ]

A union of rectangles generally fails to be rectangular. For example, if (x_0\ne x_1) and (y_0\ne y_1), the set

[ {(x_0,y_0),(x_1,y_1)} ]

omits the two mixed pairs required by the mixing property. Rectangle covers and rectangle partitions are therefore distinct from closure systems generated by intersections.

Matrix formulation

Let (M) be a matrix indexed by (X\times Y). A rectangle (A\times B) is monochromatic with value (c) when

[ M_{x,y}=c ]

for every (x\in A) and (y\in B). For a Boolean function

[ f:X\times Y\to{0,1}, ]

a (1)-rectangle lies entirely inside (f^{-1}(1)), while a (0)-rectangle lies entirely inside (f^{-1}(0)). The minimum number of monochromatic rectangles required to cover or partition these sets yields several measures of combinatorial complexity.

A rectangle cover permits overlaps. A rectangle partition requires pairwise disjoint rectangles whose union is the designated relation or matrix domain. These conditions produce different minima because an overlapping family may represent a relation more economically than any disjoint family. In graph terminology, a (1)-rectangle is a complete bipartite subgraph of the bipartite graph represented by the matrix, and a rectangle cover is therefore a biclique cover.

The indicator matrix of a rectangle has the outer-product form

[ \mathbf 1_A\mathbf 1_B^{\mathsf T}. ]

Consequently, every nonempty rectangle indicator has matrix rank one over any field. A partition of a matrix into (t) monochromatic (1)-rectangles expresses its (1)-matrix as a sum of (t) rank-one indicator matrices, which implies that its rank is at most (t). This observation underlies the log-rank bound in deterministic communication complexity.

Communication protocols

In the standard two-party setting, one party receives (x\in X), while the other receives (y\in Y). Andrew Yao created the formal two-party communication model in which the parties compute a function of ((x,y)) while minimizing the number of communicated bits. The geometry of deterministic protocols is rectangular because each message restricts only the sender’s own possible inputs.

For every transcript (\tau) of a deterministic protocol, the set of input pairs producing (\tau) is a combinatorial rectangle. This fact follows inductively from the protocol tree. A message sent by the holder of (x) divides the current rectangle by replacing its row factor with a subset, while a message sent by the holder of (y) replaces its column factor with a subset. Every leaf of the tree therefore corresponds to a rectangle, and correctness requires that each leaf rectangle be monochromatic.

A deterministic protocol using at most (c) bits has at most (2^c) transcripts. Its input matrix is consequently partitioned into at most (2^c) monochromatic rectangles. If every monochromatic rectangle partition of (f) requires at least (N) members, then

[ D(f)\geq \lceil\log_2 N\rceil, ]

where (D(f)) denotes deterministic communication complexity. The converse does not hold with the same parameters for arbitrary partitions, because a collection of rectangles need not possess the recursive row-or-column separation imposed by a protocol tree.

In nondeterministic communication complexity, a (1)-input is certified by identifying a (1)-rectangle containing it. The logarithm of the minimum (1)-rectangle cover number determines the corresponding nondeterministic cost up to the conventions used for verification and indexing. Mauricio Karchmer and Avi Wigderson built a related communication framework in which rectangle structure connects Boolean circuit depth with the communication complexity of search relations.

The inequality relation

A concrete covering problem arises from the directed inequality relation

[ \operatorname{NEQ}_n={(i,j)\in[n]\times[n]:i\ne j}. ]

Every rectangle (A\times B) contained in (\operatorname{NEQ}_n) satisfies (A\cap B=\varnothing), since a common element would place a diagonal pair inside the rectangle. In 2016, You Watanabe and Kanan Matsuura discovered the exact directed rectangle-cover number of this relation through an antichain construction. If (m(n)) denotes the minimum number of rectangles whose union is (\operatorname{NEQ}_n), their result is

[ m(n)=\min\left{m: n\leq {m\choose \lfloor m/2\rfloor}\right}. ]

The lower bound follows by assigning to each (i\in[n]) the set

[ S_i={t:i\in A_t}, ]

where (A_t\times B_t) is the (t)-th rectangle in a cover. Coverage of the ordered pair ((i,j)) gives an index (t\in S_i\setminus S_j), because (i\in A_t), (j\in B_t), and (A_t\cap B_t=\varnothing). Coverage of ((j,i)) similarly gives an index in (S_j\setminus S_i). The family ({S_i:i\in[n]}) is therefore an antichain in the Boolean lattice. Sperner's theorem then yields

[ n\leq {m\choose\lfloor m/2\rfloor}. ]

For the matching construction, choose (n) distinct subsets (S_i\subseteq[m]), all of cardinality (\lfloor m/2\rfloor). For each (t\in[m]), define

[ A_t={i:t\in S_i}, \qquad B_t={j:t\notin S_j}. ]

The factors are disjoint when regarded as subsets of the common label set ([n]), so each (A_t\times B_t) avoids the diagonal. Distinct equal-sized sets are incomparable under inclusion, which ensures that every ordered pair of unequal labels belongs to at least one of the constructed rectangles.

By the central estimate for binomial coefficients,

[ {m\choose\lfloor m/2\rfloor} =\Theta\left(\frac{2^m}{\sqrt m}\right). ]

It follows that

[ m(n)=\log_2 n+\frac12\log_2\log_2 n+O(1). ]

This example demonstrates that directed rectangle covering is governed by the incidence structure of the factors rather than solely by the cardinality of the relation.

Lower-bound methods

A fooling set for a Boolean function is a collection of equally valued matrix entries arranged so that no monochromatic rectangle contains two distinct members of the collection. A fooling set of size (s) forces every corresponding monochromatic rectangle cover to contain at least (s) rectangles, producing a communication lower bound of (\log_2 s).

The rank method uses linear algebra instead of pairwise incompatibility. If a deterministic protocol partitions the (1)-entries of a Boolean matrix into (t) rectangles, then the matrix rank is at most (t). Hence

[ D(f)\geq \log_2\operatorname{rank}(M_f). ]

For randomized protocols, the relevant rectangles need not be perfectly monochromatic. Distributional arguments instead measure the imbalance of function values inside large rectangles. Discrepancy theory formalizes this imbalance, while the corruption method bounds how closely a large rectangle approaches monochromaticity under a specified input distribution.