Tverbergの定理

$k=1,\dots,r-1$ では $k< r< 2r-k$ なので $y_k\le y_r\le y_{2r-k}$ であり、$y_r\in[y_k,y_{2r-k}]=\operatorname{conv}\{y_k,y_{2r-k}\}$ である。$y_r\in\operatorname{conv}\{y_r\}$ は明らかである。添字 $1,\dots,2r-1$ はちょうど 1 回ずつ現れる。$\square$

$\sum_{j=1}^rc_jv_j=\sum_{j=1}^{r-1}c_je_j-c_r\sum_{j=1}^{r-1}e_j=\sum_{j=1}^{r-1}(c_j-c_r)e_j$ であり、$e_1,\dots,e_{r-1}$ は線形独立なので、これが $0$ であることは $c_j=c_r$（$j=1,\dots,r-1$）と同値である。$\square$

行列 $\sum_jv_j\otimes y_j=\sum_jv_jy_j^{\mathsf T}$ の第 $k$ 列は $\sum_j(y_j)_k\,v_j$ である（$(y_j)_k$ は $y_j$ の第 $k$ 成分）。これが $0$ なので、lem-tv-vectors により $(y_1)_k=\cdots=(y_r)_k$ である。これがすべての $k=1,\dots,d+1$ で成り立つ。$\square$

2 ならば 1：$0=\sum_i\lambda_i\,v_{c(i)}\otimes\hat x_i$（$\lambda_i\ge0$、$\sum_i\lambda_i=1$）とする。添字を組ごとにまとめ、$v\otimes w$ の $w$ についての線形性を使うと
$$ 0=\sum_{j=1}^r\ \sum_{i\in I_j}\lambda_i\,v_j\otimes\hat x_i=\sum_{j=1}^rv_j\otimes y_j,\qquad y_j:=\sum_{i\in I_j}\lambda_i\hat x_i\in\mathbb{R}^{d+1} $$
となる（$I_j$ が空なら $y_j=0$）。lem-tv-tensor により $y_1=\cdots=y_r$ である。$y_j$ の最後の成分は $\sigma_j:=\sum_{i\in I_j}\lambda_i$ なので $\sigma_1=\cdots=\sigma_r$ であり、その和は $\sum_i\lambda_i=1$ だから、すべて $\dfrac1r$ に等しい。とくに各 $I_j$ は空でない。$y_j$ の最初の $d$ 成分 $\sum_{i\in I_j}\lambda_ix_i$ も $j$ によらないので、$p=r\sum_{i\in I_j}\lambda_ix_i$ は $j$ によらない。係数 $r\lambda_i$（$i\in I_j$）は $0$ 以上で和が $1$ なので、$p\in\operatorname{conv}x_{I_j}$ がすべての $j$ で成り立つ。
1 ならば 2：$p$ を共通部分の点とし、各 $j$ について $p=\sum_{i\in I_j}\alpha_ix_i$（$\alpha_i\ge0$、$\sum_{i\in I_j}\alpha_i=1$）と書く。各 $i$ はちょうど 1 つの $I_j$ に属するので、係数 $\alpha_i$ は $i$ ごとに 1 つ決まる。このとき $\sum_{i\in I_j}\alpha_i\hat x_i=\hat p$ なので
$$ \sum_{i=1}^m\frac{\alpha_i}r\,v_{c(i)}\otimes\hat x_i=\frac1r\sum_{j=1}^rv_j\otimes\hat p=\frac1r\Bigl(\sum_{j=1}^rv_j\Bigr)\otimes\hat p=0 $$
である（$v_1+\cdots+v_r=0$ は lem-tv-vectors で $c_j=1$ とした場合）。係数 $\alpha_i/r$ は $0$ 以上で、和は $r\cdot\frac1r=1$ である。$\square$

rem-tv-reduction により $m=N+1$ としてよい。点を $x_0,x_1,\dots,x_N$ と番号づけ直す。各 $i=0,\dots,N$ について、$M$ の $r$ 個の行列の集合
$$ A_i:=\{\,v_1\otimes\hat x_i,\ v_2\otimes\hat x_i,\ \dots,\ v_r\otimes\hat x_i\,\} $$
を考える。$\frac1r\sum_jv_j\otimes\hat x_i=\frac1r\bigl(\sum_jv_j\bigr)\otimes\hat x_i=0$ なので、原点は $\operatorname{conv}A_i$ に属する。
$M$ は $N$ 次元であり、集合はちょうど $N+1$ 個ある。Carathéodoryの定理(凸幾何) の定理「色つきのCarathéodoryの定理」（$\mathbb{R}^n$ の $n+1$ 個の集合 $S_0,\dots,S_n$ の凸包がすべて点 $x$ を含めば、各 $S_i$ から 1 点ずつ選んでその凸包が $x$ を含むようにできる）を、$n=N$、$S_i=A_i$、$x=0$ として使うと、各 $i$ について $c(i)\in\{1,\dots,r\}$ を選んで、
$$ 0\in\operatorname{conv}\bigl\{\,v_{c(0)}\otimes\hat x_0,\ v_{c(1)}\otimes\hat x_1,\ \dots,\ v_{c(N)}\otimes\hat x_N\,\bigr\} $$
とできる。これは prop-tv-criterion の 2 なので、$I_j:=c^{-1}(j)$ は $r$ 組の Tverberg 分割である。$\square$

$\beta_0(x):=1-(x_1+\cdots+x_d)$、$\beta_k(x):=x_k$（$k=1,\dots,d$）とおく。各 $\beta_k$ は 1 次式に定数を足した関数で、$\beta_k(u_l)$ は $l=k$ なら $1$、$l\ne k$ なら $0$ であり、すべての $x$ で $\sum_{k=0}^d\beta_k(x)=1$ である。凸結合 $\sum_i\mu_iy_i$ について $\beta_k\bigl(\sum_i\mu_iy_i\bigr)=\sum_i\mu_i\beta_k(y_i)$ が成り立つ。

1. Tverberg 分割 $I_1,\dots,I_r$ と Tverberg 点 $p$ があるとする。$k$ を固定すると、$u_k$ の $r-1$ 個の写しは高々 $r-1$ 個の組にしか入らないので、$u_k$ を 1 つも含まない組 $I_j$ がある。その組の点はすべて $l\ne k$ の $u_l$ なので $\beta_k=0$ であり、$p\in\operatorname{conv}x_{I_j}$ から $\beta_k(p)=0$ となる。これがすべての $k$ で成り立つので $\sum_k\beta_k(p)=0$ となり、和が $1$ であることに反する。
2. 点を相異なるようにずらしても、同じ議論が通る。
   2 の詳しい証明を開く

   $\beta_k$ の 1 次の部分の係数は $0$ か $\pm1$ なので、Cauchy–Schwarz の不等式により $\lvert\beta_k(y)-\beta_k(u)\rvert\le\sqrt d\,\| y-u\|$ である。異なる頂点の距離は $1$ 以上で、$\varepsilon< \frac1{(d+1)\sqrt d}\le\frac12$ なので、各 $u_k$ のまわりにとった点は全部で $N$ 個の相異なる点になる。Tverberg 分割と Tverberg 点 $p$ があるとし、1 と同じく、$u_k$ のまわりの点を 1 つも含まない組 $I_j$ をとる。その組の点 $y$ はある $l\ne k$ について $\| y-u_l\|< \varepsilon$ を満たすので $\beta_k(y)< \beta_k(u_l)+\sqrt d\,\varepsilon=\sqrt d\,\varepsilon$ であり、$p$ はそれらの凸結合なので $\beta_k(p)< \sqrt d\,\varepsilon$ となる。$k$ について足すと $1=\sum_k\beta_k(p)< (d+1)\sqrt d\,\varepsilon< 1$ となり、矛盾する。$\square$

$H=\{x\mid a\cdot x\le b\}$（$a\ne0$）が $x_{I_j}$ の点を 1 つも含まなければ、$x_{I_j}$ は開半空間 $G:=\{x\mid a\cdot x>b\}$ に含まれる。$G$ は凸なので $p\in\operatorname{conv}x_{I_j}\subset G$ となり、$p\in H$ に反する。組は互いに交わらないので、各組から 1 つずつとった添字は $r$ 個の相異なる添字である。$\square$

$r:=\bigl\lceil\frac m{d+1}\bigr\rceil$ とおく。$m=0$ なら任意の点 $c$ でよい。$r=1$ なら $1\le m\le d+1$ であり、$c\in S$ を 1 つとれば、$c$ を含む閉半空間は $S$ の点を $1\ge\frac m{d+1}$ 個以上含む。$r\ge2$ なら $r-1< \frac m{d+1}$ から $(r-1)(d+1)< m$、すなわち $m\ge(r-1)(d+1)+1$ なので、$S$ の点に thm-tv-main を使って Tverberg 点 $c$ をとる。prop-tv-depth により、$c$ を含む閉半空間は $S$ の相異なる点を $r\ge\frac m{d+1}$ 個以上含む。$\square$

面 $\sigma_1,\dots,\sigma_r$ は相異なる頂点の集合が張るので、互いに交わらない。辺 $\sigma_k$ 上の連続関数 $g(t):=f\bigl((1-t)w_{(k)}+tw_{(2r-k)}\bigr)$（$0\le t\le1$）は $g(0)=f(w_{(k)})\le f(w_{(r)})\le f(w_{(2r-k)})=g(1)$ を満たすので、中間値の定理 により $g(t)=f(w_{(r)})$ となる $t$ がある。よって $f(w_{(r)})\in f(\sigma_k)$ である。$\sigma_r$ の像は $\{f(w_{(r)})\}$ である。$\square$