CommunicationComplexity.Rectangle.IsMonoPartition
defimported Lean
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.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in def CommunicationComplexity.Rectangle.IsMonoPartition (Part : Set (Set (X × Y))) (g : X → Y → α) : Prop
- Defined in
- TCSlib, `CommunicationComplexity.Rectangle.IsMonoPartition`
- 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.IsMonoPartition← CommunicationComplexity.Rectangle.IsMonoPartition (TCSlib/CommunicationComplexity/DeterministicCC/Rectangle.lean:104): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 2
- CommunicationComplexity.Rectangle.IsMonochromaticA 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.,…
- CommunicationComplexity.Rectangle.IsRectangleA subset $S \subseteq X \times Y$ is a rectangle if it factors as a product $A \times B$ for some $A \subseteq X$ and…
- Used by 12
- 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.foolingSet_ncard_le_of_monoPartitionFooling set bound via monochromatic partition. Let $g : X \times Y \to \alpha$, let $S \subseteq X \times Y$ be a fooling set for $g$, and…
- CommunicationComplexity.Rectangle.foolingSet_encard_le_of_monoPartitionFooling set bound from a monochromatic rectangle partition. Let $X$, $Y$, and $\alpha$ be sets and let $g : X \times Y \to \alpha$. If…
- CommunicationComplexity.Rectangle.monoPartition_part_uniqueUniqueness of the part containing a point. Let $\mathcal{P}$ be a monochromatic rectangle partition for a function…
- CommunicationComplexity.Rectangle.monoPartition_values_eqConstant values within a part. Let $\mathcal{P}$ be a monochromatic rectangle partition for a function $g : X \to Y \to \alpha$, and let…
- CommunicationComplexity.Rectangle.monoPartition_point_memEvery point lies in some part of a partition. Let $g : X \times Y \to \alpha$ and let $\mathcal{P}$ be a monochromatic rectangle partition…
- CommunicationComplexity.Deterministic.Protocol.sum_indicator_leafRectangles_eqIndicator sum over leaf rectangles recovers the protocol output. Let $X$ and $Y$ be input types whose product $X \times Y$ carries a…
- CommunicationComplexity.Deterministic.foolingSet_ncard_le_pow_of_communicationComplexity_leFooling set bound from communication complexity. Let $g : X \times Y \to \alpha$ be a two-argument function, and let…
- CommunicationComplexity.Rectangle.monoPartition_cross_memCross closure within a part. Let $\mathcal{P}$ be a monochromatic rectangle partition for a function $g : X \to Y \to \alpha$, and let…
- CommunicationComplexity.Deterministic.Rank.boolFunctionRank_le_ncardRank bounded by monochromatic partition size. Let $X$ be a finite set, $Y$ a finite set, and $f : X \to Y \to \mathrm{Bool}$ a Boolean…
- CommunicationComplexity.Deterministic.mono_partition_of_communicationComplexity_leLow deterministic complexity yields a small monochromatic partition. Let $g : X \times Y \to \alpha$ be a two-argument function, and let…
- CommunicationComplexity.Deterministic.le_communicationComplexity_of_forall_lt_ncardRectangle-partition lower bound on communication complexity. Let $g : X \to Y \to \alpha$ be a two-argument function and let $n$ be a…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in /-- A set of sets is a monochromatic rectangle partition of `X × Y` with respect to `g` if every member is a rectangle, every member is monochromatic for `g`, the members cover `X × Y`, and distinct members are disjoint. [RY20, Thm 1.7] (the notion of a partition of `X × Y` into monochromatic rectangles). -/ def CommunicationComplexity.Rectangle.IsMonoPartition (Part : Set (Set (X × Y))) (g : X → Y → α) : Prop := (∀ R ∈ Part, IsRectangle R) ∧ (∀ R ∈ Part, IsMonochromatic R g) ∧ ⋃₀ Part = Set.univ ∧ (∀ R S, R ∈ Part → S ∈ Part → R ≠ S → Disjoint R S)