벡의 정리 (기하학)

이산기하학에서 벡의 정리는 몇 가지 다른 결과 중 하나이며, 그 중 두 개는 다음과 같습니다. 둘 다 다른 중요한 정리들과 함께 요제프 벡(József Beck)의 유명한 논문에 등장했습니다.^[1] 아래에 설명된 두 가지 결과는 주로 평면의 점 집합에 의해 결정되는 선의 수에 대한 하한에 관한 것입니다. (최소 두 점 이상의 점 집합을 포함하는 선은 해당 점 집합에 의해 결정된다고 합니다.)

에르트 ő스-벡 정리

Erd ős-Beck 정리는 L. M. Kelly와 W. O. J. Moser에 의한 고전적인 결과의 변형으로, 약 0 < k < O( √n)에 대해 최대 n - k 점의 구성이 공선입니다. 그들은 n이 k에 대해 충분히 크다면 구성이 적어도 kn - (1/2) (3k + 2) (k - 1) 선에 걸쳐 있음을 보여주었습니다.^[3]

Elekes와 Csaba Toth는 Erd ős-Beck 정리가 더 높은 차원으로 쉽게 확장되지 않는다고 언급했습니다. R에서³ 두 개의 꼬임선 위에 놓인 2n개의 점들의 집합을 예로 들어 보자. 이 두 선은 각각 n개의 점에 대한 입사선이라고 가정합니다. 점들의 그러한 구성은 단지 2n개의 평면에 걸쳐 있습니다. 따라서^d R의 점 집합에 대한 가설의 사소한 확장만으로는 원하는 결과를 얻을 수 없습니다.

이 결과는 Erd ő스에 의해 처음 추측되었고 Beck에 의해 증명되었습니다 (정리 5.2 in. 참조).

진술

S를 평면상 n개의 점들의 집합이라 하자. 0 ≤ k < n - 2 정도의 어떤 선 위에 n - k개 이하의 점이 놓여 있으면, S의 점에 의해 결정되는 ω(nk)개의 선이 존재합니다.

증명

벡 정리

벡의 정리에 따르면 평면에 있는 유한한 점들의 집합은 두 극단 중 하나에 해당합니다. 하나는 많은 부분의 점들이 하나의 선 위에 놓여 있고, 하나는 모든 점들을 연결하기 위해 많은 선들이 필요한 것입니다.

Beck의 논문에는 언급되지 않았지만, 이 결과는 Erd ős-Beck 정리에 의해 암시됩니다.

진술

이 정리는 양의 상수 C, K의 존재를 주장하므로 평면상의 임의의 n개의 점이 주어지면 다음 문장 중 적어도 하나가 참입니다.

n/C 이상의 점을 포함하는 선이 있습니다.
$n^{2}/K$ 의 / $n^{2}/K$ $n^{2}/K$ 개의 $n^{2}/K$ 선이 있으며, 각 선에는 두 개 이상의 점이 포함되어 있습니다.

Beck의 원래 주장에서 C는 100이고 K는 불특정 상수입니다. C와 K의 최적값이 무엇인지 알 수 없습니다.

증명

벡 정리의 증명은 다음과 같이 주어질 수 있습니다. 평면에서 n개의 점으로 이루어진 집합 P를 생각해 보자. j를 양의 정수라고 합니다. A와 B를 연결하는 선이 $2^{j}$ {\ $displaystyle$ 2 $^{j}}$ 와 $2^{j}$ $2^{j+1}-1$ $2^{j+1}-1$ - $2^{j+1}-1$ {\ $displaystyle$ 2 $^{j+1}-1}$ 개의 $2^{{j+1}}-1$ P(A와 B 포함) 지점을 포함하는 경우 집합 P의 한 쌍의 점 A, B가 j-연결되었다고 가정합니다.

Szemerédi–Troter 정리에서, 이러한 선의 수는 $O(n^{2}/2^{3j}+n/2^{j})$ 2 $O(n^{2}/2^{3j}+n/2^{j})$ / $O(n^{2}/2^{3j}+n/2^{j})$ j $O(n^{2}/2^{3j}+n/2^{j})$ + $O(n^{2}/2^{3j}+n/2^{j})$ / $O(n^{2}/2^{3j}+n/2^{j})$ $O(n^{2}/2^{3j}+n/2^{j})$ $O(n^{2}/2^{3j}+n/2^{j}$ 이며 $O(n^{2}/2^{3j}+n/2^{j})$ 다음과 같습니다. n개의 점으로 이루어진 집합 P와 P의 $2^{j}$ {\ $displaystyle 2^{$ j $2^{j}$ }} $2^{j}$ 이상을 포함하는 P의 점 쌍에 걸쳐 있는 모든 선의 집합 L을 생각해 보십시오. 어떤 두 점도 두 개의 구별되는 $|L|\cdot {2^{j} \choose 2}\leq {n \choose 2}$ L 위에 놓일 수 없으므로 $|L|\cdot {2^{j} \choose 2}\leq {n \choose 2}$ $|L|\cdot {2^{j} \choose 2}\leq {n \choose 2}$ ⋅ $|L|\cdot {2^{j} \choose 2}\leq {n \choose 2}$ 2 j $|L|\cdot {2^{j} \choose 2}\leq {n \choose 2}$ ) $≤$ (n 2) {\ $displaystyle L \cdot {2$ ^{ $j}$ \ $선택 2}\leq$ { $n$ \선택 2}. 이제 Szemerédi–Troter 정리를 사용하여, 따라서 P와 L 사이의 발생 수는 $O(n^{2}/2^{2j}+n)$ O $O(n^{2}/2^{2j}+n)$ $O(n^{2}/2^{2j}+n)$ / $O(n^{2}/2^{2j}+n)$ j $O(n^{2}/2^{2j}+n)$ + $O(n^{2}/2^{2j}+n)$ ) $O(n^{2}/2^{2j}+n)$ 입니다 $O(n^{2}/2^{2j}+n)$ j-연결된 점들을 연결하는 모든 선들도 L에 위치하고, 각각은 적어도 $2^{j}$ ${\$ 2 $^{j}$ 개의 $2^{j}$ 사건들에 기여합니다. 따라서 이러한 선의 총 $O(n^{2}/2^{3j}+n/2^{j})$ 는 O $O(n^{2}/2^{3j}+n/2^{j})$ 2 $O(n^{2}/2^{3j}+n/2^{j})$ / $O(n^{2}/2^{3j}+n/2^{j})$ j $O(n^{2}/2^{3j}+n/2^{j})$ + n $O(n^{2}/2^{3j}+n/2^{j})$ / $O(n^{2}/2^{3j}+n/2^{j})$ j $O(n^{2}/2^{3j}+n/2^{j})$ ) $O(n^{2}/2^{3j}+n/2^{j}$ 입니다 $O(n^{2}/2^{3j}+n/2^{j})$

이러한 각 선은 $\Omega (2^{2j})$ ω $\Omega (2^{2j})$ 22 $\Omega (2^{2j})$ j) ${\displaystyle \Omega($ 2^{2j})} 쌍의 점을 연결하므로 $O(n^{2}/2^{j}+2^{j}n)$ O( $O(n^{2}/2^{j}+2^{j}n)$ / $O(n^{2}/2^{j}+2^{j}n)$ $O(n^{2}/2^{j}+2^{j}n)$ + 2 $O(n^{2}/2^{j}+2^{j}n)$ j n) ${\displaystyle O(n^{2}/2^{j}+$ 2^{j}n)} 쌍의 점을 j-연결할 수 있음을 알 수 있습니다.

이제 C를 큰 상수라고 가정해 보겠습니다. 기하 급수를 합하면 $C\leq 2^{j}\leq n/C$ $C\leq 2^{j}\leq n/C$ $C\leq 2^{j}\leq n/C$ $C\leq 2^{j}\leq n/C$ $C\leq 2^{j}\leq n/C$ $C\leq 2^{j}\leq n/C$ / C ${\displaystyle$ C $\leq 2^{j}\leq n/C}$ 를 만족하는 일부 j에 대해 j 연결된 점 쌍의 수는 최대 $O(n^{2}/C)$ $O(n^{2}/C)$ / C $O(n^{2}/C)$ ) ${\displaystyle$ O $(n^{2}/C)}$ 임을 $C\leq 2^{j}\leq n/C$ 알 수 있습니다 $O(n^{2}/C)$

반면, 총 쌍의 ${\frac {n(n-1)}{2}}$ 는 ${\frac {n(n-1)}{2}}$ - 1 ${\frac {n(n-1)}{2}}$ 2 ${\$ 입니다 ${\frac {n(n-1)}{2}}$ 따라서 C를 충분히 크게 선택하면 어떤 $C\leq 2^{j}\leq n/C$ $C\leq 2^{j}\leq n/C$ $C\leq 2^{j}\leq n/C$ $C\leq 2^{j}\leq n/C$ $C\leq 2^{j}\leq n/C$ n $C\leq 2^{j}\leq n/C$ / C $C\leq 2^{j}\leq n/C$ 에 대해서도 j-연결되지 않은 적어도 $n^{2}/4$ $n^{2}/4$ / $n^{2}/4$ 4 $n^{2}/4$ 쌍을 $n^{2}/4$ 찾을 수 있습니다 $C\leq 2^{j}\leq n/C$ 이 쌍들을 연결하는 선들은 2C 미만의 점들을 통과하거나 n/C 이상의 점들을 통과합니다. 만약 후자의 경우가 이 쌍들 중 하나라도 성립한다면, 우리는 벡 정리의 첫 번째 결론을 얻게 됩니다. 따라서 $n^{2}/4$ 의 2 $n^{2}/4$ $n^{2}/4$ 쌍 $n^{2}/4$ 모두가 2C 미만의 점을 통과하는 선으로 연결되어 있다고 가정할 수 있습니다. 그러나 이러한 각 선은 최대 $C(2C-1)$ C $C(2C-1)$ - $C(2C-1)$ ${\displaystyle C(2$ C-1 $)}$ 쌍의 $C(2C-1)$ 점을 연결할 수 있습니다. 따라서 최소 n개의 2/4 C ( $n^{2}/4C(2C-1)$ C $n^{2}/4C(2C-1)$ - $n^{2}/4C(2C-1)$ ${\displaystyle n^{2}/4$ C (2 $C-1)}$ 개의 선이 두 개 이상 연결되어 $K=4C(2C-1)$ 하며, $K=4C(2C-1)$ = $K=4C(2C-1)$ $K=4C(2C-1)$ ( $K=4C(2C-1)$ $K=4C(2C-1)$ - $K=4C(2C-1)$ 1) {\displaystyle K = 4 C (2 C-1)}를 사용하여 클레임을 수행합니다.

참고문헌

^ ^a ^b Beck, József (1983). "On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry". Combinatorica. 3 (3–4): 281–297. doi:10.1007/BF02579184. MR 0729781. S2CID 31011939.
^ "William O. J. Moser".
^ Kelly, L. M.; Moser, W. O. J. (1958), "On the number of ordinary lines determined by n points", Can. J. Math., 10: 210–219, doi:10.4153/CJM-1958-024-6, S2CID 123865536, archived from the original on 2011-08-07, retrieved 2010-03-12
^ Elekes, György; Tóth, Csaba D. (2005). "Incidences of not-too-degenerate hyperplanes". Proceedings of the twenty-first annual symposium on Computational geometry. Pisa, Italy: Annual Symposium on Computational Geometry. pp. 16–21. doi:10.1145/1064092.1064098. ISBN 1-58113-991-8. S2CID 9617907.
^ 벡 정리는 k = n(1 - 1/C)으로 하고 에르트 ő스-벡 정리를 적용하면 유도할 수 있습니다.

[becks-paper-1] Beck, József (1983). "On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry". Combinatorica. 3 (3–4): 281–297. doi:10.1007/BF02579184. MR 0729781. S2CID 31011939.

[2] "William O. J. Moser".

[3] Kelly, L. M.; Moser, W. O. J. (1958), "On the number of ordinary lines determined by n points", Can. J. Math., 10: 210–219, doi:10.4153/CJM-1958-024-6, S2CID 123865536, archived from the original on 2011-08-07, retrieved 2010-03-12

[4] Elekes, György; Tóth, Csaba D. (2005). "Incidences of not-too-degenerate hyperplanes". Proceedings of the twenty-first annual symposium on Computational geometry. Pisa, Italy: Annual Symposium on Computational Geometry. pp. 16–21. doi:10.1145/1064092.1064098. ISBN 1-58113-991-8. S2CID 9617907.

[5] 벡 정리는 k = n(1 - 1/C)으로 하고 에르트 ő스-벡 정리를 적용하면 유도할 수 있습니다.

[1]

[3]

v t 발생구조
대표성	입사행렬 발생 그래프
필드	조합론 블록설계 슈타이너 시스템 기하학. 인시퀀스 사영평면 그래프이론 하이퍼그래프 통계학 막는
구성	완전 사각형 판오평면 뫼비우스-칸토르 구성 파퍼스 구성 헤세 구성 디세그즈 구성 Reye 구성 슐레플리 더블 식스 크레모나-리치먼드 구성 쿠머 구성 Grünbaum–Rigby 구성 클라인 구성 듀얼
정리	실베스터-갈라이 정리 드 브루인-에르트 ő 정리 세메레디-트로터 정리 벡 정리 브루크 라이저 초울라 정리
적용들	실험설계 커크먼의 여학생 문제

Search

벡의 정리 (기하학)

네임스페이스

더

목차

에르트 ő스-벡 정리

진술

증명

벡 정리

진술

증명

참고문헌