CommunicationComplexity.Rectangle.IsFoolingSet
defimported Lean
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$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in variable {X Y α : Type*} in def CommunicationComplexity.Rectangle.IsFoolingSet (S : Set (X × Y)) (g : X → Y → α) : Prop
- Defined in
- TCSlib, `CommunicationComplexity.Rectangle.IsFoolingSet`
- 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.IsFoolingSet← CommunicationComplexity.Rectangle.IsFoolingSet (TCSlib/CommunicationComplexity/DeterministicCC/Rectangle.lean:95): 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 5
- 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.Functions.Disjointness.foolingSet_isFoolingSetThe disjointness fooling set. Fix $n \in \bbn$, and consider the set-disjointness function on subsets of $[n]$, namely the Boolean…
- CommunicationComplexity.Deterministic.clog_ncard_le_communicationComplexityFooling-set lower bound for deterministic communication complexity. Let $g : X \times Y \to \alpha$ be a two-argument function and let…
- 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…
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 a fooling set for `g` if every monochromatic rectangle with respect to `g` contains at most one point of `S`. [Rou16, §4.2.5 Definition (fooling set)]. Deviation: Rou16 define a fooling set by the two conditions "`g` is constant on `S`" and "for distinct points of `S`, one of the two mixed pairs has a different `g`-value"; the definition here is the consequence those conditions are used for (every monochromatic rectangle meets `S` in at most one point), which is all the counting bound needs. -/ def CommunicationComplexity.Rectangle.IsFoolingSet (S : Set (X × Y)) (g : X → Y → α) : Prop := ∀ R : Set (X × Y), IsRectangle R → IsMonochromatic R g → (S ∩ R).Subsingleton