2024/03/12 by Diego Gamboa, Gamboa, Diego, Carlos Uzcategui-Aylwin +1
Computer Science · Physics and Astronomy · #05C15 #05D10 #Color Science and Applications #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2403.08104
openalex publication_date 2024/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A coloring on a finite or countable set X is a function φ: [X]2 → \0,1\, where [X]2 is the collection of unordered pairs of X. The collection of homogeneous sets for φ, denoted by Hom(φ), consist of all H ⊆ X such that φ is constant on [H]2; clearly, Hom(φ) = Hom(1-φ). A coloring φ is reconstructible up to complementation from its homogeneous sets if, for any coloring ψ on X such that Hom(φ) = Hom(ψ), either ψ= φ or ψ= 1-φ. By R we denote the collection of all colorings reconstructible from their homogeneous sets. Let φ and ψ be colorings on X, and set D(φ, ψ) = \ \x,y\ ∈ [X]2: ψ\x,y\ ≠ φ\x,y\\. If φ\not∈ R, let r(φ) = min\|D(φ, ψ)|: Hom(φ) = Hom(ψ), ψ≠ φ, ψ≠ 1-φ\. A coloring ψ such that Hom(φ)=Hom(ψ), φ≠ ψ and 1-φ≠ ψ is called a \em non trivial reconstruction of φ. If, in addition, r(φ) =|D(φ, ψ)|, we call ψ a \em minimal reconstruction of φ. The purpose of this article is to study the minimal reconstructions of a coloring. We show that, for large enough X, r(φ) can only takes the values 1 or 4.