ハイパーグラフの矛盾

ハイパーグラフの不一致は、一般集合システムの不一致を研究する 不一致理論の分野です。

古典的な設定では、ハイパーグラフの頂点を2つのクラスに分割し、理想的には各ハイパーエッジが両方のクラスで同じ数の頂点を含むようにすることを目指します。2つのクラスへの分割は、色分け で表すことができます。-1 と +1を色と呼びます。色クラスと は、対応する分割を形成します。ハイパーエッジ の場合、 ${\displaystyle {\mathcal {H}}=(V,{\mathcal {E}})}$${\displaystyle \chi \colon V\rightarrow \{-1,+1\}}$${\displaystyle \chi^{-1}(-1)}$${\displaystyle \chi^{-1}(+1)}$${\displaystyle E\in {\mathcal {E}}}$

${\displaystyle \chi (E):=\sum _{v\in E}\chi (v).}$

に対するの不一致${\displaystyle {\mathcal {H}}}$${\displaystyle \chi}$との不一致は${\displaystyle {\mathcal {H}}}$次のように定義されます。

${\displaystyle \operatorname {disc} ({\mathcal {H}},\chi ):=\;\max _{E\in {\mathcal {E}}}|\chi (E)|,}$

${\displaystyle \operatorname {disc} ({\mathcal {H}}):=\min _{\chi :V\rightarrow \{-1,+1\}}\operatorname {disc} ({\mathcal {H}},\chi ).}$

これらの概念と「矛盾」という用語は、ベックの論文で初めて登場したようです。^[1]この問題に関する以前の結果には、ロスによる等差数列の矛盾の有名な下限値^{[2]や、この問題と}エルデシュとスペンサーによるその他の結果の上限値^{[3] [4]およびサルコジによる上限値[5]}などがあります。^{: 39}当時、矛盾問題は準ラムゼー問題と呼ばれていました。

この概念を直感的に理解するために、いくつかの例を見てみましょう。

• のすべての辺が自明に交差する場合、つまり任意の 2 つの異なる辺について、すべての辺の基数が偶数であれば矛盾は 0 になり、奇数基数の辺がある場合は矛盾は 1 になります。${\displaystyle {\mathcal {H}}}$${\displaystyle E_{1}\cap E_{2}=\varnothing }$${\displaystyle E_{1},E_{2}\in {\mathcal {E}}}$
• もう一方の極端は、完全なハイパーグラフ によって示されます。この場合、食い違いは です。任意の 2 色付けには、少なくともこのサイズの色クラスがあり、このセットもエッジです。一方、サイズが および の色クラスを持つ任意の色付けは、食い違いが より大きくないことを証明します。食い違いは、 のハイパーエッジが交差する無秩序さを反映しているようです。ただし、次の例が示すように、物事はそれほど簡単ではありません。${\displaystyle (V,2^{V})}$${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$${\displaystyle \chi}$${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$${\displaystyle \lfloor {\frac {1}{2}}|V|\rfloor }$${\displaystyle \lceil {\frac {1}{2}}|V|\rceil }$${\displaystyle {\mathcal {H}}}$
• 、および を設定します。言葉で言えば、は 4 k頂点 {1,...,4 k } 上のハイパーグラフであり、その辺はすべて、{1,...,2 k } と {2 k +1,...,4 k } の要素の数が同じサブセットです。現在、 には多数 ( 個以上) の複雑に交差する辺があります。ただし、{1,...,2 k } をある色で塗り、{2 k +1,...,4 k } を別の色で塗ることができるため、その矛盾はゼロです。${\displaystyle n=4k}$${\displaystyle k\in {\mathcal {N}}}$${\displaystyle {\mathcal {H}}_{n}=([n],\{E\subseteq [n]\mid |E\cap [2k]|=|E\setminus [2k]|\}) }$${\displaystyle {\mathcal {H}}_{n}}$${\displaystyle {\mathcal {H}}_{n}}$${\displaystyle {\binom {n/2}{n/4}}^{2}=\シータ ({\frac {1}{n}}2^{n})}$

最後の例は、ハイパーエッジの数のような単一のパラメータを見ても矛盾を判断できないことを示しています。それでも、ハイパーグラフのサイズによって最初の上限が得られます。

1. n 個の頂点とm 個の辺を持つ任意のハイパーグラフの場合 : ${\displaystyle {\mathcal {H}}}$

• ${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq {\sqrt {2n\ln(2m)}}.}$

証明は確率的手法の単純な応用である。 をランダムな色付けとすると、 ${\displaystyle \chi :V\rightarrow \{-1,1\}}$

${\displaystyle \Pr(\chi (v)=-1)=\Pr(\chi (v)=1)={\frac {1}{2}}}$

すべての に対して独立に成り立つ。 は独立した −1, 1 のランダム変数の和なので、すべてのおよびに対して成り立つ。を とると、${\displaystyle v\in V}$${\displaystyle \chi (E)=\sum _{v\in E}\chi (v)}$${\displaystyle \Pr(|\chi (E)|>\lambda )<2\exp(-\lambda ^{2}/(2n))}$${\displaystyle E\subseteq V}$${\displaystyle \lambda \geq 0}$${\displaystyle \lambda ={\sqrt {2n\ln(2m)}}}$

${\displaystyle \Pr(\operatorname {disc} ({\mathcal {H}},\chi )>\lambda )\leq \sum _{E\in {\mathcal {E}}}\Pr(|\chi (E)|>\lambda )<1.}$

正の確率を持つランダムな色付けの食い違いは最大で なので、特に、食い違いが最大で である色付けが存在します。したがって、${\displaystyle \lambda}$${\displaystyle \lambda}$${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq \lambda .\ \Box }$

2. n個の頂点とm個の辺を持つ任意のハイパーグラフについて 、${\displaystyle {\mathcal {H}}}$ ${\displaystyle m\geq n}$

• ${\displaystyle \operatorname {disc} ({\mathcal {H}})\in O({\sqrt {n}}).}$

これを証明するには、エントロピー関数を使用するはるかに洗練されたアプローチが必要でした。もちろん、これは の場合に特に興味深いものです。 の場合、n が十分に大きい場合、 が示されることができます。したがって、この結果は通常、「6 標準偏差で十分」として知られています。これは、食い違い理論のマイルストーンの 1 つと考えられています。エントロピー法は、他の多くの用途に使用されています。たとえば、Matoušekと Spencerの等差数列の厳しい上限の証明^[6]や、Matoušek による原始粉砕関数の上限の証明などです。^[7]${\displaystyle m=O(n)}$${\displaystyle m=n}$${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq 6{\sqrt {n}}}$

ハイパーグラフの次数が有界である場合、つまり、 の各頂点が、ある小さなtに対して最大t個の辺に含まれる場合、より良い不一致境界を達成できます。特に、 ${\displaystyle {\mathcal {H}}}$

• ベックとフィアラ^[8]はを証明した。これはベック・フィアラ定理として知られている。彼らは と推測した。${\displaystyle \operatorname {disc} ({\mathcal {H}})<2t}$${\displaystyle \operatorname {disc} ({\mathcal {H}})=O({\sqrt {t}})}$
• BednarchakとHelm ^[9]およびHelm ^[10]は、Beck-Fiala境界を小さなステップで（わずかに制限された状況、すなわち）まで改良しました。${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq 2t-3}$${\displaystyle t\geq 3}$
• Bukh ^[11]は2016年にこれを に改良しました。ここで は反復対数を表します。${\displaystyle 2t-\log ^{*}t}$${\displaystyle \log ^{*}t}$
• ベックの論文^[1]の帰結は、矛盾の概念が初めて明示的に登場したものであり、ある定数Cに対して次のことを示しています。${\displaystyle \operatorname {disc} ({\mathcal {H}})\leq C{\sqrt {t\log m}}\log n}$
• この方向での最新の改善はバナシュチクによるものである^[12] 。${\displaystyle \operatorname {disc} ({\mathcal {H}})=O({\sqrt {t\log n}})}$

次のような特殊な構造を持つハイパーグラフでは、不一致のより良い境界が可能です。

• 順列の不一致- 頂点が整数 1、...、nであり、ハイパーエッジが整数上の順列が与えられたm個の区間である場合。
• 幾何学的矛盾- 頂点がユークリッド空間内の点であり、ハイパーエッジが長方形や半空間などの幾何学的オブジェクトである場合。

• 等差数列 (Roth、Sárközy、Beck、Matoušek、Spencer )
• 6つの標準偏差で十分です（スペンサー）

• コムロス予想^[13]

• 数値積分: 高次元のモンテカルロ法。
• 計算幾何学:分割統治アルゴリズム。
• 画像処理: ハーフトーン処理

• ベック、ヨーゼフ、チェン、ウィリアム WL (2009)。流通の不規則性。ケンブリッジ大学出版局。ISBN 978-0-521-09300-2。
• チャゼル、バーナード（2000年）。「不一致法：ランダム性と複雑性」ケンブリッジ大学出版局。ISBN 0-521-77093-9。
• Doerr, Benjamin (2005). Integral approximation (PDF) (資格取得論文).キール大学. OCLC  255383176. 2019年10月20日閲覧。
• マトウシェク、イジー(1999)。幾何学的不一致: 図解ガイド。スプリンガー。ISBN 3-540-65528-X。