平面点集中的子集选择问题：一般位置、单调性与斜率多样性

《European Journal of Combinatorics》：Subset selection problems in planar point sets

　　

给定满足条件A的有限点集，子集选择问题询问：能够提取出多大满足条件B的子集？这类问题以其固有难度著称，并吸引了广泛的研究。本文在平面点集的三个子集选择问题上取得了进展。设n,s∈?且n≥s，并设P??2是一个由n个点组成的集合，其中至多有s个点共线。 首先，研究人员选择一个处于一般位置（general position）的P的子集，即不包含任意三点共线的子集。该问题由Erd?s在s为常数的情况下提出。对于s非常数的情况，研究人员给出了此类子集最大规模的新下界和上界。特别地，研究表明在最坏情况下，当3≤s≤n1/3时，此类集合的规模至多为O(n5/6+o(1)/√s)；当n1/3≤s≤n时，至多为O(n/s)。 其次，研究人员选择一个单调一般位置（monotone general position）的P的子集，即点从左到右排序且其y坐标非递减或非递增的一般位置子集。研究人员给出了此类子集最大规模的界。特别地，当s=Ω(√n)时，其上界与下界最多相差一个对数因子。 最后，研究人员选择一个具有两两不同斜率（pairwise distinct slopes）的P的子集。该问题最初由Erd?s, Graham, Ruzsa和Taylor在网格上研究。研究表明，对于s=O(√n)，在P中总能找到一个大小为Ω((n/log s)1/3)的此类子集。当s=Θ(√n)时，这与Zhang在网格上给出的下界相匹配。至于上界，研究表明在最坏情况下，当2≤s≤n3/8时，此类子集规模至多为O(√n)；当n3/8≤s=O(√n)时，至多为O((n/s)4/5)。 证明过程使用了广泛的方法，包括关联几何（incidence geometry）、概率方法（probabilistic methods）、超图容器方法（hypergraph container method）和加性组合学（additive combinatorics）。

一、研究背景与动机

子集选择问题是离散几何与极值组合中的一类核心难题。其基本范式是：给定一个满足某种约束条件A的有限点集，问最多能从中选出一个多大的子集，使其满足另一个更强的约束条件B。这类问题因其内在的复杂性而闻名，并常作为机器学习等领域的重要基准任务。本文聚焦于平面点集中的三个经典子集选择问题。

第一个问题是选择一般位置（general position, 无三点共线）的子集。该问题的起源可追溯至著名的“无三点共线问题”（no-three-in-line problem），即在一个n×n整数网格中最多能选出多少个无三点共线的点，该问题已存在超过百年历史且尚未完全解决。Erd?s将其推广至任意满足一定共线性条件的平面点集，定义了函数f(n,s)，表示从任意n个点（至多s点共线）的点集中一定能选出的最大一般位置子集的大小。先前研究在s为常数时给出了f(n,s)的上下界，但对于s随n变化（非恒定）的情况，尤其是中等范围的s，上界仍不精确。

第二个问题是选择单调一般位置（monotone general position）的子集。这是本文引入的一个新变体，要求所选子集不仅无三点共线，而且其点的x坐标与y坐标需呈单调关系（要么同时非减，要么同时非增）。该问题与经典的Erd?s–Szekeres定理密切相关，该定理指出任何实数序列都包含长单调子序列。研究者定义了函数g(n,s)来描述此问题的最优解。

第三个问题是选择两两确定不同斜率（pairwise distinct slopes）的子集。这比一般位置的要求更强，因为任意两点连线的斜率均不相同自然保证了无三点共线。该问题最初由Erd?s, Graham, Ruzsa和Taylor在网格上研究，后经Zhang和Clemen等人改进了下界。研究者将问题推广至一般的平面点集，定义了函数h(n,s)。

开展这些研究的根本动机在于揭示点集几何结构中隐藏的组合规律，理解共线限制如何影响子集的选择可能性，并为长期悬而未决的猜想（如Dudeney关于2n点的猜测）提供新的视角和工具。

二、研究方法与技术

为攻克上述三个问题，研究人员综合运用了多种前沿数学工具：

1. 1.
   超图容器方法（Hypergraph Container Method）：用于推导一般位置子集的上界。该方法由Balogh, Morris, Samotij以及Saxton, Thomason独立发展，能有效刻画稀疏超图中独立集的结构。研究人员通过构造一个平衡过饱和引理（balanced supersaturation result），迭代应用该引理，从而在更宽的参数范围内获得了最优上界。
2. 2.
   概率方法（Probabilistic Methods）：用于构造下界和某些上界构造。例如，在证明单调一般位置子集的下界时，采用了随机选取点集并结合Chernoff界等工具进行概率分析；在证明斜率不同子集的下界时，同样基于随机子集选择，并利用Szemerédi–Trotter定理控制关键参数。
3. 3.
   关联几何（Incidence Geometry）：特别是Szemerédi–Trotter定理，用于估计点与线之间的关联数，这在分析斜率不同子集的下界时起到关键作用。
4. 4.
   加性组合学（Additive Combinatorics）：具体而言，Sidon集理论被用于构造斜率不同子集的第一种上界构造。
5. 5.
   图论与超图着色理论：如Cooper–Mubayi关于稀疏超图色数的引理，以及Hajnal–Szemerédi定理，被用于改进一般位置子集的下界。

三、主要研究结果

• •
  Section 2: 选择一般位置子集：下界
  研究人员证明了命题2（Proposition 2）。通过构造一个辅助的三一致超图（3-uniform hypergraph），其顶点为点集，边为共线三点组。利用Payne–Wood给出的共线三元组数量上界，结合Cooper–Mubayi关于超图色数的引理，研究人员推导出当3 ≤ s ? √(n log n)时，f(n,s) = Ω( √( n log( n log s / s2 ) / log s ) )。特别地，当n^1/2-o(1) ≤ s = O(√(n log log n))时，有f(n,s) = Ω( √( n log log n / log n ) )。这一结果改进了Payne–Wood在该参数范围内的下界。
• •
  Section 3: 选择一般位置子集：上界
  研究人员证明了定理1（Theorem 1），分为两部分：
  • •
    Part (ii)：对于n^1/3 ≤ s ≤ n，通过考虑[n]×[n/s]网格并使用鸽笼原理，得到f(n,s) = O(n/s)。结合已知下界，当s = Ω(√(n log n))时，有f(n,s) = Θ(n/s)。
  • •
    Part (i)：对于3 ≤ s ≤ n^1/3，研究人员创新性地采用了超图容器方法。关键的创新在于提出了一个平衡过饱和引理（Lemma 11），该引理表明，对于三维网格[n]3中任意大小为n^3-x的子集S，存在一个S上的三一致超图H'，其边数很大（约n^6-4x），但最大度适中且最大2-度仅为1。通过在超图容器方法中迭代使用这个稀疏化的H'而非原始的H_S，研究人员成功将上界适用范围从之前的s ≤ n^1/6扩展到s ≤ n^1/3，得到f(n,s) = O(n^5/6+o(1)/√s)。
• •
  Section 4: 选择单调一般位置子集
  研究人员证明了定理4（Theorem 4），给出了g(n,s)的上下界：
  • •
    下界：当3 ≤ s ? √(n log n)时，g(n,s) = Ω( ( n log(n log s / s2) / log s )^1/4 )；当s = Ω(√(n log n))时，g(n,s) = Ω( √(n/s) )。
  • •
    上界：对所有s ≥ 3，g(n,s) = O( √(n/s) )。
    特别地，当s = Ω(√n)时，上下界仅差对数因子；当s = Ω(√(n log n))时，达到紧界g(n,s) = Θ(√(n/s))。
    此外，定理5（Theorem 5）专门针对√n × √n整数网格，给出了单调一般位置子集的下界Ω( (n/log n)^2/5 )和上界o(n^1/2)。下界构造来自一个精心选择的环形扇区与网格交集的随机子集。
• •
  Section 5: 选择两两不同斜率的子集
  研究人员证明了定理6（Theorem 6）：
  • •
    下界：当2 ≤ s = O(√n)时，h(n,s) = Ω( (n / log s)^1/3 )。当s = Θ(√n)时，该下界与Zhang在网格上给出的界匹配。
  • •
    上界：当2 ≤ s ≤ n^3/8时，h(n,s) = O(√n)；当n^3/8 ≤ s = O(√n)时，h(n,s) = O( (n/s)^4/5 )。

四、总结与结论

本文系统研究了平面点集中的三个重要子集选择问题。通过综合运用超图容器方法、概率方法、关联几何和加性组合学等现代工具，研究人员在多个参数范围内显著改进了已有的上下界，填补了非恒定共线限制下的理论空白。特别是，对于一般位置子集问题，通过创新的平衡过饱和引理将超图容器的适用范围扩展到了更广的s值；对于单调一般位置子集问题，首次给出了系统性研究，并在大s时得到了紧界；对于斜率不同子集问题，将问题从网格推广至一般点集，并给出了与网格特例相匹配的通用下界。

研究结论部分翻译：

本文的主要结论如下：

• •
  定理1：f(n,s) = O(n^5/6+o(1)/√s) 当 3 ≤ s ≤ n^1/3，且 f(n,s) = O(n/s) 当 n^1/3 ≤ s ≤ n。特别地，当 s = Ω(√(n log n)) 时，f(n,s) = Θ(n/s)。
• •
  定理4：g(n,s) = Ω( (n log(n log s / s2) / log s)^1/4 ) 当 3 ≤ s ? √(n log n)，且 g(n,s) = Ω(√(n/s)) 当 s = Ω(√(n log n))。另一方面，g(n,s) = O(√(n/s))。
• •
  定理5：对于√n × √n网格G，其最大单调一般位置子集的规模至少为Ω( (n/log n)^2/5 )，至多为o(n^1/2)。
• •
  定理6：当 2 ≤ s = O(√n) 时，h(n,s) = Ω( (n / log s)^1/3 )。另一方面，h(n,s) = O(√n) 当 2 ≤ s ≤ n^3/8，且 h(n,s) = O( (n/s)^4/5 ) 当 n^3/8 ≤ s = O(√n)。