ブロッキングセット

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

位数nの有限射影平面π において、ブロッキング集合とは、すべての直線が交差し、どの直線も完全には含まれない π の点の集合のことである。この定義によれば、B がブロッキング集合であれば、補集合 π\ Bもブロッキング集合である。ブロッキング集合Bが最小とは、 Bの任意の点を取り除いたときにブロッキング集合ではない集合が残る場合である。最小サイズのブロッキング集合は、コミッティと呼ばれる。すべてのコミッティは最小ブロッキング集合であるが、すべての最小ブロッキング集合がコミッティであるわけではない。ブロッキング集合は、位数 2 の最小の射影平面であるファノ平面を除くすべての射影平面に存在する。^[1]

ブロッキング セットに直線が含まれないという条件を削除すると便利な場合があります。この拡張された定義では、射影平面ではすべての直線のペアが交わるため、すべての直線がブロッキング セットになります。この設定では、直線を含むブロッキング セットは、 自明なブロッキング セットと呼ばれます。

n次射影平面（各線分にはn + 1 個の点が含まれる）では、三角形の頂点を除いた三角形を形成する線分上の点（3( n -1) 個の点）は、一般にはコミッティではない最小ブロッキング セット（n = 2 の場合、このブロッキング セットは自明）を形成します。

n次の任意の射影平面におけるもう 1 つの一般的な構成は、与えられた直線上の1 つの点 (たとえばP )を除くすべての点を取り、次にP を通る他の各直線上の 1 つの点を取り、これらの点がすべて同一線上にないことを確認することです(この最後の条件はn = 2の場合は満たすことができません)。これにより、サイズ 2 nの最小のブロック セットが生成されます。

PG (2, q )上の辺がmの射影三角形βは、三角形の各辺にm個ずつ、計3( m -1)点から構成され、三角形の頂点A、B、Cはβ内にあり、次の条件が満たされます。線分AB上の点Pと線分BC上の点Qが両方ともβ内にある場合、 PQとACの交点はβ内にあります。

辺が m の射影三角和点δは、 3 つの同時直線のそれぞれにm個ある3 m - 2 点の集合であり、同時点C はδ 内にあり、次の条件が満たされます。直線の 1 つにある点Pと別の直線にある点Q がδ 内にある場合、 PQと 3 番目 の直線の交点はδ 内にあります。

定理： qが奇数のPG(2, q )において、辺が( q + 3)/2の射影三角形が存在し、これは大きさが3( q + 1)/2のブロック集合である。 ^[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 )の要素です。これらの辺のそれぞれに 1 つずつある 3 つの点は、 a = bcの場合にのみ同一直線上にあります。 a、b、cが GF( q )のゼロでない平方であるすべての点を選択すると、射影三角形の定義の条件が満たされます。

定理： qが偶数のPG(2, q )において、辺が( q + 2)/2の射影三元集合が存在し、これは大きさが( 3q + 2)/2のブロッキング集合である。 ^[3]

構築は上記と似ていますが、体の標数が 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が素数であるとき、辺が( p + 1)/2の射影三元組が存在し、これは大きさが( 3p + 1)/2のブロッキング集合である。^[4]

通常は、小さなブロッキング セットを検索します。 のブロッキング セットの最小サイズはと呼ばれます。 ${\displaystyle H}$${\displaystyle \tau (H)}$

q位のデザルグ射影平面PG(2, q )において、ブロッキング集合Bの大きさは制限される: ^[5]

${\displaystyle q+{\sqrt {q}}+1\leq |B|\leq q^{2}-{\sqrt {q}}.}$

qが平方の場合、下限は任意の Baerサブ平面によって達成され、上限は Baer サブ平面の補平面から得られます。

より一般的な結果が証明できる。^[6]

位数nの射影平面 π 内の任意のブロック集合には、少なくとも 個の点が存在します。さらに、この下限が満たされる場合、n は必ず正方形となり、ブロック集合は π の何らかの Baer サブ平面内の点から構成されます。 ${\displaystyle n+{\sqrt {n}}+1}$

最小ブロッキング集合の大きさの上限も同様である。^[7]

n 位の射影平面 π 内の任意の最小ブロック集合には、最大で個の点が含まれます。さらに、この上限に達すると、n は必ず正方形になり、ブロック集合は π に埋め込まれた何らかの単位元の点から構成されます。 ${\displaystyle n{\sqrt {n}}+1}$

nが平方でない場合、最小サイズの非自明なブロック集合についてはあまり言えない。アート・ブロックハウスによるよく知られた結果の1つは次の通りである: ^[4]

定理:PG(2, p )における非自明なブロッキング集合( pは素数)の大きさは少なくとも3( p +1)/2である。

これらの平面には、この境界を満たす射影三角形が存在します。

ブロッキングセットは、1956年にモーゼス・リチャードソンが発表した経済ゲーム理論の論文^[8]で生まれました。 ^{[9]プレイヤーは有限}射影平面上の点として識別され、最小勝利連合は線でした。ブロッキング連合は、線を含まないがすべての線と交差する点の集合として定義されました。1958年、JRイズベル^[10​​]は非幾何学的な観点からこれらのゲームを研究しました。ジェーン・W・ディパオラは1969年にすべての射影平面の順序における最小ブロッキング連合を研究しました。^[11]${\displaystyle \leq 9}$

をハイパーグラフとすると、 は要素の集合であり、は (ハイパー) エッジと呼ばれるのサブセットのコレクションです。 のブロッキング セットは、各ハイパーエッジと空でない交差を持つ のサブセットです。${\displaystyle H=(X,E)}$${\displaystyle X}$${\displaystyle E}$${\displaystyle X}$${\displaystyle H}$${\displaystyle S}$${\displaystyle X}$

ブロッキング セットは、「ヒット セット」または「頂点カバー」と呼ばれることもあります。また、「横断」という用語も使用されますが、コンテキストによっては、の横断は各ハイパーエッジと正確に 1 つの点で交わる のサブセットになります。${\displaystyle H}$${\displaystyle T}$${\displaystyle X}$

の「2 色分割」とは、を2 つのサブセット (色クラス) に分割することです。この場合 、どの辺も単色ではありません。つまり、どの辺も 内または 内に完全に含まれることはありません。これで、と は両方ともブロッキング セットになります。 ${\displaystyle H}$${\displaystyle \{C,D\}}$${\displaystyle X}$${\displaystyle C}$${\displaystyle D}$${\displaystyle C}$${\displaystyle D}$

射影平面では、完全なk弧は、同一直線上にない 3 つの k 点の集合であり、より大きな弧に拡張することはできません (したがって、弧上にないすべての点は、弧の割線、つまり 2 つの点で弧と交わる線上にあります)。

定理：KをΠ = PG(2, q )の完全なk弧とし、 k < q + 2とする。Kの割線集合のΠにおける双対は、サイズk ( k - 1)/2のブロッキング集合Bである。^[12]

位数qの任意の射影平面において、任意の非自明なブロック集合B (ブロック集合のサイズb = | B |) に対して、 n点でB と交わる直線を考える。 Bに含まれる直線はないため、この直線上にはBに含まれない点Pが存在する必要がある。Pを除く他のq本の直線は、それぞれがブロックされるためにはBの点を少なくとも 1 つ含んでいなければならない。したがって、この関係において何らかの直線の等式が成り立つ場合、ブロック集合はRédei 型のブロック集合と呼ばれ、直線はブロック集合のRédei 直線と呼ばれる( n はB内の共線点の最大数になる点に注意)。^[13]すべてのブロック集合が Rédei 型というわけではないが、小さいものの多くは Rédei 型である。これらの集合は、有限体上の Lacunary 多項式に関するモノグラフがこれらの集合の研究に影響を与えたLászló Rédeiにちなんで名付けられている。 ^[14]${\displaystyle b\geq n+q.}$

有限デザルグアフィン空間内の点の集合で、すべての超平面と非自明に交差する、つまりすべての超平面がその集合のどこかの点と接するものを、アフィンブロッキング集合と呼ぶ。座標系を固定して、空間を と同一視する。すると、座標軸上にある点の集合がサイズ のブロッキング集合を形成することが簡単に示される。Jean Doyen は 1976 年のオーバーヴォルフアッハ会議で、これがブロッキング集合の最小サイズであると予想した。これは 1977 年に RE Jamison によって^[15]証明され、 1978 年にはAE BrouwerとA. Schrijverによって^[16]いわゆる多項式法を用いて独立に証明された。Jamison は、双対性を用いてアフィンブロッキング集合の境界が従う次の一般的な被覆結果を証明した。 ${\displaystyle AG(n,q)}$${\displaystyle \mathbb {F} _{q}^{n}}$${\displaystyle 1+n(q-1)}$

を 上の次元ベクトル空間とします。このとき、零ベクトル以外のすべてのベクトルをカバーするために必要な 次元剰余類の数は少なくとも です。さらに、この境界は厳密です。${\displaystyle V}$${\displaystyle n}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle k}$${\displaystyle q^{nk}-1+k(q-1)}$

• バーウィック、スーザン; エバート、ゲイリー (2008)、Unitals in Projective Planes、ニューヨーク: Springer、doi :10.1007/978-0-387-76366-8、ISBN 978-0-387-76364-4、ISSN  1439-7382
• C. Berge、「Graphs and hypergraphs」、North-Holland、アムステルダム、1973 年。(定義)${\displaystyle \tau (H)}$
• P. Duchet、「ハイパーグラフ」、第 7 章: Handbook of Combinatorics、North-Holland、アムステルダム、1995 年。
• ヒルシュフェルド、JWP（1979）、有限体上の射影幾何学、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-853526-3
• ホルダー、リアン・D. (2001)、円錐曲線のブロッキングセット、博士論文、コロラド大学デンバー校
• ジャン・ド・ブール。 Storme、Leo (2011)、ガロア幾何学における現在の研究トピックス、Nova Science Publishers、ISBN 978-1-61209-523-3、2016年1月29日にオリジナルからアーカイブされ、2016年1月23日に取得