Reconstruction of a coloring from its homogeneous sets (Q2680357)

Given a countable set \(X\), an (edge) coloring on \(X\) is a function \(\varphi\) from the set of \(2\)-subsets of \(X\) to the set \(\{0,1\}\). A subset \(H \subseteq X\) of size at least \(3\) is homogeneous for \(\varphi\) if \(\varphi\) is constant on the set of all \(2\)-subsets of \(H\). Denote by \(\mathrm{hom}(\varphi)\) the set of all homogeneous sets for \(\varphi\). A coloring \(\varphi\) on \(X\) is reconstructible if for any coloring \(\psi\) on \(X\) it holds that if \(\mathrm{hom}(\varphi) =\mathrm{hom}(\psi)\), then \(\psi = \varphi\) or \(\psi = 1- \varphi\). In this paper, the authors consider the problem of determining which colorings are reconstructible. They provide several necessary as well as sufficient conditions for the reconstructibility of a coloring. Furthermore, they give many examples of both reconstructible and non-reconstructible colorings and provide several open problems for future work.