A coloring on a finite or countable set X is a function \(\varphi : [X]^{2} \rightarrow \{0,1\}\) , where \([X]^{2}\) is the collection of unordered pairs of X. The collection of homogeneous sets for \(\varphi \) , denoted by \(\operatorname {hom}(\varphi )\) , consists of all \(H \subseteq X\) such that \(\varphi \) is constant on \([H]^2\) ; clearly, \(\operatorname {hom}(\varphi ) = \operatorname {hom}(1-\varphi )\) . A coloring \(\varphi \) is reconstructible up to complementation from its homogeneous sets if, for any coloring \(\psi \) on X such that \(\operatorname {hom}(\varphi ) = \operatorname {hom}(\psi )\) , either \(\psi = \varphi \) or \(\psi = 1-\varphi \) . By \(\mathcal {R}\) we denote the collection of all colorings reconstructible from their homogeneous sets. Let \(\varphi \) and \(\psi \) be colorings on X, and set \( D(\varphi , \psi ) = \{ \{x,y\} \in [X]^2: \; \psi \{x,y\} \ne \varphi \{x,y\}\}. \) If \(\varphi \not \in \mathcal {R}\) , let \( r(\varphi ) = \min \{|D(\varphi , \psi )|: \; \operatorname {hom}(\varphi ) = \operatorname {hom}(\psi ), \, \psi \ne \varphi , \, \psi \ne 1-\varphi \}. \) A coloring \(\psi \) such that \(\operatorname {hom}(\varphi )=\operatorname {hom}(\psi )\) , \(\varphi \ne \psi \) and \(1-\varphi \ne \psi \) is called a non trivial reconstruction of \(\varphi \) . If, in addition, \(r(\varphi ) =|D(\varphi , \psi )|\) , we call \(\psi \) a minimal reconstruction of \(\varphi \) . The purpose of this article is to study the minimal reconstructions of a coloring. The main result is that, for sufficiently large X, \(r(\varphi )\) can only take the values 1 or 4.
