ラドーの定理（ラムゼー理論）

ラドーの定理は、ラムゼー理論として知られる数学の分野の定理です。ドイツの数学者リチャード・ラドーにちなんで名付けられました。この定理は、彼の論文「組み合わせ論の研究」で証明されました。

を線形方程式のシステムとし、 を整数要素を持つ行列とします。このシステムは、自然数 1、2、3、... のすべての - 色付けに対して、システムが単色解を持つ場合、 - 正則であると言われます。すべてのr ≥ 1に対して r 正則である場合、システムは正則です 。 ${\displaystyle A\mathbf {x} =\mathbf {0} }$${\displaystyle A}$${\displaystyle r}$${\displaystyle r}$

ラドーの定理は、行列A が列条件を満たす場合のみ、システムが正則であると述べている。c _{i は}Aのi番目の列を表すものとする。行列Aが列条件を満たすには、列インデックスの分割C ₁、C ₂、 ...、C _{n が}存在し、 の場合、 ${\displaystyle A\mathbf {x} =\mathbf {0} }$${\displaystyle s_{i}=\Sigma _{j\in C_{i}}c_{j}}$

1. ₁ = 0です
2. すべてのi  ≥ 2に対して、 s _{i は}k  <  iであるすべてのC _kにおけるc _jの有理数 [1] 線型結合として^表すことができます。これは、 s _{i が}c _jの集合によって張られるQ ^mの線型部分空間内にあることを意味します 。

フォークマンの定理は、すべての空でない和が単色であるような任意の大きな整数の集合が存在するという主張であり、方程式系の正則性に関するラドーの定理の特別なケースと見なすことができます。

${\displaystyle x_{T}=\sum _{i\in T}x_{\{i\}},}$

ここでTは集合{1, 2, ..., x }の各空でない部分集合にわたる。^[2]

ラドーの定理の他の特殊なケースとしては、シューアの定理とファンデルワールデンの定理があります。前者を証明するには、ラドーの定理を行列に適用します。mを単色等差数列の長さとして選択した場合のファンデルワールデンの定理の場合、たとえば次の行列を考えることができます。 ${\displaystyle (1\ 1\ {-1})}$

${\displaystyle \left({\begin{matrix}1&1&-1&0&\cdots &0&0\\1&2&0&-1&\cdots &0&0\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\1&m-1&0&0&\cdots &-1&0\\1&m&0&0&\cdots &0&-1\end{matrix}}\right)}$

線形方程式のシステムが与えられた場合、それが正則であることを計算的に確認する方法は、事前には不明です。幸い、ラドーの定理は、有限時間でテスト可能な基準を提供します。無限の数の自然数の着色を考慮する代わりに、与えられた行列が列条件を満たしていることを確認する必要があります。行列は有限の数の列のみで構成されているため、この特性は有限時間で検証できます。

しかし、部分集合和問題は、必要な列の分割C ₁、C ₂、...、C _nを計算する問題に簡略化できます。部分集合和問題の入力セットS が与えられた場合、 Sの要素を 1 × | S |の形状の行列に書き込むことができます。すると、分割C _{1のベクトルに対応する}Sの要素の合計はゼロになります。部分集合和問題はNP 完全です。したがって、線形方程式系が正則であることを確認することも NP 完全問題です。