2020/09/26 by Piña, Claribet, Uzcátegui, Carlos
#03E15 #Combinatorics (math.CO) #FOS: Mathematics #Primary 05D10 #Secondary 05C15
paper · doi:10.48550/arxiv.2009.12611
We study a reconstruction problem for colorings. Given a finite or countable set X, a coloring on X is a function φ: [X]2→ \0,1\, where [X]2 is the collection of all 2-elements subsets of X. A set H⊆ X is homogeneous for φ when φ is constant on [H]2. Let hom(φ) be the collection of all homogeneous sets for φ. The coloring 1-φ is called the complement of φ. We say that φ is \em reconstructible up to complementation from its homogeneous sets, if for any coloring ψ on X such that hom(φ)=hom(ψ) we have that either ψ=φ or ψ=1-φ. 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.