{
  "id": "2009.12611",
  "version": "v1",
  "published": "2020-09-26T14:35:25.000Z",
  "updated": "2020-09-26T14:35:25.000Z",
  "title": "Reconstruction of a coloring from its homogeneous sets",
  "authors": [
    "Claribet Piña",
    "Carlos Uzcátegui"
  ],
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-26T14:35:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D10",
      "03E15",
      "05C15"
    ],
    "keywords": [
      "homogeneous sets",
      "reconstruction problem",
      "collection",
      "non reconstructibility",
      "borel way"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}