Maximum Betti Numbers of Čech Complexes

The Upper Bound Theorem for convex polytopes implies that the <i>p</i>-th Betti number of the Čech complex of any set of <i>N</i> points in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup><mml:mrow><mml:mi>R</mml:mi></mml:mrow> <mml:mi>d</mml:mi></mml:msup> </mml:math> and any radius satisfies <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msub><mml:mi>β</mml:mi> <mml:mi>p</mml:mi></mml:msub> <mml:mrow></mml:mrow> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mrow><mml:mo>(</mml:mo> <mml:msup><mml:mi>N</mml:mi> <mml:mi>m</mml:mi></mml:msup> <mml:mo>)</mml:mo></mml:mrow> </mml:mrow> </mml:math> , with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>m</mml:mi> <mml:mo>=</mml:mo> <mml:mo>min</mml:mo> <mml:mo>{</mml:mo> <mml:mi>p</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mrow><mml:mrow><mml:mo>⌈</mml:mo></mml:mrow> <mml:mi>d</mml:mi> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> <mml:mrow><mml:mo>⌉</mml:mo></mml:mrow> </mml:mrow> <mml:mo>}</mml:mo></mml:mrow> </mml:math> . We construct sets in even and odd dimensions that prove this upper bound is asymptotically tight. For example, we describe a set of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo></mml:mrow> </mml:math> points in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup><mml:mrow><mml:mi>R</mml:mi></mml:mrow> <mml:mn>3</mml:mn></mml:msup> </mml:math> and two radii such that the first Betti number of the Čech complex at one radius is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup><mml:mrow><mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo></mml:mrow> <mml:mn>2</mml:mn></mml:msup> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn></mml:mrow> </mml:math> , and the second Betti number of the Čech complex at the other radius is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>n</mml:mi> <mml:mn>2</mml:mn></mml:msup> </mml:math> .