차단 세트

특히 투영 기하학에서 블럭화 집합은 모든 선이 교차하고 전체 선을 포함하지 않는 투영 평면의 점 집합이다.그 개념은 여러 가지 방법으로 일반화될 수 있다.점과 선을 말하는 대신, 어떤 교차 개념이 이러한 물체에 이치에 맞는 경우, n차원 서브스페이스와 m차원 서브스페이스, 또는 더 일반적으로는 제1형 물체와 제2형 물체를 다룰 수 있다.일반화하는 두 번째 방법은 투영 기하학보다 더 추상적인 설정으로 이동하는 것이다.하이퍼그래프의 차단 집합을 하이퍼그래프의 모든 가장자리를 충족하는 집합으로 정의할 수 있다.

정의

순서 n의 유한 투영 평면 π에서 블럭화 집합은 모든 선이 교차하며 완전히 어떤 선도 포함하지 않는 π의 점 집합이다.이 정의에서 B가 블로킹 세트인 경우, 보완적인 포인트 세트인 π\B도 블로킹 세트인 것이다.B의 어느 지점을 제거해도 차단 세트가 아닌 세트를 남길 경우 차단 세트 B는 최소값이다.가장 작은 크기의 차단 세트를 위원회라고 한다.모든 위원회가 최소한의 차단 집합이지만, 모든 차단 집합이 위원회인 것은 아니다.순서 2의 가장 작은 투영 평면인 Fano 평면을 제외한 모든 투영 평면에 블록 세트가 존재한다.^[1]

차단 세트에 선이 없다는 조건을 떨어뜨리는 것이 유용할 때도 있다.이 확장된 정의에 따르면, 그리고 투영 평면에서 모든 선 쌍이 일치하므로, 모든 선은 차단 집합이 될 것이다.이 설정에서 선이 포함된 차단 세트를 사소한 차단 세트라고 한다.

예

순서가 n인 모든 투영 평면(각 선에는 n + 1 점이 포함됨)에서 삼각형의 정점이 없는 삼각형을 형성하는 선의 점들은 최소 차단 세트(3(n - 1)를 형성하며, 일반적으로 이 차단 세트는 위원회가 아니다.

임의의 n 순서의 투영 평면에서 다른 일반적인 구조는 주어진 선에 P라고 하는 한 점을 제외한 모든 점을 취하여 P를 통해 다른 선에 한 점을 취함으로써 이러한 점들이 모두 일렬로 있지 않도록 하는 것이다(n = 2인 경우 이 마지막 조건은 충족될 수 없다).이로써 2n 크기의 최소 차단 세트가 생성된다.

PG(2,q)에서 측면 m의 투사 삼각형 β는 삼각형의 정점 A, B, C가 β에 있고 다음 조건이 충족되도록 삼각형의 각 면에 m인 3(m - 1) 포인트로 구성된다.선 AB의 점 P와 선 BC의 점 Q가 모두 β인 경우, PQ와 AC의 교차점은 β이다.

측면 m의 투사형 3개 Δ는 3m - 2개의 점의 집합으로, m은 동시성 C 지점이 Δ이고 다음 조건이 충족되는 등 3개의 동시선 각각에 놓여 있다.한 선의 P점과 다른 선의 Q점이 Δ인 경우, 세 번째 선과 PQ의 교차점은 Δ이다.

정리:q 비드가 있는 PG(2,q)에는 크기 3(q + 1)/2의 블럭 세트인 측면(q + 3)/2의 투영 삼각형이 존재한다.^[2]

균일한 좌표를 사용하여 삼각형의 정점을 A = (1,0,0), B = (0,0), C = (0,0,1)로 한다.AB의 정점 이외의 점은 (-c, 1, 0) 형식의 좌표를 가지며, BC의 점들은 좌표(0,1,a), AC의 점들은 좌표(1,0,b)를 가지며, 여기서 a, b 및 c는 유한장 GF(q)의 요소들이다.이들 면에 각각 하나씩 있는 세 점은 a = bc일 경우에만 일직선이다.a, b, c가 GF(q)의 0이 아닌 제곱인 점을 모두 선택하면 투사 삼각형의 정의에 있는 조건이 충족된다.

정리:짝수 PG(2,q)에는 크기(3q + 2)/2의 블럭 세트인 측면(2,q + 2)의 투영 삼합체가 존재한다.^[3]

시공은 위와 유사하지만, 필드가 특성 2이므로 사각형과 비제곱은 절대추적 0과 절대추적 1의 원소로 교체할 필요가 있다.구체적으로는 C = (0,0,1)로 한다.선 X = 0에 있는 점들은 형태의 좌표(0,1,a), 선 Y = 0에 있는 점들은 형태의 좌표(1,0,b)를 가진다.선 X = Y의 점에는 (1,1,c)로 표기될 수 있는 좌표가 있다.a = b + c인 경우에만 이들 각 선에서 1개씩 세 점이 시준된다. a, b 및 c가 절대 트레이스 0의 필드 요소인 이 선에서 모든 점을 선택하면 투사적 삼합체 정의의 조건이 충족된다.

정리:PG(2,p)에서는 p p prime과 함께 측면(p + 1)/2의 투영 삼합체가 존재하며, 이는 크기(3p+ 1)/2의 차단 집합이다.^[4]

크기

일반적으로 작은 차단 세트를 검색한다.$H{\displaystyle }$ ${\displaystyle H}$ 차단 세트의 최소 크기를 $\tau {\displaystyle }$(${\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인 투영 평면에 설정된 $모든{\displaystyle }$ 블럭에는 n${\displaystyle }$+ n${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle n+{\sqrt{n}+1}개$ 이상의$$ 포인트가 있다.더욱이 이 하한을 충족하면 n은 반드시 정사각형이며 차단 세트는 π의 일부 Baer 하위 평면에 있는 점들로 구성된다.

최소 블럭 세트 크기의 상한은 동일한 맛을 가지고 있다.^[7]

순서 n의 투영 평면에 설정된 최소 블럭화에는 $최대{\displaystyle n\sqrt{}}$ + ${\displaystyle 1}${\$displaystyle n{\sqrt{n}+1$}개의$$ 점이 있다.더욱이 이 상한에 도달하면 n은 반드시 정사각형이며 차단 세트는 π에 내장된 일부 유니탈의 점들로 구성된다.

n이 제곱이 아닐 때 가장 작은 크기의 비경쟁 블럭화 세트에 대해 말할 수 있다.Aart Blokhuis로 인해 잘 알려진 한 가지 결과는 다음과 같다.^[8]

정리:p 프라임인 PG(2,p)에 설정된 비차단 블럭의 크기는 최소 3(p + 1)/2이다.

이 평면에는 이 경계를 충족하는 투영 삼각형이 존재한다.

역사

블로킹 세트는 모세 리처드슨에 의해 1956년 논문의 경제 게임 이론의 맥락에서 유래되었다^[9].^[10]유한한 투사면에서 선수들이 포인트로 식별되었고 최소 승자 연합은 라인이었다.차단 연합은 선이 없고 모든 선이 교차하는 점 집합으로 정의되었다.1958년 J. R. Isbell은^[11] 이 게임들을 비기하학적 관점에서 연구했다.Jane W. $DiPaola$는 1969년에$$ ${\displaystyle \mathrm{모든}}$ 투사 $평면$의 최소 차단 $연합$을 연구했다$.$^[12]

하이퍼그래프에서

Let $H{\displaystyle }$=${\displaystyle }$( ${\displaystyle X}$, ${\displaystyle E}$) ${\displaystyle H=(X,E)}$을(를) 하이퍼그래프로 $설정$하여 X ${\displaystyle$ X$}$을(를) 원소 집합으로 하고, $E{\displaystyle }${\$displaystyle E}$은(하이퍼)라고$$$하는{\displaystyle }$ X$${\$displaystysty X}$의 하위 집합이다.$H{\displaystyle }$ ${\displaystyle H}$의 차단 세트는 $X{\displaystyle }$ ${\displaystyle X}$의 부분 집합 $S{\displaystyle }$ ${\displaystyle S}$이며, 각$$ 축종과 비어 있지 않은 교차점이 있다.

차단 세트는 "히팅 세트" 또는 "버텍스 커버"라고도 한다.또한 "횡단"이라는 용어도 사용되지만, $일부{\displaystyle }$ 맥락에서 H ${\displaystyle H}$의 횡단면은 $X{\displaystyle }$ ${\displaystyle X}$의 부분 집합 $T{\displaystyle }$ ${\displaystyle T}$이며, 각$$ 성화체를 정확히 한 점에서 만난다.

A "two-coloring" of ${\displaystyle H}$ is a partition ${\displaystyle \{C,D\}}$ of ${\displaystyle X}$ into two subsets (color classes) such that no edge is monochromatic, i.e., no edge is contained entirely within ${\displaystyle C}$ or within ${\displaystyle D}$. Now both ${\displaystyle C}$$$ $및{\displaystyle }$ D ${\displaystyle D}$이(가) 차단 세트.

전체 k-arcs

투영 평면에서 완전한 k-arc는 3개의 콜린어(colinar)가 없는 k 포인트 집합으로, 더 큰 호로 확장할 수 없다(따라서, 호에 없는 모든 포인트는 두 점의 호를 만족하는 선인 호의 제2의 선에 있다).

정리:K를 = = PG(2,q)에서 k < q + 2의 완전한 k-arc가 되게 한다.K secant line set of K의 π에서 이중은 크기 k(k - 1)/2의 blocking set, B이다.^[13]

레데이 차단 세트

순서 q의 모든 투영 평면에서, 모든 비경쟁 차단 세트 B(b = B , 차단 세트 크기)에 대해, n 포인트에서 B를 만나는 라인을 고려한다.B에는 어떤 선도 포함되어 있지 않기 때문에, 이 선에는 B에 없는 점인 P가 있어야 한다.q를 제외한 다른 선은 각각 B의 최소 한 점을 포함해야 막힌다.따라서 $b{\displaystyle }$ ${\displaystyle \ge n}$+ ${\displaystyle q.}$ ${\displaystyle b\geq n+q.}$ 만약 어떤 선 평등이 이 관계에 있다면 차단$$ 세트는 레데이 유형의 차단 세트라고 하며 차단 세트의 라인은 레데이 라인으로 불린다(n은 B에서 가장 많은 공선 포인트가 될 것이라는 점에 유의한다).^[14]모든 블로킹 세트가 레데이 타입은 아니지만, 작은 블럭 세트도 많이 있다.이 세트들은 유한한 분야에 걸친 Lacunary 다항식들에 관한 모노그래프가 이 세트들의 연구에 영향을 미친 Laszlo Rédei의 이름을 따서 명명되었다.^[15]

아핀 차단 세트

모든 하이퍼플레인, 즉 모든 하이퍼플레인이 세트의 특정 지점과 충돌하는 유한$$ 데사게스 아핀 공간 $A{\displaystyle }$ ${\displaystyle G}$(${\displaystyle n}$ ,${\displaystyle q}$) ${\displaystyle AG(n,q)}$에 있는 점 집합을 아핀 블로킹 세트라고 한다.좌표계를 고정하여$$ $F{\displaystyle {\mathbb{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}${\$displaystyle \mathb {F} _{q}^{n}}}$을(를) 사용하여 공간을 식별하십시오.그러면 좌표 축에 놓여 있는 점들이 크기 1 +${\displaystyle }n{\displaystyle \mathrm{}}$ (${\displaystyle q}$ -${\displaystyle 1}$ $){\displaystyle 1+n (q-1)}$의 차단 세트를 형성하고 있음을 쉽게 알 수 있다$.$Jean Doyen은 1976년 Oberwolfach 회의에서 이것이 차단 세트 중에서 가장 적은 크기라고 추측했다.이것은 1977년 R. E. Jamison에 의해 증명되었고,^[16] A. E. Brouwer에 의해 독립적으로 증명되었다. 1978년 슈리히버는 이른바 다항식 방식을 사용했다.Jamison은 이중성을 사용하여 다음과 같은 일반적인 커버링 결과를 증명했다.

Let ${\displaystyle V}$ be an ${\displaystyle n}$ dimensional vector space over ${\displaystyle \mathbb {F} _{q}}$. Then the number of ${\displaystyle k}$-dimensional cosets required to cover all vectors except the zero vector is at least ${\displaystyle q^{n-k}-1+k(q-1)}$.더구나 이 바운드는 날카롭다.

메모들

참조

• Barwick, Susan; Ebert, Gary (2008), Unitals in Projective Planes, New York: 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, Amsterdam, 1973.$$(Defines ${\displaystyle \tau }$(H ) {\$displaystyle \tau (H)}.)$
• P. Ducet, Hypergraphs, 7장: Combit of Combinatorics, North-Holland, Amsterdam, 1995.
• Hirschfeld, J.W.P. (1979), Projective Geometries over Finite Fields, Oxford: Oxford University Press, ISBN 978-0-19-853526-3
• Holder, Leanne D. (2001), Blocking Sets of Conics, Ph.D. thesis, University of Colorado Denver
• De Beule, Jan; Storme, Leo (2011), Current Research Topics in Galois Geometry, Nova Science Publishers, ISBN 978-1-61209-523-3, archived from the original on 2016-01-29, retrieved 2016-01-23