【开放问题】超立方体中的极值集

发表于 2023-04-24 更新于 2023-04-25 分类于开放问题

发现了一篇叫做 Real Analysis in Computer Science: A collection of Open Problems 的文献，记录了许多计算机科学视域下的实分析领域的未解之谜。

下面介绍一个文章提到的Boolean functions方向的很好理解的问题——Extremal sets in the hypercube。

记号

为n维超立方体的顶点集，有个顶点，每个顶点由长为的01向量作为坐标。为和超立方体的边组成的图。显然，超立方体的边为所有只在一个维度上坐标不同的点之间的连线。如时，是一条边。

到上的一个嵌入是一个保边映射，即维超立方体的顶点到维超立方体的某个顶点的映射，而且在n维立方体中这些点之间的连边关系仍然与d维中的边相一一对应。

给定，我们称是的，当且仅当每个到的嵌入都满足。对于集族，我们称是的，当且仅当对于每个都是的。

对于任意、和上的，考虑所有的，其中基数最大的那些集合中是否总有对称集？

这个问题所在的领域精准地讲其实叫“极值组合”，类似这样的问题统称为Turan问题。

一句话讲就是：一个图中不允许出现某种结构，那么这个图至多可以有多少条边？

而本题稍稍有一些变化，因为它主要考虑的是点集。因此它属于Vertex Turan问题。

定义：

，称为vertex Turan density。

问题：求上面这两个东西，或者估计它们。我们对它们的了解还很少，主要只能考虑很小或者和很接近的情况。

定义：若，用表示的第个维度的坐标，，

，

。

Kostochka给出了下面这个定理：

若是的且，则对于的自同构以及某个，即。

简单地讲，就是正方形嵌入产生的最大free集只需要把n维超立方体每三层就删掉一层就可以得到。

另外，在上面一部分提到的那个问题（也即最大集是对称集的问题）的肯定结果可以直接推导出一个叫The daisies problem的肯定结果，有兴趣的读者可以自行了解。