物件B
ハイパーグラフの2色付け。プロパティ B を持つコレクション C と同等です。

数学において、性質Bは集合論的性質の一種です。正式には、有限集合 Xが与えられたとき、 Xの部分集合の集合Cが性質Bを持つとは、Xを2つの互いに素な部分集合YとZに分割し、 C内のすべての集合がYとZの両方を満たすことができることを意味します。

この性質は、1908年に初めてこの性質を導入した数学者フェリックス・バーンスタインにちなんで名付けられました。 [1]

特性Bは、集合Cによって記述されるハイパーグラフを2色にすることと等価である。特性Bを持つハイパーグラフは、2色可能とも呼ばれる。[2] : 468 二部グラフとの類推から、二部グラフとも呼ばれる。特性Bは、一様ハイパーグラフ（集合システムのすべての部分集合が同じ濃度を持つ集合システム）について研究されることが多いが、非一様の場合にも考察されてきた。[3]

コレクションCがプロパティ B を持っているかどうかを確認する問題は、集合分割問題と呼ばれます。

特性Bを持たない最小の集合族

シュタイナー三重体系 S 7 は、特性 B を持たない最小の 3 均一集合です。

サイズnの集合の集合の中で、Cが特性Bを持たない最小の集合の数はm ( n )で表される。

m(n)の値が小さい

m (1) = 1、m (2) = 3、m (3) = 7（以下の例からわかるように）、m (4) = 23（Östergård）であることが知られていますが、この結果は徹底的な探索の結果です。上限は23（Seymour、Toft）、下限は21（Manning）であることが証明されています。本稿執筆時点（2017年3月）では、既知の項が不足しているため、 m ( n )という数列のOEISエントリはまだ存在しません。

m (1) = 1
n = 1の場合、 X = {1}、C = {{1}} と設定します。すると、C は特性 B を持ちません。
m (2) = 3
n = 2 の場合、 X = {1, 2, 3} とし、C = {{1, 2}, {1, 3}, {2, 3}} （三角形）とします。すると、C は性質 B を持たないため、m (2) <= 3 となります。しかし、C ' = {{1, 2}, {1, 3}} は性質 B を持ちます（Y = {1}、Z = {2, 3} と設定）。そのため、m (2) >= 3 となります。
メートル（3）＝7
n = 3 の場合、 X = {1, 2, 3, 4, 5, 6, 7} とし、C = {{1, 2, 4}, {2, 3, 5}, {3, 4, 6}, {4, 5, 7}, {5, 6, 1}, {6, 7, 2}, {7, 1, 3}} と設定します (シュタイナーの 3 組システム S 7 )。C には特性 B がありません (したがってm (3) <= 7)。ただし、Cのいずれかの要素を省略した場合は、その要素をYとすることができ、残りの要素の集合C ' には特性 B があります (したがって、この特定のケースではm (3) >= 7)。 6 個の 3 組の他のすべてのコレクションを調べて、すべてが特性 B を持っていることを確認できます。
メートル（4）＝23
Östergård (2014)は徹底的な探索によりm (4)=23を発見した。それ以前には、Seymour (1974)が特性Bに従わずに11頂点23辺のハイパーグラフを構築し、m (4)<=23であることを示しており、Manning (1995)はm (4)>=21となるように下限を狭めていた。
29 <= m (5) <= 51
次の未知数の値の境界でさえ、かなり離れています。下限値では、一定数の一意の要素を持つ集合のみが特性Bを持たない可能性がありますが、下限値から離れるほど、この範囲は広がります。下限値は2020年に28から29に改善されました。[4]

漸近解析メートル（n）

エルデシュ (1963) は、 n個未満の集合からなる任意の集合に対して、すべての集合が二色となるような2色彩色が存在することを証明した。証明は簡単である。ランダム彩色を考える。任意の集合が単色である確率は である。和集合の境界より、単色集合が存在する確率は 未満である。したがって、良い彩色が存在する。 2 n − 1 {\displaystyle 2^{n-1}} 2 − n + 1 {\displaystyle 2^{-n+1}} 2 n − 1 2 − n + 1 = 1 {\displaystyle 2^{n-1}2^{-n+1}=1}

エルデシュ (1964) は、特性 B を持たない (つまり、すべてのハイパーエッジが二色である 2 色を持たない) ハイパーエッジを持つn均一ハイパーグラフの存在を示し、上限を確立しました。 O ( 2 n ⋅ n 2 ) {\displaystyle O(2^{n}\cdot n^{2})}

Schmidt (1963) は、最大でn個の集合からなる集合の集合はすべて性質 B を持つことを証明しました。Erdős と Lovász は と予想しました。1978 年に Beck は下限を（ は任意の小さな正数）に改良しました。2000 年に Radhakrishnan と Srinivasan は、巧妙な確率的アルゴリズムを用いて下限を に改良しました。 n / ( n + 4 ) ⋅ 2 n {\displaystyle n/(n+4)\cdot 2^{n}} m ( n ) = θ ( 2 n ⋅ n ) {\displaystyle m(n)=\theta (2^{n}\cdot n)} m ( n ) = Ω ( n 1 / 3 − ϵ 2 n ) {\displaystyle m(n)=\Omega (n^{1/3-\epsilon }2^{n})} ϵ {\displaystyle \epsilon } m ( n ) = Ω ( 2 n ⋅ n / log ⁡ n ) {\displaystyle m(n)=\Omega (2^{n}\cdot {\sqrt {n/\log n}})}

参照

参考文献

  1. ^ バーンスタイン、F. (1908)、「Zur theorie der trigonometrische Reihen」、ライプツ。ベル。、60：325～ 328。
  2. ^ ロヴァシュ、ラズロ;プラマー医学博士(1986 年)、『マッチング理論』、『離散数学年報』、第 1 巻。 29、北オランダ、ISBN 0-444-87916-1、MR  0859549
  3. ^ Beck, J. (1978)、「3-彩色ハイパーグラフについて」、離散数学、24 (2): 127– 137、doi : 10.1016/0012-365X(78)90191-7、MR  0522920
  4. ^ Aglave, Sachin; Amarnath, VA; Shannigrahi, Saswata; Singh, Shwetank (2020). 「特性Bを持たない一様ハイパーグラフの改良された境界値」(PDF) . Australasian Journal of Combinatorics . 76 (1): 73– 86. ISSN  2202-3518.

さらに読む

  • エルデシュ、ポール (1963)、「組み合わせ問題について」、Nordisk Mat。ティツクル。、11：5～ 10
  • エルデシュ、P. (1964)。 「組み合わせ問題について。II」。Acta Mathematica Academiae Scientiarum Hungaricae。15 ( 3–4 ): 445– 447.土井: 10.1007/BF01897152。
  • シュミット、W.M. (1964)。 「Ein kombinatorisches 問題 von P. Erdős と A. Hajnal」。Acta Mathematica Academiae Scientiarum Hungaricae。15 ( 3–4 ): 373–374 .土井: 10.1007/BF01897145。
  • シーモア、ポール（1974）、「エルデシュとハジュナルの組合せ問題についてのノート」、ロンドン数学会報、8（4）：681-682、doi：10.1112/jlms/s2-8.4.681。
  • トフト、ビャーネ（1975）「色彩臨界ハイパーグラフについて」、ハジュナル、A.、ラド、リチャード、ソス、ヴェラ・T.（編）『無限集合と有限集合：ポール・エルデシュ60歳の誕生日に』、ノースホランド出版社、 1445～ 1457頁 。
  • マニング、GM（1995）、「エルデシュとハジュナルのm（4）問題に関するいくつかの結果」、アメリカ数学会電子研究発表、1（3）：112-113、doi：10.1090/S1079-6762-95-03004-6。
  • ベック、J.（1978）、「3-彩色ハイパーグラフについて」、離散数学、24（2）：127-137、doi：10.1016/0012-365X（78）90191-7。
  • Radhakrishnan, J.; Srinivasan, A. (2000)、「ハイパーグラフ2色化の改良された境界とアルゴリズム」、Random Structures and Algorithms、16 (1): 4– 32、doi :10.1002/(SICI)1098-2418(200001)16:1<4::AID-RSA2>3.0.CO;2-2。
  • ミラー, EW ( 1937)「集合族の性質について」『Comp. Rend. Varsovie』30 : 31–38。
  • エルデシュ、P. ; Hajnal, A. (1961)、「集合の族の性質について」、Acta Mathematica Academiae Scientiarum Hungaricae、12 ( 1–2 ): 87–123、doi : 10.1007/BF02066676。
  • アボット, HL; ハンソン, D. (1969)「エルデシュの組合せ問題について」カナダ数学速報、12 (6): 823– 829、doi : 10.4153/CMB-1969-107-x
  • Östergård, Patric RJ (2014年1月30日). 「性質Bを持たない4-ユニフォームハイパーグラフの最小サイズについて」.離散応用数学. 163, Part 2: 199–204 . doi : 10.1016/j.dam.2011.11.035 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Property_B&oldid=1321827560"