실베스터-갈라이 정리

기하학에서 실베스터-갈라이 정리는 유클리드 평면의 모든 유한한 점 집합은 두 점을 정확히 통과하는 선 또는 모든 점을 통과하는 선을 가지고 있다고 말합니다. 이름은 1893년에 문제로 제기한 제임스 조셉 실베스터와 1944년에 이 정리의 첫 번째 증명 중 하나를 발표한 티보르 갈라이의 이름을 따서 지어졌습니다.

점 집합 중 정확히 두 개를 포함하는 선을 보통 선이라고 합니다. 그 정리를 진술하는 또 다른 방법은 점들의 공선이 아닌 모든 유한 집합은 보통의 선을 갖는다는 것입니다. 정리의 강화에 따르면, 모든 유한 점 집합(한 선에 있는 모든 것은 아님)은 적어도 선형의 일반 선을 가집니다. 알고리즘은 $O{\displaystyle (n}$ ${\displaystyle \log }$ ⁡ n) ${\displaystyle O($n$\backslash$log n)}에서 $n$ ${\displaystyle$ $n$$}$개의 점 집합에서 일반 선을 찾을 수 있습니다.

역사

실베스터-갈라이 정리는 J. J. J. 실베스터 (1893)에 의해 문제로 제기되었습니다. 켈리(Kelly, 1986)는 실베스터가 복잡한 사영 평면에서 입방 곡선의 변곡점이 9개의 점과 12개의 선으로 구성된 구성(헤세 구성)을 이루는 대수기하학의 관련 현상에 의해 동기부여되었을 수 있다고 제안합니다. 실베스터-갈라이 정리는 이 9개의 점 모두가 실제 좌표를 갖는 것은 불가능하다는 것을 암시합니다.^[1]

H. J. Woodall(1893a, 1893b)은 실베스터-갈라이 정리에 대한 짧은 증명을 가지고 있다고 주장했지만, 이 정리는 출판 당시 이미 불완전한 것으로 지적되었습니다. 에버하르트 멜키오르(Eberhard Melchior, 1941)는 이와 동등한 공식인 사영 이중에서 이 정리(그리고 실제로는 약간 더 강력한 결과)를 증명했습니다. Melchior의 증명을 알지 못한 Paul Erd ő스(1943)는 이 추측을 다시 언급했고, 이후 Tibor Gallai에 의해 증명되었고, 곧이어 다른 저자들에 의해 증명되었습니다.

1951년 에르트 ő스는 이 결과를 "갈라이의 정리"라고 불렀지만, 1954년 레너드 블루멘탈의 리뷰에서는 이미 실베스터-갈라이 정리라고 불렸습니다. 그것은 실베스터의 이름을 딴 많은 수학적 주제들 중 하나입니다.

동등한 버전

일반적인 선의 존재에 대한 문제는 유클리드 평면 대신 실제 사영 평면 RP의² 점에 대해서도 제기될 수 있습니다. 사영 평면은 유클리드 평면에서 평행한 선들이 서로 교차하는 "무한에서" 추가 점들을 추가하고, 추가된 모든 점들을 포함하는 "무한에서" 단일 선을 추가함으로써 유클리드 평면으로부터 형성될 수 있습니다. 그러나 사영 평면의 추가 점들은 일반적인 선이 없는 비유클리드 유한 점 집합을 만드는 데 도움이 될 수 없습니다. 왜냐하면 사영 평면의 모든 유한 점 집합은 점선 입사의 동일한 조합 패턴을 가진 유클리드 점 집합으로 변환될 수 있기 때문입니다. 따라서 이 두 가지 유형의 평면 중 하나에 존재하는 점과 선이 무한히 많이 교차하는 패턴도 다른 하나에 존재합니다. 그럼에도 불구하고, 투영 관점은 특정 구성을 더 쉽게 설명할 수 있게 합니다. 특히 투영 기하학의 문장에서 점과 선의 역할을 서로 교환할 수 있는 투영 이중성을 사용할 수 있습니다. 투영 이중성 하에서 RP에서² 비직선 점들의 집합에 대한 일반적인 선의 존재는 유한하게 많은 선들의 사소한 배열에서 일반적인 점의 존재와 동등합니다. 배열은 모든 선이 공통점을 통과할 때는 사소하고 그렇지 않으면 사소하지 않다고 합니다. 일반점은 정확히 두 선에 속하는 점입니다.^[2]

선의 배열은 생성기라고 불리는 유한한 선분 집합의 민코프스키 합으로 형성된 다면체인 zonohedra와 밀접하게 연결된 조합 구조를 가지고 있습니다. 이와 관련하여 정사면체의 서로 다른 면의 각 쌍은 각 생성기에 대해 하나의 선이 있는 사영 평면의 선 배열의 교차점에 해당합니다. 각 면의 변의 수는 배열에서 교차하는 선의 수의 두 배입니다. 예를 들어, 보이는 길쭉한 십이면체는 5개의 생성기, 2쌍의 반대 육각형 면, 4쌍의 반대 평행사변형 면을 가진 정면체입니다. 해당하는 다섯 줄 배열에서는 두 개의 세 쌍의 선이 교차하고(반대되는 육각형의 두 쌍에 해당) 나머지 네 쌍의 선은 일반적인 점(반대되는 평행사변형의 네 쌍에 해당)에서 교차합니다. 실베스터-갈라이 정리의 동치 명제는, zonohedra의 관점에서, 모든 정면체는 적어도 하나의 평행사변형 면(평행사변형의 특별한 경우로 직사각형, 마름모꼴, 정사각형을 세는 것)을 갖는다는 것입니다. 보다 강력하게, 평면에서 $n개$의 ${\displaystyle$ n$}개$ 점 세트가 적어도 ${\displaystyle {t2\mathrm{}}_{}n)}$ ${\displaystyle t_{2}(n)$개의 일반$$ 라인을 가질 수 있을 때마다, $n개$의 ${\displaystyle n}$개의$$ 생성기가 있는 zonohedra는 적어도 ${\displaystyle {t2\mathrm{}}_{}n)}$ ${\displaystyle 2t_{2}(n)$개의 평행사변형$$ 면을 가질 수 있습니다.^[6]

증명

실베스터-갈라이 정리는 여러 가지 방법으로 증명되었습니다. Gallai의 1944년 증명은 유클리드 기하학과 사영 기하학 사이를 왔다갔다하며, 이는 점들을 0에 가장 가까운 기울기의 선으로 찾을 수 있는 동등한 구성으로 변환하기 위한 것입니다. 자세한 내용은 Borwein & Moser(1990)를 참조하십시오. 1941년 Melchior의 증명은 사영 이중성을 사용하여 문제를 선의 배열에 대한 동등한 질문으로 변환하고 오일러의 다면체 공식을 사용하여 답할 수 있습니다. Leroy Milton Kelly의 또 다른 증거는 다른 점과 0이 아닌 거리가 가장 작은 연결선이 반드시 정규적이어야 한다는 것을 모순으로 보여줍니다. 그리고 이전에 스타인버그의 증명에 이어 H. S. M. 콕서터는 갈라이와 켈리의 증명에 나타나는 기울기와 거리의 메트릭 개념이 불필요하게 강력하다는 것을 보여주었고, 대신 질서 기하학의 공리만을 사용하여 정리를 증명했습니다.

켈리의 증명

이 증명은 르로이 밀턴 켈리의 것입니다. Aigner & Ziegler (2018)는 이 정리의 많은 증명 중 "단순히 최고"라고 부릅니다.^[7]

점들의$$ 유한 집합 $S{\displaystyle }$ ${\displaystyle$ S$}$가 모두 공선이 아니라고 가정하자. 연결선을 집합에서 두 개 이상의 점을 포함하는 선으로 정의합니다. $유한$하게 S ${\displaystyle S}$에는 점 P ${\displaystyle$ P$}$ 및$$연결선 ℓ${\displaystyle \$ell}이(가) 양의 거리이지만 다른 모든 점선 쌍보다 가깝습니다. 켈리는$$ℓ {\displaystyle \ell$}$이(가) 정상임을 모순으로 증명했습니다.

ℓ$${\$displaystyle$\ell}이(가) 정상이 아니라고 가정합니다. Then it goes through at least three points of ${\displaystyle S}$. At least two of these are on the same side of ${\displaystyle P'}$, the perpendicular projection of ${\displaystyle P}$ on ${\displaystyle \ell }$. Call them ${\displaystyle B}$ and ${\displaystyle C}$, $B{\displaystyle }$ ${\displaystyle B}$이${\displaystyle {(}^{}}$가) $'$ {\$displaystyle$ P$'}$에 가장 가깝습니다.$$ Draw the connecting line ${\displaystyle m}$ passing through ${\displaystyle P}$ and ${\displaystyle C}$, and the perpendicular from ${\displaystyle B}$ to ${\displaystyle B'}$ on ${\displaystyle m}$ . Then ${\displaystyle BB'}$ is shorter than ${\displaystyle PP'}$. This follows from the fact that ${\displaystyle PP'C}$ and ${\displaystyle BB'C}$ are similar triangles, one contained inside the other.^[7]

그러나 이는 $P$ ${\displaystyle P}$ 및$$ℓ${\displaystyle \$ell}을(를) 양의 거리가 가장 작은 점선 쌍으로 정의한 원래 정의와 모순됩니다. 따라서$$ℓ {\displaystyle$$\ell}이(가) 정상이 아니라는 가정은 성립할 수 없습니다. QED

멜키오르의 증명

1941년 (따라서, Erd ő들이 질문과 갈라이의 후속 증거를 발표하기 전에) Melchior는 사영 평면에 있는 어떤 사소한 유한한 선 배열도 적어도 세 개의 평범한 점을 가지고 있다는 것을 보여주었습니다. 이중성에 의해, 이 결과는 평면상의 임의의 유한한 중요하지 않은 점들의 집합이 적어도 세 개의 통상적인 선들을 갖는다는 것을 의미합니다.^[8]

Melchior는 실제 사영 평면에 포함된 그래프에 대해 공식 $V{\displaystyle }$- ${\displaystyle E}$+ ${\displaystyle F}$ ${\displaystyle V-E+F}$가 사영 평면의 오일러 특성인$$$1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$과 같아야 한다는$$ 것을 관찰했습니다. 여기서 $V{\displaystyle }$ ${\displaystyle V$ $E{\displaystyle }$ ${\displaystyle E}$및 $F{\displaystyle }$ ${\displaystyle F}$는 각각 그래프의 정점, 모서리 및 면의 개수입니다. 사영 평면에 있는 모든 중요하지 않은 선 배열은 각 면이 최소 3개의 모서리로 경계지어지고 각 모서리가 2개의 면으로 경계지어지는 그래프를 정의합니다. 따라서 이중 계산은 $추가적$인${\displaystyle \mathrm{부등식}F\mathrm{}}$ $≤$ 2 E / 3 {\$displaystyle$ F\$leq 2E/3}$을 제공합니다$.$ 이 $부등식$을 사용하여 오일러 특성에서$$ F ${\displaystyle$ F$}$를 제거하면 부등식 $E{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle 3}$ ${\displaystyle \mathrm{V}}$- ${\displaystyle 3}$ ${\displaystyle E\leq 3V-3}$이 됩니다$.$ 그러나 배열의 모든 정점이 세 개 이상의 선의 교차점이라면 총 간선 수는 최소 $3{\displaystyle \mathrm{}}$ ${\displaystyle V}$ ${\displaystyle 3V}$이 됩니다$.$ 이 불평등에 모순되는 것입니다. 따라서 일부 정점은 두 선의 교차점이어야 하며, Melchior의 보다 신중한 분석에서 알 수 있듯이 부등식 $E{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle 3}$ V${\displaystyle }$- ${\displaystyle 3}$ ${\displaystyle E\leq 3V-3}$을 만족하려면 최소 3개의 일반 정점이 필요합니다$.$^[8]

Aigner & Ziegler (2018)가 지적한 바와 같이, 일반 정점의 존재에 대한 동일한 주장은 1944년 Norman Steenrod에 의해 제시되었고, 그는 이를 이중 일반 선 문제에 명시적으로 적용했습니다.^[9]

멜키오르 부등식

비슷한 주장으로 멜키오르는 좀 더 일반적인 결과를 증명할 수 있었습니다. $모든$ $k$ ≥ 2 ${\displaystyle$k$\backslash$geq 2}에 대해 k {\$displaystyle$t_{k}}를 k ${\displaystyle$ k}개의 선이 $입사$되는$$점의 개수라고$$합니다. 그러면^[8].

${\displaystyle \displaystyle \sum _{k\geq 2} (k-3)t_{k}\leq -3.}$

혹은 그에 상응하는,

${\displaystyle \displaystyle t_{2}\geqslant 3+\sum _{k\geq 4}(k-3)t_{k}.$

공리학

H. S. M. 콕서터(H. S. M. Coxeter, 1948, 1969)는 "아몬드를 깨기 위해 썰매 망치를 사용하는 것과 같이" 유클리드 거리를 사용하는 것이 불필요하게 강력하다는 켈리의 증명을 썼습니다. 대신, 콕서터는 유클리드 기하학뿐만 아니라 여러 다른 관련 기하학을 포함하는 중간성의 관점에서 기하학의 공리화인 순서 기하학 내의 실베스터-갈라이 정리에 대한 또 다른 증거를 제시했습니다.^[10] 콕서터의 증명은 1944년 스타인버그가 제시한 초기의 증명을 변형한 것입니다.^[11] 정리를 증명하는 데 필요한 최소 공리 집합을 찾는 문제는 역수학에 속합니다. 이 문제에 대한 연구는 팜부치안(2009)을 참조하십시오.

실베스터-갈라이 정리의 일반적인 진술은 건설적인 분석에서 타당하지 않습니다. 왜냐하면 그것은 건설적인 수학의 공리로서 거부되는 배제된 중간의 법칙의 약화된 형태인 전지전능의 덜 제한된 원리를 의미하기 때문입니다. 그럼에도 불구하고, 구성적 분석의 공리 안에서 유효한 실베스터-갈라이 정리의 버전을 공식화할 수 있고, 켈리의 정리 증명을 이 공리 안에서 유효한 증명으로 적용하는 것이 가능합니다.^[12]

일반 선 찾기

켈리의 평범한 선의 존재에 대한 증명은 다른 두 점을 통해 점과 선의 가장 가까운 쌍을 검색하여 평범한 선을 찾는 알고리즘으로 바뀔 수 있습니다. Mukhopadhyay & Green(2012)은 모든 세 개의 점에 대한 단순한 검색을 기반으로 이 가장 가까운 쌍 검색 시간을 $O{\displaystyle ({n\mathrm{}}^{}}$ 3${\displaystyle {}^{}}$ ${\displaystyle$ O$(n^{3})}$로 보고하지만$,$ $O{\displaystyle ({n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$ ${\display O(n^{2}}$ 시간에 주어진 두 점을 통해 각 선에 가장 가까운 주어진 점을 찾는 알고리즘을 기반으로 합니다$.$ 에델스브루너 & Guibas(1989)는 주어진 점 집합 중 3개에 의해 결정되는 최소 면적 삼각형을 찾기 위한 서브루틴으로서 앞서 제시했습니다. 에델스브루너 & Guibas (1989)의 동일한 논문은 (Melchior와 Steenrod의 증명에서 사용된 것처럼) 주어진 점에 대한 선의 이중 배열을 동시에 구성하는 방법도 ${\displaystyle {보여줍니다\mathrm{}}^{}.}$ ${\displaystyle {}^{}}$(n$2$) {\$display O(n$^{2$\})\}.$ 이로부터 모든 정규 정점과 모든 정규 선을 식별할 수 있습니다. Mukhopadhyay, Agrawal & Hosabettu(1997)는 시간 $O{\displaystyle (n}$ ${\displaystyle \log }$ ⁡$n$) ${\displaystyle$ O(n$\$log n)}에서 하나의 일반 선(꼭 Kelly의 증명에서 나온 것은 아님)을 찾는 방법을 처음 보여주었고, Mukhopadhyay & Green(2012)은 동일한 시간 제한을 가진 더 간단한 알고리즘을 설명했습니다.

Mukhopadhyay & Green(2012)의 알고리즘은 순서 기하학을 사용한 Coxeter의 증명을 기반으로 합니다. 다음 단계를 수행합니다.

1. 주어진 점의 볼록한 선체의 꼭지점인 점 $p{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$을 선택합니다.
2. $p$ 0 {\$displaystyle$p_{0}}을$$통과하고 볼록한 선체 외부에 머무르는 선$$ℓ 0 ${\displaystyle \ell$ _{0}}을 구성합니다.
3. ${\displaystyle {다른\mathrm{}}_{}}$ 주어진 점들을 p 0 {\$displaystyle$ p_${0$과의 각도로 정렬하여 같은 각도를 이루는 점들을 그룹화합니다$.$
4. 점들 중 하나가 해당 그룹에 단독으로 있는 경우, 해당 점을 통해 일반 ${\displaystyle {선}_{}}$을$$반환하고 p 0 {\$displaystyle$p_$\{$0}}.
5. 각 두 개의 연속적인 점 그룹에 대해 각도에 따라 정렬된 순서로 두 개의 선을 형성하며, 각 선은 한 그룹에서$$ ${\displaystyle {p\mathrm{}}_{}}$ $0{\displaystyle {}_{}}$ ${\$에 가장 가까운 점을 통과하고 다른 그룹에서는$$ p ${\displaystyle {0\mathrm{}}_{}}$ ${\$에 가장 먼 점을 통과합니다.
6. 이렇게 형성된 선 집합에서 각 선$$ℓ i ${\displaystyle \ell_${i}에 대해$$ℓ$0${\displaystyle \ell_{i}$$ℓ i${\displaystyle$ \${$i}의 ${\displaystyle {교차점}_{}}$을 찾습니다.
7. ℓ$0$ {\$displaystyle \ell_$${$i}}과의 교차점이 p 0 {\displaystyle p_{0}에 가장 가까운 선 ℓ i {\$displaystyle$ \ell_{i}}를 반환합니다.

저자들이 증명하듯이, 이 알고리즘에 의해 반환되는 선은 반드시 정상이어야 합니다. 증명은 4단계까지 반환되는 경우 구축에 의해 수행되거나 7단계까지 반환되는 경우 모순에 의해 수행됩니다. 7단계에서 반환되는 선이 정상적이지 않은 경우, 저자는 점들 중 하나와 p$$ {\$displaystyle p_{0}}$ 사이에 정상적인 선이 존재함을 증명합니다$.$ 그러나 이 줄은 이미 4단계에서 발견되어 반환되었어야 합니다.^[13]

보통줄의 수

실베스터-갈라이 정리는 모든 점들이 일직선이 아닌 점들의 배열이 정규선을 결정해야 한다고 말하지만, 얼마나 많은 점들이 결정되어야 하는지는 말하지 않습니다. $t{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$( ${\displaystyle n}$) ${\displaystyle t_{2}(n)}$를 n$${\$displaystyle n$}개의$$ 비선점 집합에 대해 결정된 최소 일반 선 개수라고$$ 가정합니다. Melchior의 증명에 따르면 $t$ ${\displaystyle 2_{}}$($n)$≥$$3 {\$displaystyle t_{2}($n$)\backslash$geq 3}. de Bruijn과 Erd ő(1948)는 t 2 (n$) {\displaystyle$ t_{2}(n)}가$n$ $\{\backslash$displaystyle n}으로$무한대$에$$접근하는지에 ${\displaystyle \mathrm{대한}{}_{}}$문제를 제기했습니다. Theodore Motzkin (1951) confirmed that it does by proving that ${\displaystyle t_{2}(n)\geq {\sqrt {n}}}$. Gabriel Dirac (1951) conjectured that ${\displaystyle t_{2}\geq \lfloor n/2\rfloor }$, for all values of ${\displaystyle n}$, a conjecture that still stands as of 2013^[update]. 이는 종종 디랙-모츠킨 추측(Dirac-Motzkin 추측)이라고도 합니다. 예를 들어 Brass, Moser & Pach(2005, 페이지 304)를 참조하십시오. Kelly & Moser(1958)는 ${\displaystyle t2{}_{}}$(${\displaystyle n)}$ ≥ 3$n$ / 7 {\$displaystyle$t_{2}($n)\geq$3n/7}임을 증명했습니다.

디랙의$$ 추측된 $하한$은$$4보다 큰 $짝수$ n {\$displaystyle{\displaystyle {}_{}}$n$}$이 일치하는 ${\displaystyle {상한\mathrm{}}_{}\mathrm{t2}}$ $)$ ≤ n / 2 ${\displaystyle$t_{2}(n)\$leq n/2}$을 가지므로 점근적으로 가능한 최선입니다$.$ 이 구성은 Karoly Böröczky로 인해, 이 경계를 달성하는 것은 실제 사영 평면에서 $일반적$인 m$${\$displaystyle m}$ -gon의 정점과 정점 쌍에 의해 결정되는 각 방향에 해당하는 무한대의 라인에서 $다른$ m ${\displaystyle m}$ $점$(thus를 들어, ${\displaystyle n}$ =$$2 m {\displaystyle n = 2 m})으로 구성됩니다. 이러한 점에는 $m{\displaystyle (\mathrm{m}}$- 1${\displaystyle )/2\mathrm{}}$ ${\displaystyle$ m$(m-1)/2}$ 쌍이$$ 있지만 m ${\displaystyle$ m$}$의 서로 다른 방향만 결정합니다. 이 배열에는 $정점{\displaystyle }$ v ${\displaystyle v}$와 무한대의 점을 연결하는 선이 $v{\displaystyle }$ ${\displaystyle v}$의 두 이웃과 동일선을 이루는 m개의 ${\$displaystyle $m}$개의$$ 일반 선만 있습니다$.$ 실제 사영 평면의 유한 구성과 마찬가지로 이 구성은 일반 선의 수를 변경하지 않고 모든 점이 유한하도록 교란될 수 있습니다.^[14]

홀수 $n$ ${\displaystyle$ n$}$의 경우$,$ dirac의 하한 추측과 일치하는 두 가지 예, 즉 ${\displaystyle t_{}}$ 2${\displaystyle {}_{}}$(${\displaystyle n)}$ = ${\displaystyle (n}$-$$1 ) / 2 {\displaystyle t_{2}(n) = (n-1)/2} 한 예는 Kelly & Moser (1958)에 의해 정점, 에지 중간점으로 구성됩니다. 정삼각형의 중심; 이 7개의 점들은 단지 세 개의 평범한 선들을 결정합니다. 이 세 개의 일반적인 선들이 하나의 선으로 대체되는 구성은 유클리드 평면에서는 실현될 수 없으며, 파노 평면으로 알려진 유한 사영 공간을 형성합니다. 이러한 연결 때문에 Kelly-Moser 예제는 Non-Fano 구성이라고도 불립니다.^[15] 다른 반례는 McKee로 인해 ^[14]두 개의 일반 오각형이 사영 평면에서 무한대의 선 위에 있는 점과 공유 모서리의 중간점과 함께 가장자리에서 가장자리로 연결된 두 개의 일반 오각형으로 구성됩니다. 이 13개의 점은 그 중 6개의 일반 선을 포함합니다. Böröczky의 구성을 수정하면 ${\displaystyle 3개}$의 ⌊ n$/4개$의 ⌋ {\$displaystyle$ 3$\lfloor$ n/4\rfloor}개의 일반 선이 있는 홀수 점 집합이 생성됩니다.

Csima & Sawyer(1993)는 n ${\displaystyle$ n}이 7인 $경우를$제외하고 $t$ ${\displaystyle 2_{}}$ ${\displaystyle {}_{}n)}$≥ ⌈ ${\displaystyle 6}$ n${\displaystyle }$/ $13$ ⌉ ${\displaystyle$ t_{2}($n)\geq \lceil$6n/13\rceil}$임$을 증명했습니다. 점근적으로 이 공식은 이미 ${\displaystyle 12/13}$ ≈$$92.3% {\$displaystyle$ 12/$13\proxy$ 92입니다.입증된 $n{\displaystyle /2\mathrm{}}$ ${\displaystyle$ n$/2}$ $상한$의 3$\%}$입니다. $n$ = ${\$displaystyle n = 7}인 경우는 예외입니다. 그렇지 않으면 Kelly-Moser 구조가 반례이기 때문입니다. 구조는 t (7) ≤ 3 {\display t(7)\leq 3}임을 보여줍니다. 그러나 Csima-Sawyer 경계가 n = 7 {\displaystyle n = 7}에 대해 유효한지, ${\displaystyle {t2}_{}}$(${\displaystyle 7)}$은$$≥ 4 {\$displaystyle$t_{2}($7$geq 4}이라고 주장합니다.

밀접하게 관련된 결과는 벡의 정리로, 소수의 점이 있는 선의 수와 한 선의 점의 수 사이의 균형을 나타냅니다.^[17]

Ben Green and Terence Tao showed that for all sufficiently large point sets (that is, ${\displaystyle n>n_{0}}$ for some suitable choice of ${\displaystyle n_{0}}$), the number of ordinary lines is indeed at least ${\displaystyle n/2}$. Furthermore, when ${\displaystyle n}$ is odd, 어떤 상수 $C{\displaystyle }$ ${\displaystyle C}$에 대해$$일반 선의 수는 최소 ${\displaystyle \mathrm{3n}/4}$- C ${\displaystyle 3n/4-C}$입니다$.$ 따라서 짝수 및 홀수에 대한 Böröczky의 구성(위에서 논의됨)이 가장 잘 가능합니다. 일반 선의 수를 최소화하는 것은 3점 선의 수를 최대화하는 과수원 심기 문제와 밀접한 관련이 있으며, Green과 Tao도 충분히 큰 모든 점 집합에 대해 해결했습니다.^[18] 일반 점을 찾는 이중 설정에서는 의사선 배열에서 일반 점의 최소 개수를 고려할 수 있습니다. 이러한 맥락에서 ${\displaystyle \mathrm{Csima-Sawyer}}$⌈ 6n$/13$⌉${\displaystyle \lceil$ 6n/13\rceil} 하한은 여전히 유효하지만 녹색 및${\displaystyle }Tao$ $n/2 {\$displaystyle n/2} 바인딩이 여전히 유지되는지 여부는 알 수 없습니다.

연결선의 수

폴 에르트 ő스가 관찰한 바와 같이, 실베스터-갈라이 정리는 공선이 아닌 $n개의${\display n}개의$$점 $집합$이 적어도$n개의 {\display$ n}개의 다른 선을 결정한다는 것을 즉시 암시합니다. 이 결과는 드 브루인-에르드 ő 정리로 알려져 있습니다. 기본 케이스로 $n$ = ${\$$displaystyle$ n = 3}에 대해 결과가 분명히 참입니다. n$${\$displaystyle$ n$}$ 값이 더 큰 경우, 결과는 n {\displaystyle n} 포인트에서 n - 1 {\displaystyle n-1} 포인트로 감소될 수 있습니다. 일반적인 선과 그 위에 있는 두 점 중 하나를 삭제함으로써(나머지 부분집합이 한 선 위에 놓일 점을 삭제하지 않도록 주의). 따라서 수학적 귀납법이 뒤따릅니다. $n{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle n-1}$개의$$ 공선 점과 다른 점과 동일한 선에 있지 않은 하나의 추가 점의 집합인 근연필의 예는 이 경계가 엄격함을 보여줍니다.^[16]

일반화

실베스터-갈라이 정리는 유클리드 평면의 유색 점 집합과 대수적으로 또는 미터 공간의 거리로 정의된 점과 선의 시스템으로 일반화되었습니다. 일반적으로 정리의 이러한 변형은 일반적인 선이 없는 유클리드 평면의 모든 점의 집합과 같은 예를 피하기 위해 유한한 점 집합만을 고려합니다.

유색점

1960년대 중반에 로널드 그레이엄(Ronald Graham)이 제기하고 도날드 J. 뉴먼(Donald J. Newman)이 대중화한 실베스터 문제의 변형은 두 가지 색상이 주어진 유한한 평면 점 집합(모두 한 줄에 있지는 않음)을 고려하고 모든 이러한 집합이 동일한 두 개 이상의 점을 통과하는 선을 갖는지 여부를 묻습니다. 집합과 집합의 언어에서 이와 동등한 문장은 유한 점 집합의 공선 부분집합의 집합은 (한 줄에 모두 있는 것은 아님) 속성 B를 가질 수 없다는 것입니다. 이러한 변이에 대한 증명은 시어도어 모츠킨에 의해 발표되었지만 발표된 적은 없었으며, 최초로 발표된 증명은 채커리언(Chakerian, 1970)에 의해 발표되었습니다.^[20]

비실점좌표

유클리드 평면 또는 사영 평면이 점의 좌표(유클리드 평면의 경우 데카르트 좌표, 사영 평면의 경우 동차 좌표)에 실수를 사용하여 정의할 수 있는 것처럼 점과 선의 유사한 추상 체계는 다른 수 체계를 좌표로 사용하여 정의할 수 있습니다. 실베스터-갈라이 정리는 유한한 필드 위에서 이러한 방식으로 정의된 기하학에는 적용되지 않습니다. 파노 평면과 같이 이러한 방식으로 정의된 일부 유한한 기하학의 경우 기하학의 모든 점의 집합에는 정규 선이 없습니다.^[7]

실베스터-갈라이 정리는 점들이 복소수 또는 4차수의 쌍인 좌표를 갖는 기하학에도 직접 적용되지 않지만, 이러한 기하학은 더 복잡한 정리의 유사성을 갖습니다. 예를 들어 복소 사영평면에는 헤세의 구성(입방 곡선의 변곡점)인 9개의 점으로 구성되어 있으며, 모든 선은 실베스터-갈라이 정리를 위반합니다. 이러한 구성은 실베스터-갈라이 구성으로 알려져 있으며 유클리드 평면의 점과 선으로는 실현할 수 없습니다. 실베스터-갈라이 정리를 진술하는 또 다른 방법은 실베스터-갈라이 구성의 점이 유클리드 공간에 삽입되어 공선성을 보존할 때마다 점이 모두 한 줄에 놓여야 하며 헤세 구성의 예는 복잡한 사영 평면에 대해 거짓임을 보여줍니다. 그러나 켈리(1986)는 실베스터-갈라이 정리의 복소수 유사체를 증명했습니다. 실베스터-갈라이 구성의 점이 복잡한 사영 공간에 삽입될 때마다 점은 모두 2차원 하위 공간에 있어야 합니다. 마찬가지로, 3차원 복소 공간에서 점들의 집합은 전체 공간이 아핀 선체인 점들은 반드시 법선을 가져야 하며, 사실은 법선의 개수가 선형이어야 합니다.^[21] 마찬가지로, Elkies, Pretorius & Swanpoel (2006)은 실베스터-갈라이 구성이 4차원에 걸쳐 정의된 공간에 삽입될 때마다 그 점이 3차원 하위 공간에 있어야 한다는 것을 보여주었습니다.

매트로이드

유클리드 평면의 모든 점들과 그 점들을 연결하는 선들은 랭크-3 지향 매트로이드의 요소들과 평면들로 추상화될 수 있습니다. 실수 이외의 다른 수 체계를 사용하여 정의된 기하학의 점과 선 또한 매트로이드를 형성하지만, 반드시 방향성을 갖는 매트로이드는 아닙니다. 이러한 맥락에서 Kelly & Moser(1958)의 일반 선 수 하한 결과는 $n개$의 ${\displaystyle n}$ 요소가$$ 있는 모든 랭크-3 배향 마트로이드는 ${\displaystyle \mathrm{최소}}$ 3n${\displaystyle /7\mathrm{}}${\$displaystyle 3n/7}$ 2점$$ 선을 가지며, 또는 이와 동등하게 2점 선이 적은 모든 순위-3 매트로이드는 방향을 잡을 수 없어야 합니다.^[22] 두 점 선이 없는 매트로이드를 실베스터 매트로이드라고 합니다. 이와 관련하여, 7개의 점과 단지 3개의 일반적인 선을 가진 Kelly-Moser 구성은 GF(4)를 대표하는 마트로이드의 금지된 미성년자 중 하나를 형성합니다.^[15]

거리기하학

실베스터-갈라이 정리를 임의의 메트릭 공간으로 일반화하는 또 다른 방법은 Chvátal(2004)에 의해 추측되었고 Chen(2006)에 의해 증명되었습니다. 이 일반화에서는 이 점들에 대한 삼각형 부등식이 등식일 때 미터법 공간에서 점들의 3배가 공선인 것으로 정의하고, 이미 선에 추가된 점들과 공선인 점들을 더 이상 추가할 수 없을 때까지 반복적으로 포함함으로써 어떤 점 쌍으로부터도 선을 정의합니다. Chvátal과 Chen의 일반화는 모든 유한 미터 공간은 모든 점을 포함하거나 정확히 두 점을 포함하는 선을 가지고 있다고 말합니다.^[23]

메모들

참고문헌

외부 링크

• Malkevitch, Joseph (2003), "A discrete geometrical gem", AMS Feature Column, American Mathematical Society, archived from the original on 2006-10-10
• Weisstein, Eric W., "Ordinary Line", MathWorld
• 2013년 미네르바 강연에서 테렌스 타오의 증명 발표