Reconstruction of a coloring from its homogeneous sets

Abstract

We study a reconstruction problem for colorings. Given a finite or countable set $X$, a coloring on $X$ is a function $\phi :[X{]}^2\to \{0,1\}$, where $[X{]}^2$ is the collection of all 2-elements subsets of $X$. A set $H\subseteq X$ is homogeneous for $\phi$ when $\phi$ is constant on $[H{]}^2$. Let $hom(\phi )$ be the collection of all homogeneous sets for $\phi$. The coloring $1-\phi$ is called the complement of $\phi$. We say that $\phi$ is {\em reconstructible} up to complementation from its homogeneous sets, if for any coloring $\psi$ on $X$ such that $hom(\phi )=hom(\psi )$ we have that either $\psi =\phi$ or $\psi =1-\phi$. We present several conditions for reconstructibility and non reconstructibility. We show that there is a Borel way to reconstruct a coloring from its homogeneous sets.