CommunicationComplexity.Rectangle.IsMonochromatic
defimported Lean
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$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in def CommunicationComplexity.Rectangle.IsMonochromatic (S : Set (X × Y)) (g : X → Y → α) : Prop
- Defined in
- TCSlib, `CommunicationComplexity.Rectangle.IsMonochromatic`
- Lean proof
- By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.CommunicationComplexity.Rectangle.IsMonochromatic← CommunicationComplexity.Rectangle.IsMonochromatic (TCSlib/CommunicationComplexity/DeterministicCC/Rectangle.lean:85): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 6
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_isMonoPartitionLeaf rectangles of a protocol form a monochromatic partition. Let $p$ be a deterministic two-party communication protocol over input types…
- CommunicationComplexity.Rectangle.IsMonoPartitionA collection $\mathcal{P}$ of subsets of $X \times Y$ is a monochromatic rectangle partition for $g : X \to Y \to \alpha$ if every…
- is_monochromatic_cover_allGiven types $X$ and $Y$ and a curried Boolean function $f : X \to Y \to \mathrm{Bool}$, a collection…
- CommunicationComplexity.Rectangle.IsFoolingSetA 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$…
- rectangle_size_boundFor finite types $X$ and $Y$ and a curried Boolean function $f : X \to Y \to \mathrm{Bool}$, the prior-free rectangle-size bound…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_monoLeaf rectangles of a protocol are monochromatic. Let $p$ be a deterministic two-party communication protocol over input types $X$ and $Y$…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in /-- A set `S ⊆ X × Y` is monochromatic for `g` if `g` takes the same value at any two points of `S`. [RY20, Ch. 1, Definition (monochromatic)]. -/ def CommunicationComplexity.Rectangle.IsMonochromatic (S : Set (X × Y)) (g : X → Y → α) : Prop := ∀ x x' y y', (x, y) ∈ S → (x', y') ∈ S → g x y = g x' y'