AFTD Auto-Formalizing Theoretical Domains

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.
Verified
07 Oct 2026
Axioms
none listed
Used by 6

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'
See it in the graphDiscuss this resultChallenge it