ブロッキングセット – 日本語百科事典辞書

Blocking_set
幾何学、具体的には射影幾何学、ブロックセットは、内の点の集合である射影平面毎にラインが交差し、その行全体を含みません。この概念は、いくつかの方法で一般化できます。点と線について話す代わりに、n次元の部分空間とm次元の部分空間、またはさらに一般的には、交差の概念がこれらのオブジェクトに意味がある場合は、タイプ1のオブジェクトとタイプ2のオブジェクトを扱うことができます。一般化する2つ目の方法は、射影幾何学よりも抽象的な設定に移行することです。ハイパーグラフのブロッキングセットは、ハイパーグラフのすべてのエッジを満たすセットとして定義できます。

コンテンツ
1 意味
2 例
3 サイズ
4 歴史
5 ハイパーグラフで
6 完全なkアーク
7 Rédeiブロッキングセット
8 アフィンブロッキングセット
9 ノート
10 参考文献

意味
次数nの有限射影平面πでは、ブロッキングセットは、すべての線が交差し、線を完全に含まないπの点のセットです。この定義では、Bがブロッキングセットである場合、補完的なポイントセットであり、π Bもブロッキングセットです。ブロックセットBは、ある最小の任意の点を除去した場合、Bはブロックセットないセットを残します。最小サイズのブロッキングセットは委員会と呼ばれます。すべての委員会は最小限のブロックセットですが、すべての最小限のブロックセットが委員会であるとは限りません。ブロッキングセットは、次数2の最小射影平面であるファノ平面を除くすべての射影平面に存在します。
ブロッキングセットに行が含まれていないという条件を削除すると便利な場合がこの拡張された定義の下で、そして射影平面ではすべての線のペアが交わるため、すべての線がブロッキングセットになります。この設定では、行を含むブロッキングセットはトリビアルブロッキングセットと呼ばれます。

例
任意に射影平面ためのN（各行が含まN、三角形の頂点なしで三角形を形成するライン上の点+ 1点）（3（N – （1）点）最小阻止セットを形成する場合、N = 2このブロッキングセットは些細なものです）これは一般に委員会ではありません。
次数nの任意の射影平面での別の一般的な構成は、特定の線上の1つの点、たとえばPを除くすべてを取り、次にPを通る他の各線上の1つの点を取り、これらの点がすべて同一線上にないことを確認することです（これn = 2の場合、最後の条件は満たされません。）これにより、サイズ2nの最小ブロッキングセットが生成されます。
投影三角形のβ側M PG（2、でqは）3（から成るM – 1）点、M頂点ように、三角形の各辺に、A、B及びCの三角形のはβであり、そして次の条件が満たされます。線ABの点Pと線BCの点Qが両方ともβにある場合、PQとACの交点はβに
射影トライアドδ側Mのは、3つのセットであり、M 2点、 – M同時実行のポイントように3本の同時線のそれぞれに嘘のCが点の場合：δであり、以下の条件が満たされるP一方線の数と別の線上の点Qがδにある場合、PQと3番目の線との交点はδに
定理：qが奇数のPG（2、q）には、サイズ3（q + 1）/ 2のブロッキングセットである辺（q + 3）/ 2の射影三角形が存在します。
同次座標
を使用して
、三角形の頂点を
A =（1，0，0）、
B =（0，1，0）、
C =（0，0，1）とします。頂点以外のAB側の点は、（- c、1、0）の形式の座標を
持ち、
BC上の点は座標（0，1、
a）を持ち、
AC上の点は座標（1，0、b）を持ちます。
ここ
で、a、 b、 cは有限体GF（q）の要素です
。a =
bcの場合に限り、これらの各辺に1つずつ、3つの点が同一線上にありa、 b、 cがGF（q）の非ゼロ二乗である
すべての点を選択することにより
、射影三角形の定義の条件が満たされます。
定理：qが偶数のPG（2、q）には、サイズ（3 q + 2）/ 2のブロッキングセットである辺（q + 2）/ 2の射影トライアドが存在します。
構造は上記と同様ですが、フィールドが
標数2であるため、正方形と非正方形を絶対トレース0と絶対トレース1の要素に置き換える必要があり具体的には、
C =（0，0，1）とします。線X = 0上の点
は、形式（0，1、
a）の座標を持ち、線
Y = 0上の点は、形式（1，0、b）の座標を持ち
ます。線X = Yの点は、（1，1、c）と書くことができる座標を持ってい
ます。これらの線のそれぞれから1つずつ、3つの点は、a =
b +
cの場合に限り、同一線上にありa、 b、 cが絶対トレース0のフィールド要素であるこれらの線上のすべての点を選択することにより
、射影トライアドの定義の条件が満たされます。
定理：PG（2、p）では、pが素数で、サイズ（3 p + 1）/ 2のブロッキングセットである辺（p + 1）/ 2の射影トライアドが存在します。

サイズ
通常、小さなブロッキングセットを検索します。のブロッキングセットの最小サイズ {H}
$H""$
と呼ばれる τ （（）。
{ tau（H）}

。
次数q、PG（2、q）のDesarguesian射影平面では、ブロッキングセットBのサイズは次のように制限されます。 + +1 ≤
| |
≤ 2
− 。
{q + { sqrt {q}} + 1 leq | B | leq q ^ {2}-{ sqrt {q}}。}
qが正方形の場合、下限は任意のBaerサブプレーンによって達成され、上限はBaerサブプレーンの補集合から得られます。
より一般的な結果を証明することができます。
次数nの射影平面πに設定されたブロッキングには、少なくとも ++ 1 {n + { sqrt {n}} + 1}

ポイント。さらに、この下限が満たされている場合、nは必然的に正方形であり、ブロッキングセットはπのいくつかのBaerサブプレーン内の点で構成されます。
最小ブロッキングセットのサイズの上限は同じフレーバーを持っています。
n次の射影平面πに設定された最小のブロッキングは最大で+ 1 {n { sqrt {n}} + 1}

ポイント。さらに、この上限に達した場合、nは必然的に正方形であり、ブロッキングセットはπに埋め込まれたいくつかの単位の点で構成されます。
nが正方形でない場合、最小サイズの自明でないブロッキングセットについて言うことができます。Aart Blokhuisによるよく知られた結果の1つは、次のとおりです。
定理：PG（2、p）、p素数で設定された自明でないブロッキングは、少なくとも3（p + 1）/ 2のサイズを持ちます。
これらの平面には、この境界を満たす射影三角形が存在します。

歴史
ブロッキングセットは、モーゼスリチャードソンによる1956年の論文の経済ゲーム理論の文脈で始まりました。プレイヤーは有限の射影平面内の点で識別され、最小の勝利連立は線でした。ブロッキング連立は何行を含まないが、すべての線と交差する点の集合として定義しました。1958年、JR Isbell は、これらのゲームを非幾何学的な観点から研究しました。Jane W. DiPaolaは、すべての射影平面における最小ブロッキング連立を研究しました≤ 9
{ leq 9}

1969年。

ハイパーグラフで
させて =（（、 E ）。
{H =（X、E）}

ハイパーグラフになるので、 {X}

要素のセットであり、 E {E}

のサブセットのコレクションです {X}

、（ハイパー）エッジと呼ばれます。のブロッキングセット {H}

サブセットです {S}

の {X}

各ハイパーエッジとの交差が空ではありません。
ブロッキングセットは、「ヒットセット」または「頂点被覆」と呼ばれることも「横断」という用語も使用されますが、状況によっては、 {H}

サブセットです {T}

の {X}

これは、各ハイパーエッジと正確に1点で一致します。
の「2色」 {H}

パーティションです
{{ 、 }
{ {C、D }}

の {X}

エッジが単色にならないように、つまりエッジが完全に含まれないように、2つのサブセット（カラークラス）に分割します {C}

または内 {D}

。今両方 {C}

と {D}

ブロッキングセットです。

完全なkアーク
射影平面完全K -arcの集合であるk個の点は、何3つのコリニア大きい円弧に拡張することができない（したがって、ない円弧上のすべての点は、アークライン会議の割線ではありません2点の弧。）
定理：レッツは、Kが完了するk個のΠ= PG（2、で-arc Q付き）K < Q + 2重の割線ラインのセットのΠにおけるKはブロックセットであるBサイズの、K（K -1）/ 2。

Rédeiブロッキングセット
次数qの射影平面では、自明でないブロッキングセットB（b = | B |、ブロッキングセットのサイズ）について、n点でBと交わる線を考慮します。Bには線が含まれていないため、この線上にはBにない点Pが存在する必要が他のq行は、ブロックされるために、Pがそれぞれ少なくとも1つのBポイントを含む必要がしたがって、 ≥ + 。
{b geq n + q。}

いくつかのラインの平等は、この関係に保持するために、ブロックセットが呼び出された場合Rédeiタイプのブロッキングセット及び行をRédeiラインブロックセットの（すなわちノートNにおける同一線上の点の最大数になりますB）。すべてのブロッキングセットがRédeiタイプであるわけではありませんが、小さいものの多くはそうです。これらの集合は、有限場上のラクナリー多項式に関するモノグラフがこれらの集合の研究に影響を与えたラースロー・レデイにちなんで名付けられました。

アフィンブロッキングセット
有限のDesarguesianアフィン空間内の点のセット（（、）。
{AG（n、q）}

すべての超平面と自明ではない交差をする、つまりすべての超平面がセットのある点に入射するものは、アフィンブロッキングセットと呼ばれます。スペースを特定する{ mathbb {F} _ {q} ^ {n}}

座標系を固定することによって。次に、座標軸上にある点のセットがサイズのブロッキングセットを形成することが簡単に示されます。 1 + （（ − 1 ）。
{1 + n（q-1）}

。Jean Doyenは、1976年のOberwolfach会議で、これがブロッキングセットの可能な最小サイズであると推測しました。これは、1977年にRE Jamison によって証明され、1978年にAE Brouwer、A。Schrijver によって、いわゆる多項式法を使用して独立して証明されました。ジャミソンは、アフィンブロッキングセットの限界が双対性を使用して続く次の一般的なカバー結果を証明しました。
させて V {V}

豆 {n}

上の次元ベクトル空間 { mathbb {F} _ {q}}

。次に、 k {k}

-ゼロベクトルを除くすべてのベクトルをカバーするために必要な次元剰余類は、少なくとも −k − 1 + k（（ − 1 ）。
{q ^ {nk} -1 + k（q-1）}

。さらに、この限界は鋭いです。

ノート
^ Hirschfeld 1979、p。366
^ Hirschfeld 1979、p。376、定理13.4.1
^ Hirschfeld 1979、p。377、定理13.4.2
^ Blokhuis、Aart。「PG（2、p）のブロッキングセットのサイズについて」（PDF）。スプリンガー。
^ Hirschfeld 1979、p。376、定理13.3.3
^ Barwick＆Ebert 2008、p。30、定理2.15
^ Barwick＆Ebert 2008、p。30、定理2.16
^ Blokhuis、Aart（1994）、「PG（2、p）で設定されたブロッキングのサイズについて」、Combinatorica、14：111–114、doi：10.1007 / bf01305953
^ ホルダー2001、p。45
^ Richardson、Moses（1956）、「On Finite Projective Games」、Proceedings of the American Mathematical Society、7（3）：458–465、doi：10.2307 / 2032754、JSTOR 2032754
^ Isbell、JR（1958）、「A Class of Simple Games」、Duke Mathematical Journal、25（3）：425–436、doi：10.1215 / s0012-7094-58-02537-7
^ DiPaola、Jane W.（1969）、「小さな射影平面ゲームにおける最小ブロッキング連合について」、SIAM Journal on Applied Mathematics、17（2）：378–392、doi：10.1137 / 0117036
^ Hirschfeld 1979、p。366、定理13.1.2
^ Szőnyi、Tomás（1997）、「Desarguesianアフィンおよび射影平面のブロッキングセット」、有限体とその応用、3（3）：187–202、doi：10.1006 / ffta.1996.0176
^ Szőnyi、Tomás（1999）、「AroundRédeiの定理」、離散数学、208 /209：557–575、doi：10.1016 / s0012-365x（99）00097-7
^ Jamison、Robert E.（1977）、「部分空間の剰余類による有限体のカバー」、Journal of Combinatorial Theory、シリーズA、22（3）：253–266、doi：10.1016 / 0097-3165（77）90001-2
^ ブラウワー、アンドリーズ; Schrijver、Alexander（1978）、「アフィン空間のブロッキング数」（PDF）、Journal of Combinatorial Theory、シリーズA、24（2）：251–253、doi：10.1016 / 0097-3165（78）90013-4

参考文献
バーウィック、スーザン; Ebert、Gary（2008）、Unitals in Projective Planes、ニューヨーク：Springer、doi：10.1007 / 978-0-387-76366-8、ISBN 978-0-387-76364-4、ISSN 1439-7382
C.ベルジュ、グラフとハイパーグラフ、北ホラント、アムステルダム、1973年。（定義 τ （（）。
{ tau（H）}
。） P. Duchet、Hypergraphs、Chapter 7 in：Handbook of Combinatorics、North-Holland、Amsterdam、1995。
Hirschfeld、JWP（1979）、有限フィールド上の射影幾何学、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-853526-3
ホルダー、Leanne D.（2001）、円錐曲線のブロッキングセット、Ph.D。コロラド大学デンバー校論文
De Beule、1月; Storme、Leo（2011）、Galois Geometryの現在の研究トピック、Nova Science Publishers、ISBN 978-1-61209-523-3、アーカイブからのオリジナル2016年1月29日に、取得した2016年1月23日を”