Regresar

Minimal Reconstructions of a Coloring from its Homogeneous Sets

Abstract:

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(φ), consists 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 (Formula presented.) If φ∉R, let (Formula presented.) A coloring ψ such that hom(φ)=hom(ψ), φ≠ψ and 1-φ≠ψ is called a non trivial reconstruction of φ. If, in addition, r(φ)=|D(φ,ψ)|, we call ψ a minimal reconstruction of φ. The purpose of this article is to study the minimal reconstructions of a coloring. The main result is that, for sufficiently large X, r(φ) can only take the values 1 or 4.