凸集合
概要
凸集合（convex set）とは、$\mathbb{R}^n$ などの実ベクトル空間の部分集合で、その任意の 2 点を結ぶ線分を含むもののことである。円板・三角形・半平面・直線は凸集合であり、円環や星形は凸集合でない。凸集合の共通部分は凸であり、集合 $S$ を含む最小の凸集合（凸包）は $S$ の点の凸結合の全体に等しい。$\mathbb{R}^n$ では Carathéodory の定理・Radon の定理・Helly の定理が成り立ち、そこに現れる数 $n+1$、$n+2$ はどれも減らせない。
数直線上の 3 つの閉区間 $[0,3]$、$[1,4]$、$[2,5]$ を考える。どの 2 つも重なっている（共通部分は $[1,3]$、$[2,3]$、$[2,4]$）。そして 3 つ全部にも共通部分 $[2,3]$ がある。実は、数直線上の区間を有限個とると、どの 2 つも交わるなら全部に共通な点がある。平面では「どの 2 つも」を「どの 3 つも」に変えれば、同じことが三角形・円板・多角形など「へこみのない」図形の有限個の組について成り立つ。これが Helly の定理 である。平面の 4 点 $(0,0)$、$(4,0)$、$(0,4)$、$(1,1)$ では、$(1,1)$ が残りの 3 点の作る三角形の内部にあるので、4 点を $\{(1,1)\}$ と $\{(0,0),(4,0),(0,4)\}$ に分けると、両者を囲む最小の「へこみのない」図形（点 $(1,1)$ と三角形）が交わる。平面のどの 4 点でもこのような分け方ができる、というのが Radon の定理 である。
ここで「へこみのない」図形とは、図形の中のどの 2 点を結ぶ線分も図形からはみ出さないものであり、これを 凸集合 という。円板・三角形・正方形・半平面・直線は凸集合であり、円環（ドーナツ形）や星形・三日月形は凸集合でない。凸集合は幾何学・線形計画法・最適化・関数解析の基本的な対象であり、Minkowskiの凸体定理のように整数論にも現れる。本記事では凸集合の定義と基本性質、凸包の記述を述べ、組合せ幾何の 3 つの基本定理（Carathéodory・Radon・Helly の定理）を完全に証明する。
定義
以下 $\mathbb{R}^n$ は $n$ 次元 Euclid空間 とし、その元を点ともベクトルとも呼ぶ。2 点 $x,y\in\mathbb{R}^n$ を結ぶ 線分 を
$$
[x,y]:=\{(1-t)x+ty\mid 0\le t\le1\}
$$
と書く。$t=0$ で $x$、$t=1$ で $y$、$t=\frac12$ で中点になる。$n=1$ で $x\le y$ なら、これは閉区間 $[x,y]$ そのものである。
$C\subset\mathbb{R}^n$ が 凸（convex）であるとは、任意の $x,y\in C$ と $0\le t\le1$ について $(1-t)x+ty\in C$ であること、すなわち $C$ の任意の 2 点を結ぶ線分が $C$ に含まれることをいう。凸な集合を 凸集合（convex set）という。
条件は $C$ の 2 点についての主張なので、空集合と 1 点集合は凸集合である。定義は $\mathbb{R}^n$ の構造のうち「和と実数倍」しか使っていないので、任意の実ベクトル空間の部分集合についても同じ定義ができ、以下の性質の多くは（次元を使う Carathéodory・Radon・Helly の定理を除いて）そのまま成り立つ。この定義は BV04 §2.1.4（p. 23）や Minkowskiの凸体定理 の記事の定義「原点対称な凸集合」と同じである。
有限個の点 $x_1,\dots,x_m$ の 凸結合（convex combination）とは、
$$
\lambda_1x_1+\cdots+\lambda_mx_m,\qquad \lambda_i\ge0,\quad \lambda_1+\cdots+\lambda_m=1
$$
の形の点をいう。$m=2$ の凸結合 $\lambda_1x_1+\lambda_2x_2=(1-t)x_1+tx_2$（$t=\lambda_2$）はちょうど線分 $[x_1,x_2]$ の点である。
$S\subset\mathbb{R}^n$ を含むすべての凸集合の共通部分を $S$ の 凸包（convex hull）といい、$\operatorname{conv}S$ と書く。
prop-convex-intersection により $\operatorname{conv}S$ は凸集合であり、$S$ を含む凸集合のうち包含について最小のものである。$\operatorname{conv}S$ を「$S$ の点の凸結合の全体」として具体的に記述するのが thm-convex-hull-combinations である。
直感
凸集合は、「中のどの 2 点の間も、外に出ずにまっすぐ行き来できる」集合である。$S$ の凸包は、$S$ を輪ゴムで囲んだ（空間なら風呂敷で包んだ）ときにできる図形と思えばよい。平面の有限個の点の凸包は、それらを頂点の候補とする凸多角形になる。
凸性は「線分」という 1 次元の概念だけで定義されるので、凸集合を 1 本の直線で切った切り口は、つねに直線上の凸集合、すなわち区間である。凸集合の議論の多くは、この「どの方向に切っても途切れない」性質から出てくる。一方、凸集合の組合せ的な性質（どの点が何点の凸結合で書けるか、いくつの凸集合が交わるか）には、空間の次元 $n$ が $n+1$ や $n+2$ という数として現れる。これは $\mathbb{R}^n$ の $n+2$ 個の点がつねに「アフィン従属」になる（lem-convex-affine-dependence）ことによる。
例と反例
- 球：中心 $c$、半径 $r>0$ の開球 $B=\{x\mid\|x-c\|< r\}$ は凸である。$x,y\in B$、$0\le t\le1$ なら、三角不等式により
$$ \|(1-t)x+ty-c\|=\|(1-t)(x-c)+t(y-c)\|\le(1-t)\|x-c\|+t\|y-c\|<(1-t)r+tr=r $$
となるからである。閉球 $\{x\mid\|x-c\|\le r\}$ も同じ計算で凸である。ここで $\|\cdot\|$ は通常の長さでも、任意のノルムでもよい。 - 半空間と超平面：$a\in\mathbb{R}^n$、$b\in\mathbb{R}$ について $\{x\mid a\cdot x\le b\}$ は凸である。$a\cdot x\le b$、$a\cdot y\le b$ なら $a\cdot((1-t)x+ty)=(1-t)a\cdot x+t\,a\cdot y\le b$ だからである。$<$、$=$ に変えても同じで、とくに直線・平面・超平面は凸である。
- 連立 1 次不等式の解：有限個の半空間の共通部分（連立 1 次不等式の解の集合）は、prop-convex-intersection により凸である。たとえば正方形 $[0,1]^2$ は 4 つの半平面 $x_1\ge0$、$x_1\le1$、$x_2\ge0$、$x_2\le1$ の共通部分であり、三角形 $\Delta_2$（thm-convex-hull-combinations の後で定義する）は $x_1\ge0$、$x_2\ge0$、$x_1+x_2\le1$ の共通部分である。
- 1 次元：$\mathbb{R}$ の凸集合はちょうど区間である（区間 の記事の定理「区間の特徴づけ」の条件 2 は凸性そのものである）。
- 円環：$A=\{x\in\mathbb{R}^2\mid 1\le\|x\|\le2\}$ は凸でない。$(-1.5,0)$ と $(1.5,0)$ は $A$ に属するが、その中点 $(0,0)$ は属さない。
- 2 つの円板の和：交わらない 2 つの閉円板の和は、たとえば中心どうしを結ぶ線分が途中で両方の円板の外に出るので凸でない。凸集合の和は一般に凸でない。
- 星形：原点を中心とする五芒星の形の領域（輪郭とその内部）は、隣り合う 2 つの先端を結ぶ線分が 2 つの先端の間のへこみの外側を通るので凸でない。ただし中心の原点と星形の任意の点を結ぶ線分は星形に含まれる。このように「特定の 1 点からはどの点も見通せる」集合を 星状集合 といい、凸集合は「どの点からもすべての点が見通せる」星状集合である。
- 球面：単位円周 $\{x\in\mathbb{R}^2\mid\|x\|=1\}$ は、$(1,0)$ と $(-1,0)$ の中点 $(0,0)$ を含まないので凸でない。
どの例も「2 点を結ぶ線分が集合に含まれる」という条件を、具体的な 2 点で破っている。とくに 1 は、有界閉集合で弧状連結（弧状連結空間）であっても凸とは限らないことを示している。
性質
凸性を保つ操作
凸集合の任意の族 $(C_\lambda)_{\lambda\in\Lambda}$ の共通部分 $\bigcap_\lambda C_\lambda$ は凸集合である。
$x,y\in\bigcap_\lambda C_\lambda$、$0\le t\le1$ とする。各 $\lambda$ について $x,y\in C_\lambda$ で $C_\lambda$ は凸なので $(1-t)x+ty\in C_\lambda$ である。よって $(1-t)x+ty\in\bigcap_\lambda C_\lambda$ である。$\square$
和集合は凸とは限らない（ex-convex-non-examples の 2）が、増大列 $C_1\subset C_2\subset\cdots$ の和は凸である（2 点はある同じ $C_k$ に入るから）。
$f\colon\mathbb{R}^n\to\mathbb{R}^m$ を $f(x)=Ax+b$（$A$ は $m\times n$ 行列、$b\in\mathbb{R}^m$）の形の写像とする。$C\subset\mathbb{R}^n$ が凸なら像 $f(C)$ は凸であり、$D\subset\mathbb{R}^m$ が凸なら逆像 $f^{-1}(D)$ は凸である。
$f((1-t)x+ty)=A((1-t)x+ty)+(1-t)b+tb=(1-t)f(x)+tf(y)$ である。像について：$f(x),f(y)\in f(C)$（$x,y\in C$）なら $(1-t)f(x)+tf(y)=f((1-t)x+ty)\in f(C)$ である。逆像について：$x,y\in f^{-1}(D)$ なら $f((1-t)x+ty)=(1-t)f(x)+tf(y)\in D$ である。$\square$
たとえば、凸集合の平行移動・拡大縮小・回転、座標への射影は凸であり、2 つの凸集合の直積 $C\times D\subset\mathbb{R}^{n+m}$ や和 $C+D=\{x+y\mid x\in C,\ y\in D\}$ も凸である（後者は凸集合 $C\times D$ の線形写像 $(x,y)\mapsto x+y$ による像）。
凸包と凸結合
$C\subset\mathbb{R}^n$ が凸であることと、$C$ の任意の有限個の点の任意の凸結合が $C$ に属することは同値である。
凸結合で閉じていれば、$m=2$ の場合として凸である。逆に $C$ が凸とし、$C$ の $m$ 点の凸結合が $C$ に属することを $m$ についての数学的帰納法で示す。$m=1$ では $\lambda_1=1$ で点そのものである。$m\ge2$ とし、$x=\lambda_1x_1+\cdots+\lambda_mx_m$（$\lambda_i\ge0$、$\sum\lambda_i=1$、$x_i\in C$）とする。$\lambda_m=1$ なら $x=x_m\in C$ である。$\lambda_m<1$ なら $s:=1-\lambda_m=\lambda_1+\cdots+\lambda_{m-1}>0$ とおくと
$$
x=s\,y+\lambda_mx_m,\qquad y:=\frac{\lambda_1}{s}x_1+\cdots+\frac{\lambda_{m-1}}{s}x_{m-1}
$$
であり、$y$ は $m-1$ 点の凸結合（係数は非負で和は $1$）なので、帰納法の仮定により $y\in C$ である。$s+\lambda_m=1$ なので $x$ は $y$ と $x_m$ を結ぶ線分上にあり、$C$ の凸性により $x\in C$ である。$\square$
$S\subset\mathbb{R}^n$ の凸包 $\operatorname{conv}S$ は、$S$ の有限個の点の凸結合全体の集合に等しい。
$S$ の点の凸結合全体を $K$ とおく。
$K\subset\operatorname{conv}S$：$S$ を含む任意の凸集合 $C$ は、prop-convex-combinations-closed により $S$ の点の凸結合をすべて含むので $K\subset C$ である。$C$ について共通部分をとって $K\subset\operatorname{conv}S$ を得る。
$\operatorname{conv}S\subset K$：$K$ は $S$ を含む（$x\in S$ は $1\cdot x$）。$K$ が凸であることを示せば、凸包の最小性から $\operatorname{conv}S\subset K$ となる。$x=\sum_{i}\lambda_ix_i$、$y=\sum_{j}\mu_jy_j$ を $S$ の点の凸結合、$0\le t\le1$ とする。
$$
(1-t)x+ty=\sum_i(1-t)\lambda_i\,x_i+\sum_j t\mu_j\,y_j
$$
の係数はすべて非負で、和は $(1-t)\cdot1+t\cdot1=1$ である（同じ点が $x_i$ と $y_j$ の両方に現れれば係数をまとめる）。よってこれも $S$ の点の凸結合であり、$K$ は凸である。$\square$
BV04 §2.1.4（p. 24）は、凸包を凸結合の全体として定義し、それが元の集合を含む最小の凸集合であることを述べている。とくに有限集合 $\{x_1,\dots,x_m\}$ の凸包は $\{\sum\lambda_ix_i\mid\lambda_i\ge0,\ \sum\lambda_i=1\}$ であり、これを 凸多面体（ポリトープ）という。$\mathbb{R}^n$ の $n+1$ 点 $0,e_1,\dots,e_n$（$e_i$ は標準基底）の凸包
$$
\Delta_n:=\{x\in\mathbb{R}^n\mid x_1,\dots,x_n\ge0,\ x_1+\cdots+x_n\le1\}
$$
は $n$ 次元の 単体 であり、$n=2$ で三角形、$n=3$ で四面体である（$x=\sum_{i}x_ie_i+(1-\sum_ix_i)\cdot0$ と書けることから確かめられる）。
位相的な性質
空でない凸集合 $C$ は弧状連結である。$x,y\in C$ に対し $\gamma(t)=(1-t)x+ty$ が $x$ と $y$ を結ぶ $C$ 内の道になるからである（弧状連結空間 の記事の例「凸集合と球面」）。さらに、点 $c\in C$ を固定して $H(x,s)=(1-s)x+sc$ とおくと、$C$ を $c$ に縮めるホモトピーが得られるので、空でない凸集合は可縮空間である。この 2 つの性質は凸性より弱い。ex-convex-non-examples の 3 の星形は凸でないが、同じ式（$c$ を中心にとる）で可縮であり、1 の円環は凸でないが弧状連結である。
凸集合の閉包と内部はまた凸である。閉包について示すと、$x,y\in\overline C$ なら $C$ の点列 $x_k\to x$、$y_k\to y$ がとれ、$(1-t)x_k+ty_k\in C$ が $(1-t)x+ty$ に収束するので、$(1-t)x+ty\in\overline C$ である。内部について示すと、$x,y$ が $C$ の内点なら、ある $r>0$ について $\|v\|< r$ のすべての $v$ で $x+v,\ y+v\in C$ となり、$z:=(1-t)x+ty$ について $z+v=(1-t)(x+v)+t(y+v)\in C$ なので、$z$ も内点である。
組合せ幾何の 3 つの定理
以下の 3 つの定理では、空間の次元 $n$ が本質的に効く。その源は次の補題である。
$m\ge n+2$ とし、$x_1,\dots,x_m\in\mathbb{R}^n$（重複があってもよい）とする。このとき、すべては $0$ でない実数 $\mu_1,\dots,\mu_m$ で
$$
\mu_1x_1+\cdots+\mu_mx_m=0,\qquad \mu_1+\cdots+\mu_m=0
$$
を満たすものが存在する。とくに、ある $\mu_i$ は正で、ある $\mu_j$ は負である。
$\mathbb{R}^{n+1}$ のベクトル $\hat x_i:=(x_i,1)$（$x_i$ の座標の後に $1$ を付け加えたもの）を考える。$n+1$ 次元の空間の $m\ge n+2$ 個のベクトルは線形独立でない（基底と次元）ので、すべては $0$ でない $\mu_i$ で $\sum_i\mu_i\hat x_i=0$ となるものがある。この等式の最初の $n$ 成分が $\sum_i\mu_ix_i=0$、最後の成分が $\sum_i\mu_i=0$ である。$\mu_i$ は全部が $0$ ではなく和が $0$ なので、正のものと負のものがともにある。$\square$
$S\subset\mathbb{R}^n$ とする。$\operatorname{conv}S$ の任意の点は、$S$ の高々 $n+1$ 個の点の凸結合として書ける。
$x\in\operatorname{conv}S$ とする。thm-convex-hull-combinations により $x$ は $S$ の有限個の点の凸結合で書ける。そのような表し方のうち点の個数 $m$ が最小のものを $x=\sum_{i=1}^m\lambda_ix_i$ とする。$m$ の最小性から、$x_i$ は相異なり、すべての $\lambda_i$ は正である（$\lambda_i=0$ の項は除けるから）。
$m\ge n+2$ と仮定して矛盾を導く。lem-convex-affine-dependence の $\mu_i$ をとり、
$$
\tau:=\min\Bigl\{\frac{\lambda_i}{\mu_i}\Bigm|\mu_i>0\Bigr\}
$$
とおく。$\tau>0$ であり、最小値をとる添字を $k$ とする。$\lambda_i':=\lambda_i-\tau\mu_i$ とおくと、$\mu_i\le0$ なら $\lambda_i'\ge\lambda_i>0$、$\mu_i>0$ なら $\tau$ の定め方から $\lambda_i'\ge0$ であり、$\lambda_k'=0$ である。さらに
$$
\sum_i\lambda_i'=\sum_i\lambda_i-\tau\sum_i\mu_i=1,\qquad \sum_i\lambda_i'x_i=\sum_i\lambda_ix_i-\tau\sum_i\mu_ix_i=x
$$
なので、$x$ は $k$ 番目を除いた $m-1$ 個の点の凸結合として書ける。これは $m$ の最小性に反する。よって $m\le n+1$ である。$\square$
平面（$n=2$）で、三角形 $\Delta_2$ の重心 $g=\bigl(\tfrac13,\tfrac13\bigr)$ は、頂点 $0,e_1,e_2$ の凸結合 $\tfrac13\cdot0+\tfrac13e_1+\tfrac13e_2$ で書ける。しかし 2 頂点の凸結合、すなわち 3 辺 $\{x_2=0\}$、$\{x_1=0\}$、$\{x_1+x_2=1\}$ 上の点ではない（$\tfrac13\ne0$、$\tfrac13+\tfrac13\ne1$）。したがって $S=\{0,e_1,e_2\}$ について、thm-convex-caratheodory の数 $n+1=3$ は $2$ に減らせない。一般の $n$ でも、単体 $\Delta_n$ の重心は $n$ 個以下の頂点の凸結合では書けない（$n$ 個以下の頂点の凸結合は、座標の 1 つが $0$ になるか座標の和が $1$ になる）。
$m\ge n+2$ とし、$x_1,\dots,x_m\in\mathbb{R}^n$ とする。このとき添字の集合 $\{1,\dots,m\}$ を、交わらない空でない 2 つの部分 $I,J$ に分けて
$$
\operatorname{conv}\{x_i\mid i\in I\}\cap\operatorname{conv}\{x_j\mid j\in J\}\ne\emptyset
$$
とできる。
lem-convex-affine-dependence の $\mu_i$ をとり、$I:=\{i\mid\mu_i>0\}$、$J:=\{j\mid\mu_j\le0\}$ とおく。補題により $I,J$ はともに空でなく、交わらず、合わせて全体である。$\sum_i\mu_i=0$ より $s:=\sum_{i\in I}\mu_i=\sum_{j\in J}(-\mu_j)>0$ であり、$\sum_i\mu_ix_i=0$ を移項して $s$ で割ると
$$
p:=\sum_{i\in I}\frac{\mu_i}{s}\,x_i=\sum_{j\in J}\frac{-\mu_j}{s}\,x_j
$$
を得る。左辺の係数は正で和が $1$、右辺の係数は $0$ 以上で和が $1$ なので、$p$ は両方の凸包に属する。$\square$
Radon の定理で得られる分け方を Radon 分割、共通の点 $p$ を Radon 点 という。冒頭の 4 点では $(1,1)=\tfrac12(0,0)+\tfrac14(4,0)+\tfrac14(0,4)$ であり、$I=\{(1,1)\}$、$J$ を残りの 3 点とする分け方が Radon 分割である。正方形の 4 頂点 $(0,0),(1,0),(1,1),(0,1)$ では、2 本の対角線が $\bigl(\tfrac12,\tfrac12\bigr)$ で交わるので、$\{(0,0),(1,1)\}$ と $\{(1,0),(0,1)\}$ が Radon 分割である。
$\mathbb{R}^n$ の $n+1$ 点 $0,e_1,\dots,e_n$ は Radon 分割をもたない。実際、分割 $I,J$ と $\sum_{i\in I}\alpha_iv_i=\sum_{j\in J}\beta_jv_j$（$v_0=0$、$v_i=e_i$、係数はそれぞれ $0$ 以上で和が $1$）があったとする。$\mu_i:=\alpha_i$（$i\in I$）、$\mu_j:=-\beta_j$（$j\in J$）とおくと $\sum_{i=0}^n\mu_iv_i=0$、$\sum_i\mu_i=0$ である。第 1 式は $\sum_{i=1}^n\mu_ie_i=0$ なので $\mu_1=\cdots=\mu_n=0$ であり、第 2 式から $\mu_0=0$ となる。すると $\alpha_i$ も $\beta_j$ もすべて $0$ で、和が $1$ であることに反する。したがって thm-convex-radon の点の個数 $n+2$ は $n+1$ に減らせない。この例は「$\mathbb{R}^n$ の $n+1$ 点はつねに Radon 分割をもつ」という含意を破っている。
$m\ge n+1$ とし、$C_1,\dots,C_m$ を $\mathbb{R}^n$ の凸集合とする。どの $n+1$ 個の $C_i$ にも共通の点があるならば、$C_1,\dots,C_m$ のすべてに共通の点がある。
$m$ についての帰納法で示す。$m=n+1$ では仮定そのものである。$m\ge n+2$ とし、$m-1$ 個の場合には正しいとする。$k=1,\dots,m$ について、$C_k$ を除いた $m-1$ 個の集合の族は、$m-1\ge n+1$ であり、そのどの $n+1$ 個にも共通点があるので、帰納法の仮定により共通の点 $x_k\in\bigcap_{i\ne k}C_i$ をもつ。
$m\ge n+2$ 個の点 $x_1,\dots,x_m$（重複してもよい）に thm-convex-radon を使い、Radon 分割 $I,J$ と Radon 点 $p$ をとる。任意の $k$ について $p\in C_k$ を示す。$k\notin I$ なら、$i\in I$ はすべて $i\ne k$ なので $x_i\in C_k$ であり、$C_k$ は凸なので prop-convex-combinations-closed により $p\in\operatorname{conv}\{x_i\mid i\in I\}\subset C_k$ である。$k\in I$ なら $k\notin J$ なので、$J$ について同じ議論で $p\in C_k$ である。よって $p\in\bigcap_{k=1}^mC_k$ である。$\square$
$n=1$ の場合、Helly の定理は「数直線上の区間の有限族で、どの 2 つも交わるなら全部に共通点がある」となる。これは冒頭の例 $[0,3],[1,4],[2,5]$ の一般化であり、閉区間の場合は次のように直接確かめられる。$[a_k,b_k]$（$k=1,\dots,m$）のどの 2 つも交わるなら、すべての $i,j$ について $a_i\le b_j$ である（$[a_i,b_i]\cap[a_j,b_j]$ の点 $z$ について $a_i\le z\le b_j$）。よって $\max_ia_i\le\min_jb_j$ であり、点 $\max_ia_i$ はすべての区間に属する。冒頭の例では $\max a_i=2$、$\min b_j=3$ で、共通部分はちょうど $[2,3]$ である。
平面（$n=2$）で、三角形の 3 辺を延長した 3 本の直線 $\{x_2=0\}$、$\{x_1=0\}$、$\{x_1+x_2=1\}$ を考える。どれも凸集合で、どの 2 本も交わる（交点は三角形の頂点 $0$、$e_1$、$e_2$）が、3 本に共通の点はない（$x_1=x_2=0$ なら $x_1+x_2=0\ne1$）。
一般の $n$ では、単体 $\Delta_n$ の $n+1$ 個の面
$$
F_0:=\{x\in\Delta_n\mid x_1+\cdots+x_n=1\},\qquad F_i:=\{x\in\Delta_n\mid x_i=0\}\ (i=1,\dots,n)
$$
を考える。どれも凸集合である。$F_k$ を除いた $n$ 個には共通の点 $v_k$ がある（$v_0=0$、$v_k=e_k$。$e_k$ は $x_k$ 以外の座標が $0$ で座標の和が $1$）。しかし $n+1$ 個すべてに属する点は $x_1=\cdots=x_n=0$ かつ $x_1+\cdots+x_n=1$ を満たさなければならず、存在しない。この例は、thm-convex-helly の仮定の「どの $n+1$ 個にも共通点がある」を「どの $n$ 個にも共通点がある」に弱めると、結論が破れることを示している。
Helly の定理は無限個の凸集合の族には、そのままでは成り立たない。$\mathbb{R}$ の区間 $[k,\infty)$（$k=1,2,\dots$）はどの有限個にも共通点があるが、全体の共通部分は空である。開区間 $(0,\tfrac1k)$ でも同じことが起きる（区間 の記事の例「反例：区間縮小法の仮定を外すと共通部分は空になりうる」）。有界閉の仮定を付ければ成り立つ。
$(C_\lambda)_{\lambda\in\Lambda}$ を $\mathbb{R}^n$ の有界な閉凸集合の族で、$\Lambda$ が $n+1$ 個以上の元をもつものとする。どの $n+1$ 個の $C_\lambda$ にも共通の点があるならば、$\bigcap_{\lambda\in\Lambda}C_\lambda\ne\emptyset$ である。
$\lambda_0\in\Lambda$ を 1 つ固定する。$C_{\lambda_0}$ は $\mathbb{R}^n$ の有界閉集合なのでコンパクトである（コンパクト空間 の記事の定理「有界閉集合とコンパクト性の一致」）。族 $(C_\lambda\cap C_{\lambda_0})_{\lambda\in\Lambda}$ は $C_{\lambda_0}$ の閉集合の族である。その有限個 $C_{\lambda_1}\cap C_{\lambda_0},\dots,C_{\lambda_k}\cap C_{\lambda_0}$ の共通部分は、有限族 $C_{\lambda_0},C_{\lambda_1},\dots,C_{\lambda_k}$ の共通部分である。この有限族に $\Lambda$ の元を必要なだけ付け加えて $n+1$ 個以上にしたものに thm-convex-helly を使うと、共通部分は空でない。よって族は有限交叉性をもち、コンパクト空間 の記事の命題「有限交叉性による言い換え」により $\bigcap_\lambda(C_\lambda\cap C_{\lambda_0})\ne\emptyset$ である。これは $\bigcap_\lambda C_\lambda$ に等しい。$\square$
Helly の定理は E. Helly が見つけ、J. Radon に伝えたものである。Radon は Rad21 の冒頭（p. 113）で、数年前に Helly からこの定理を伝えられたと書き、自分の証明を発表している。Radon の証明（p. 114）は $C_i$ を除く全部に属する点 $x^{(i)}$ をとり、本記事の lem-convex-affine-dependence と同じ 1 次方程式系の自明でない解を正の部分と負の部分に分けて、2 通りの重心として共通点を作るものである。Radon はこの分割の議論を独立した命題としては述べておらず、証明の中で使っている。本記事の prf-convex-radon と prf-convex-helly は、この 1 つの議論を 2 段に分けて書いたものである。同じ論文の校正時の追記で、Radon は Helly が当時見つけていた証明は自分の証明と本質的に異なると述べている。また Radon は p. 113 で、無限族の場合に有界性は 1 つの成員にだけ要求すれば十分であることを注意している。実際、prf-convex-helly-infinite で有界性を使ったのは $C_{\lambda_0}$ だけである。Carathéodory の定理は C. Carathéodory にちなむ。本記事では、thm-convex-caratheodory と thm-convex-radon をどちらも lem-convex-affine-dependence の $\mu_i$ から導き、thm-convex-helly を thm-convex-radon から導いた。
凸関数との関係
区間 $I$ 上の実数値関数 $f$ が凸関数であるとは、$x,y\in I$、$0\le t\le1$ について $f((1-t)x+ty)\le(1-t)f(x)+tf(y)$ となることをいう。これは $f$ のグラフの上側の部分（エピグラフ）$\{(x,y)\mid x\in I,\ y\ge f(x)\}\subset\mathbb{R}^2$ が凸集合であることと同値である。実際、エピグラフが凸なら点 $(x,f(x))$ と $(y,f(y))$ を結ぶ線分がエピグラフに入ることが上の不等式であり、逆に上の不等式があれば、$y_1\ge f(x)$、$y_2\ge f(y)$ のとき $(1-t)y_1+ty_2\ge(1-t)f(x)+tf(y)\ge f((1-t)x+ty)$ となる。また凸関数 $f$ と実数 $c$ について、$\{x\in I\mid f(x)\le c\}$ は凸集合（区間）である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
