<p>A <i>convex lattice set</i> in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathbb {Z}^d\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">Z</mi> </mrow> <mi>d</mi> </msup> </math></EquationSource> </InlineEquation> is the intersection of a convex set in <InlineEquation ID="IEq2"> <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> with the integer lattice <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\mathbb {Z}^d\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mi mathvariant="double-struck">Z</mi> </mrow> <mi>d</mi> </msup> </math></EquationSource> </InlineEquation>. A classical theorem of Doignon states that the <i>Helly number</i> of <i>d</i>-dimensional convex lattice sets equals <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(2^d\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mi>d</mi> </msup> </math></EquationSource> </InlineEquation>, exponentially larger than the Helly number <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(d+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> of ordinary convex sets in <InlineEquation ID="IEq6"> <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>. By contrast, a remarkable theorem of Bárány and Matoušek states that the <i>fractional Helly number</i> of convex lattice sets drops back down to <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(d+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, matching the classical fractional Helly theorem of Katchalski and Liu. In this paper we generalize the Bárány–Matoušek theorem to abstract convexity spaces (in the sense of van de Vel) that satisfy a suitable separation axiom. Our main result implies the following: if a separable convexity space has Radon number at most <i>r</i>, then its fractional Helly number is at most <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(2^{r}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mi>r</mi> </msup> </math></EquationSource> </InlineEquation>. This bound is nearly tight, as illustrated by the case of <i>box convexity</i> in <InlineEquation ID="IEq9"> <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>, whose Radon number is <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\Theta (\log d)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>d</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and fractional Helly number equals <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(d+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The fractional Helly number for separable convexity spaces

  • Andreas F. Holmsen,
  • Zuzana Patáková

摘要

A convex lattice set in \(\mathbb {Z}^d\) Z d is the intersection of a convex set in \(\mathbb {R}^d\) R d with the integer lattice \(\mathbb {Z}^d\) Z d . A classical theorem of Doignon states that the Helly number of d-dimensional convex lattice sets equals \(2^d\) 2 d , exponentially larger than the Helly number \(d+1\) d + 1 of ordinary convex sets in \(\mathbb {R}^d\) R d . By contrast, a remarkable theorem of Bárány and Matoušek states that the fractional Helly number of convex lattice sets drops back down to \(d+1\) d + 1 , matching the classical fractional Helly theorem of Katchalski and Liu. In this paper we generalize the Bárány–Matoušek theorem to abstract convexity spaces (in the sense of van de Vel) that satisfy a suitable separation axiom. Our main result implies the following: if a separable convexity space has Radon number at most r, then its fractional Helly number is at most \(2^{r}\) 2 r . This bound is nearly tight, as illustrated by the case of box convexity in \(\mathbb {R}^d\) R d , whose Radon number is \(\Theta (\log d)\) Θ ( log d ) and fractional Helly number equals \(d+1\) d + 1 .