Reconstruction of a coloring from its homogeneous sets
Preprint
Abstract
We study a reconstruction problem for colorings. Given a finite or countable set $X$, a coloring on $X$ is a function $\varphi: [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 $\varphi$ when $\varphi$ is constant on $[H]^2$. Let $hom(\varphi)$ be the collection of all homogeneous sets for $\varphi$. The coloring $1-\varphi$ is called the complement of $\varphi$. We say that $\varphi$ is {\em reconstructible} up to complementation from its homogeneous sets, if for any coloring $\psi$ on $X$ such that $hom(\varphi)=hom(\psi)$ we have that either $\psi=\varphi$ or $\psi=1-\varphi$. 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.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- BASES AND BOREL SELECTORS FOR TALL FAMILIESThe Journal of Symbolic Logic, 2019
- Ramsey type properties of idealsAnnals of Pure and Applied Logic, 2017
- Boolean sum of graphs and reconstruction up to complementationAdvances in Pure and Applied Mathematics, 2013
- Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problemContributions to Discrete Mathematics, 2011
- Classical Descriptive Set Theory1995
- A Theorem on Reconstruction of Random GraphsCombinatorics, Probability and Computing, 1993