论文标题
重建均匀套件的着色
Reconstruction of a coloring from its homogeneous sets
论文作者
论文摘要
我们研究着色的重建问题。给定有限或可计数的$ x $，$ x $上的着色是一个函数$φ：[x]^{2} \ to \ {0,1 \} $，其中$ [x]^{2} $是所有2个elements subsets of $ x $的集合。当$φ$在$ [h]^2 $上是常数时，$ h \ subseteq x $对于$φ$是同质的。令$ hom（φ）$为$φ$的所有同质套件的集合。着色$ 1-φ$称为$φ$的补充。我们说$φ$是{\ em可重建}，直到其均匀套件的补充，如果对于$ x $上的任何着色$ψ$，以便$ x $（φ）= hom（φ）= hom（ψ）$，我们有$ c =φ$或$ $ $ $或$ c $或$ψ= 1-φ$。我们提出了重建性和非重构性的几个条件。我们表明，有一种鲍雷尔（Borel）从其均匀套件中重建着色的方法。
We study a reconstruction problem for colorings. Given a finite or countable set $X$, a coloring on $X$ is a function $φ: [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 $φ$ 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.
