<p>We study colorful no-dimensional Tverberg-type problems and obtain several optimal results. A colorful no-dimensional Tverberg-type theorem provides a bound on a radius <i>R</i> such that, for any pairwise disjoint <i>k</i>-element subsets <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(Q_1,\dots ,Q_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>Q</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> of a normed space, there exists a partition of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(Q_1\cup \cdots \cup Q_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>Q</mi> <mn>1</mn> </msub> <mo>∪</mo> <mo>⋯</mo> <mo>∪</mo> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> into disjoint transversals <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\{P_1,\dots ,P_k\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <msub> <mi>P</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>P</mi> <mi>k</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> for which a ball of radius <i>R</i> intersects the convex hull of each <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(P_i\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> (<InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(1\le i\le k\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>≤</mo> <mi>i</mi> <mo>≤</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>). Our methods are deterministic and dimension-free, and they are unified by optimizing two functionals: a quadratic <i>selection</i> functional whose local maximizers produce a complete system of disjoint transversals, and a convex <i>intersection</i> functional that certifies a common point. First, in the Euclidean setting we bound <i>R</i> in terms of the Chebyshev radii (minimal enclosing-ball radii) of the color classes <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(Q_1,\dots ,Q_n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>Q</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>Q</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. A key observation is a “combinatorial” subadditivity of the squared Chebyshev radius: given sequences <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(X=(x_1,\dots ,x_k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>X</mi> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>x</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(Y=(y_1,\dots ,y_k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Y</mi> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>y</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>y</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of points in a Euclidean space, contained in balls of radii <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(R_X\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>R</mi> <mi>X</mi> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(R_Y\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>R</mi> <mi>Y</mi> </msub> </math></EquationSource> </InlineEquation> (not necessarily with the same center), one can reenumerate <i>Y</i> so that the pointwise-sum sequence <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(Z=(x_1+y_1,\dots ,x_k+y_k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Z</mi> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mn>1</mn> </msub> <mo>+</mo> <msub> <mi>y</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>x</mi> <mi>k</mi> </msub> <mo>+</mo> <msub> <mi>y</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is contained in a ball of radius <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(R_Z\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>R</mi> <mi>Z</mi> </msub> </math></EquationSource> </InlineEquation> satisfying <Equation ID="Equ16"> <EquationSource Format="TEX">\( R_Z^2 \le R_X^2 + R_Y^2 . \)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <msubsup> <mi>R</mi> <mi>Z</mi> <mn>2</mn> </msubsup> <mo>≤</mo> <msubsup> <mi>R</mi> <mi>X</mi> <mn>2</mn> </msubsup> <mo>+</mo> <msubsup> <mi>R</mi> <mi>Y</mi> <mn>2</mn> </msubsup> <mo>.</mo> </mrow> </math></EquationSource> </Equation>As a corollary, we obtain the best-possible bound <Equation ID="Equ17"> <EquationSource Format="TEX">\( R \le \frac{1}{\sqrt{2n}}\sqrt{\frac{k-1}{k}}\, \max _{1\le i\le n} \operatorname {diam}(Q_i). \)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mi>R</mi> <mo>≤</mo> <mfrac> <mn>1</mn> <msqrt> <mrow> <mn>2</mn> <mi>n</mi> </mrow> </msqrt> </mfrac> <msqrt> <mfrac> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> <mi>k</mi> </mfrac> </msqrt> <mspace width="0.166667em" /> <munder> <mo movablelimits="true">max</mo> <mrow> <mn>1</mn> <mo>≤</mo> <mi>i</mi> <mo>≤</mo> <mi>n</mi> </mrow> </munder> <mo>diam</mo> <mrow> <mo stretchy="false">(</mo> <msub> <mi>Q</mi> <mi>i</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>.</mo> </mrow> </math></EquationSource> </Equation>Our algorithm returns the desired disjoint transversals in overall time <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\mathcal {O}(nk^3)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <msup> <mi>k</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Second, we develop a complementary approach based on the inter-color diameter and extend the framework to obtain no-dimensional colorful Tverberg-type results in the hyperbolic setting and in Banach spaces.</p>

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

Tight Colorful No-Dimensional Tverberg Theorem

  • Polina Barabanshchikova,
  • Grigory Ivanov,
  • Alexander Polyanskii

摘要

We study colorful no-dimensional Tverberg-type problems and obtain several optimal results. A colorful no-dimensional Tverberg-type theorem provides a bound on a radius R such that, for any pairwise disjoint k-element subsets \(Q_1,\dots ,Q_n\) Q 1 , , Q n of a normed space, there exists a partition of \(Q_1\cup \cdots \cup Q_n\) Q 1 Q n into disjoint transversals \(\{P_1,\dots ,P_k\}\) { P 1 , , P k } for which a ball of radius R intersects the convex hull of each \(P_i\) P i ( \(1\le i\le k\) 1 i k ). Our methods are deterministic and dimension-free, and they are unified by optimizing two functionals: a quadratic selection functional whose local maximizers produce a complete system of disjoint transversals, and a convex intersection functional that certifies a common point. First, in the Euclidean setting we bound R in terms of the Chebyshev radii (minimal enclosing-ball radii) of the color classes \(Q_1,\dots ,Q_n\) Q 1 , , Q n . A key observation is a “combinatorial” subadditivity of the squared Chebyshev radius: given sequences \(X=(x_1,\dots ,x_k)\) X = ( x 1 , , x k ) and \(Y=(y_1,\dots ,y_k)\) Y = ( y 1 , , y k ) of points in a Euclidean space, contained in balls of radii \(R_X\) R X and \(R_Y\) R Y (not necessarily with the same center), one can reenumerate Y so that the pointwise-sum sequence \(Z=(x_1+y_1,\dots ,x_k+y_k)\) Z = ( x 1 + y 1 , , x k + y k ) is contained in a ball of radius \(R_Z\) R Z satisfying \( R_Z^2 \le R_X^2 + R_Y^2 . \) R Z 2 R X 2 + R Y 2 . As a corollary, we obtain the best-possible bound \( R \le \frac{1}{\sqrt{2n}}\sqrt{\frac{k-1}{k}}\, \max _{1\le i\le n} \operatorname {diam}(Q_i). \) R 1 2 n k - 1 k max 1 i n diam ( Q i ) . Our algorithm returns the desired disjoint transversals in overall time \(\mathcal {O}(nk^3)\) O ( n k 3 ) . Second, we develop a complementary approach based on the inter-color diameter and extend the framework to obtain no-dimensional colorful Tverberg-type results in the hyperbolic setting and in Banach spaces.