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

$k$ -横断面に対する $(\aleph_0,k+2)$ 定理

基本情報

論文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）概念の導入：凸性より弱いが依然有用な幾何学的構造を定義し、適用範囲を拡張した。
技術的革新：無限族を扱う新しい方法を開発し、幾何学的投影と位相的コンパクト性を結合した。
最適性結果：定理の鋭さを証明し、定義1.3の両条件が必要であることを示した。
構成的反例：開球族の反例を提供し、コンパクト性仮定の必要性を証明した。

方法の詳細説明

核心的定義

定義1.3（近似球）：集合族 $\mathcal{F}$ が近似球族と呼ばれるのは、定数 $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$ を含む最小球である。

主定理

定理1.4： $\mathbb{R}^d$ 内のコンパクト近似球族 $\mathcal{F}$ と $0 \leq k \leq d-1$ に対して、以下の条件のいずれか正確に一つが成立する：

$\mathcal{F}$ は有限個の $k$ 次元平坦で刺穿できる
$\mathcal{F}$ は無限 $k$ -独立部分列を含む

証明戦略

1. 帰納的構造

帰納基底： $k=0$ の場合（補題3.1）
帰納段階： $(k-1,d-1)$ から $(k,d)$ を導出

2. $k=0$ の場合の証明思路

点の分類方法を使用：

タイプ(a)点：近傍に任意に小さい当該点を含まない球が存在する
タイプ(b)点：その中の球が十分大きいか当該点を含むような近傍が存在する

タイプ(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$ -平坦で刺穿できない