{
  "id": "2403.08104",
  "version": "v1",
  "published": "2024-03-12T22:23:11.000Z",
  "updated": "2024-03-12T22:23:11.000Z",
  "title": "Minimal reconstructions of a coloring",
  "authors": [
    "Diego Gamboa",
    "Carlos Uzcategui-Aylwin"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A coloring on a finite or countable set $X$ is a function $\\varphi: [X]^{2} \\to \\{0,1\\}$, where $[X]^{2}$ is the collection of unordered pairs of $X$. The collection of homogeneous sets for $\\varphi$, denoted by $Hom(\\varphi)$, consist of all $H \\subseteq X$ such that $\\varphi$ is constant on $[H]^2$; clearly, $Hom(\\varphi) = Hom(1-\\varphi)$. A coloring $\\varphi$ is \\textit{reconstructible} up to complementation from its homogeneous sets if, for any coloring $\\psi$ on $X$ such that $Hom(\\varphi) = Hom(\\psi)$, either $\\psi = \\varphi$ or $\\psi = 1-\\varphi$. By $\\mathcal{R}$ we denote the collection of all colorings reconstructible from their homogeneous sets. Let $\\varphi$ and $\\psi$ be colorings on $X$, and set \\[ D(\\varphi, \\psi) = \\{ \\{x,y\\} \\in [X]^2: \\; \\psi\\{x,y\\} \\neq \\varphi\\{x,y\\}\\}. \\] If $\\varphi\\not\\in \\mathcal{R}$, let \\[ r(\\varphi) = \\min\\{|D(\\varphi, \\psi)|: \\; Hom(\\varphi) = Hom(\\psi), \\, \\psi \\neq \\varphi, \\, \\psi \\neq 1-\\varphi\\}. \\] A coloring $\\psi$ such that $Hom(\\varphi)=Hom(\\psi)$, $\\varphi\\neq \\psi$ and $1-\\varphi\\neq \\psi$ is called a {\\em non trivial reconstruction} of $\\varphi$. If, in addition, $r(\\varphi) =|D(\\varphi, \\psi)|$, we call $\\psi$ a {\\em minimal reconstruction} of $\\varphi$. The purpose of this article is to study the minimal reconstructions of a coloring. We show that, for large enough $X$, $r(\\varphi)$ can only takes the values $1$ or $4$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-03-12T22:23:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D10",
      "05C15"
    ],
    "keywords": [
      "minimal reconstruction",
      "homogeneous sets",
      "collection",
      "non trivial reconstruction",
      "countable set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}