Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.08104 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- A coloring on a finite or countable set $X$ is a function $φ: [X]^{2} \to \{0,1\}$, where $[X]^{2}$ is the collection of unordered pairs of $X$. The collection of homogeneous sets for $φ$, denoted by $Hom(φ)$, consist of all $H \subseteq X$ such that $φ$ is constant on $[H]^2$; clearly, $Hom(φ) = Hom(1-φ)$. A coloring $φ$ is \textit{reconstructible} up to complementation from its homogeneous sets if, for any coloring $ψ$ on $X$ such that $Hom(φ) = Hom(ψ)$, either $ψ= φ$ or $ψ= 1-φ$. By $\mathcal{R}$ we denote the collection of all colorings reconstructible from their homogeneous sets. Let $φ$ and $ψ$ be colorings on $X$, and set \[ D(φ, ψ) = \{ \{x,y\} \in [X]^2: \; ψ\{x,y\} \neq φ\{x,y\}\}. \] If $φ\not\in \mathcal{R}$, let \[ r(φ) = \min\{|D(φ, ψ)|: \; Hom(φ) = Hom(ψ), \, ψ\neq φ, \, ψ\neq 1-φ\}. \] A coloring $ψ$ such that $Hom(φ)=Hom(ψ)$, $φ\neq ψ$ and $1-φ\neq ψ$ is called a {\em non trivial reconstruction} of $φ$. If, in addition, $r(φ) =|D(φ, ψ)|$, we call $ψ$ a {\em minimal reconstruction} of $φ$. The purpose of this article is to study the minimal reconstructions of a coloring. We show that, for large enough $X$, $r(φ)$ can only takes the values $1$ or $4$.