2025-11-18T17:58:13.913048

An $(\aleph_0,k+2)$-Theorem for $k$-Transversals

Keller, Perles

A family $\mathcal{F}$ of sets satisfies the $(p,q)$-property if among every $p$ members of $\mathcal{F}$, some $q$ can be pierced by a single point. The celebrated $(p,q)$-theorem of Alon and Kleitman asserts that for any $p \geq q \geq d+1$, any family $\mathcal{F}$ of compact convex sets in $\mathbb{R}^d$ that satisfies the $(p,q)$-property can be pierced by a finite number $c(p,q,d)$ of points. A similar theorem with respect to piercing by $(d-1)$-dimensional flats, called $(d-1)$-transversals, was obtained by Alon and Kalai. In this paper we prove the following result, which can be viewed as an $(\aleph_0,k+2)$-theorem with respect to $k$-transversals: Let $\mathcal{F}$ be an infinite family of closed balls in $\mathbb{R}^d$, and let $0 \leq k < d$. If among every $\aleph_0$ elements of $\mathcal{F}$, some $k+2$ can be pierced by a $k$-dimensional flat, then $\mathcal{F}$ can be pierced by a finite number of $k$-dimensional flats. We derive this result as a corollary of a more general result which proves the same assertion for families of not necessarily convex objects called \emph{near-balls}, to be defined below. This is the first $(p,q)$-theorem in which the assumption is weakened to an $(\infty,\cdot)$ assumption. Our proofs combine geometric and topological tools.

academic

An $(\aleph_0,k+2)$ -Theorem for $k$ -Transversals

基本信息

论文ID: 2306.02181
标题: An $(\aleph_0,k+2)$ -Theorem for $k$ -Transversals
作者: Chaya Keller (Ariel University), Micha A. Perles (Hebrew University)
分类: math.CO cs.CG
发表时间: 2025年10月17日 (arXiv版本)
会议: 初步版本发表于SoCG 2022会议
论文链接: https://arxiv.org/abs/2306.02181

摘要

本文研究了经典 $(p,q)$ 定理的无穷版本。对于集合族 $\mathcal{F}$ ，如果其中任意 $p$ 个成员中总有 $q$ 个可以被单点刺穿，则称 $\mathcal{F}$ 满足 $(p,q)$ 性质。著名的Alon-Kleitman $(p,q)$ 定理断言，对于 $\mathbb{R}^d$ 中满足 $(p,q)$ 性质的紧凸集族，当 $p \geq q \geq d+1$ 时，可以用有限个点刺穿整个族。本文证明了一个 $(\aleph_0,k+2)$ 定理：对于 $\mathbb{R}^d$ 中的无穷闭球族 $\mathcal{F}$ ，如果任意 $\aleph_0$ 个元素中总有 $k+2$ 个可以被 $k$ 维平坦刺穿，则整个族可以被有限个 $k$ 维平坦刺穿。这是首个将假设弱化为 $(\infty,\cdot)$ 形式的 $(p,q)$ 定理。

研究背景与动机

问题背景

Helly定理的推广：经典Helly定理表明， $\mathbb{R}^d$ 中紧凸集族如果任意 $d+1$ 个成员有非空交集，则整个族有非空交集。 $(p,q)$ 定理是其重要推广。
$k$ -横截问题：研究用 $k$ 维平坦（ $k$ 维仿射子空间）刺穿集合族的问题。已知对于一般凸集，当 $1 \leq k \leq d-2$ 时不存在 $(p,q)$ 定理。
无穷族的挑战：现有 $(p,q)$ 定理主要针对有限族，对无穷族的研究较少，需要更强的拓扑假设。

研究动机

理论意义：探索是否可以将 $(p,q)$ 性质弱化为 $(\aleph_0,q)$ 性质，即从有限性条件推广到可数无穷条件。
技术挑战：无穷族无法直接应用紧致性论证，需要结合几何和拓扑工具。
应用价值：为计算几何中的横截问题提供新的理论框架。

核心贡献

首个 $(\aleph_0,q)$ 定理：证明了第一个将假设弱化为无穷形式的 $(p,q)$ 定理。
引入near-balls概念：定义了比凸性更弱但仍有用的几何结构，扩展了适用范围。
技术创新：开发了处理无穷族的新方法，结合几何投影和拓扑紧致性。
最优性结果：证明了定理的尖锐性，both conditions of Definition 1.3都是必需的。
构造性反例：给出了开球族的反例，证明紧致性假设的必要性。

方法详解

核心定义

Definition 1.3 (Near-balls)：集合族 $\mathcal{F}$ 称为near-balls族，如果存在常数 $K = K(\mathcal{F})$ 使得对任意 $B \in \mathcal{F}$ ：

$r(\text{escribed}(B)) \leq K \cdot r(\text{inscr}(B))$
$r(\text{escribed}(B)) \leq K + r(\text{inscr}(B))$

其中 $\text{inscr}(B)$ 是 $B$ 的最大内切球， $\text{escribed}(B)$ 是以 $\text{inscr}(B)$ 中心为圆心包含 $B$ 的最小球。

主要定理

Theorem 1.4：对于 $\mathbb{R}^d$ 中紧致near-balls族 $\mathcal{F}$ 和 $0 \leq k \leq d-1$ ，恰好满足以下条件之一：

$\mathcal{F}$ 可以被有限个 $k$ 维平坦刺穿
$\mathcal{F}$ 包含无穷 $k$ -独立子序列

证明策略

1. 归纳结构

归纳基础： $k=0$ 情形（Lemma 3.1）
归纳步骤：从 $(k-1,d-1)$ 推导 $(k,d)$

2. $k=0$ 情形的证明思路

使用点的分类方法：

Type (a) 点：附近有任意小的不包含该点的球
Type (b) 点：存在邻域使得其中的球要么足够大要么包含该点

如果存在Type (a)点，则可构造无穷两两不交球序列；否则可用有限个点刺穿。

3. 归纳步骤的关键技术

强点和弱点分类：

弱点 $x$ ：存在 $\epsilon > 0$ 使得 $\{B \in \mathcal{F} : x_B \in B°(x,\epsilon)\}$ 可被有限个 $k$ -平坦刺穿
强点 $x$ ：对任意 $\epsilon > 0$ ， $\{B \in \mathcal{F} : x_B \in B°(x,\epsilon)\}$ 不可被有限个 $k$ -平坦刺穿