The Upper Bound Theorem for convex polytopes implies that the p-th Betti number of the Čech complex of any set of N points in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">${{\mathbb R}}^d$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mi>d</mi> </msup> </math></EquationSource> </InlineEquation> and any radius satisfies <InlineEquation ID="IEq2"> <EquationSource Format="TEX">${\beta }_{p}{} = O(N^{m})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>β</mi> <mi>p</mi> </msub> <mrow /> <mo>=</mo> <mi>O</mi> <mrow> <mo stretchy="false">(</mo> <msup> <mi>N</mi> <mi>m</mi> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$m = \min \{ p+1, {\big \lceil d/2 \big \rceil } \}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>=</mo> <mo movablelimits="true">min</mo> <mo stretchy="false">{</mo> <mi>p</mi> <mo>+</mo> <mn>1</mn> <mo>,</mo> <mrow> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">⌈</mo> </mrow> <mi>d</mi> <mo stretchy="false">/</mo> <mn>2</mn> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">⌉</mo> </mrow> </mrow> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. We construct sets in even and odd dimensions that prove this upper bound is asymptotically tight. For example, we describe a set of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$N = 2(n+1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>N</mi> <mo>=</mo> <mn>2</mn> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> points in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">${{\mathbb R}}^3$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mn>3</mn> </msup> </math></EquationSource> </InlineEquation> and two radii such that the first Betti number of the Čech complex at one radius is <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$(n+1)^2 - 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, and the second Betti number of the Čech complex at the other radius is <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$n^2$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>n</mi> <mn>2</mn> </msup> </math></EquationSource> </InlineEquation>.

Maximum Betti Numbers of Čech Complexes

期刊论文
出版模式：

开放获取
发表日期：

2025年11月10日

查看全文

Herbert Edelsbrunner,
János Pach

摘要

The Upper Bound Theorem for convex polytopes implies that the p-th Betti number of the Čech complex of any set of N points in ${{\mathbb R}}^d$ $R^{d}$ and any radius satisfies ${\beta }_{p}{} = O(N^{m})$ $β_{p} = O (N^{m})$ , with $m = \min \{ p+1, {\big \lceil d/2 \big \rceil } \}$ $m = min {p + 1, ⌈ d / 2 ⌉}$ . We construct sets in even and odd dimensions that prove this upper bound is asymptotically tight. For example, we describe a set of $N = 2(n+1)$ $N = 2 (n + 1)$ points in ${{\mathbb R}}^3$ $R^{3}$ and two radii such that the first Betti number of the Čech complex at one radius is $(n+1)^2 - 1$ ${(n + 1)}^{2} - 1$ , and the second Betti number of the Čech complex at the other radius is $n^2$ $n^{2}$ .