Erdős 별개의 거리 문제

이산형 기하학에서 Erdős 별개의 거리 문제는 평면의 모든 점 집합이 거의 선형에 가까운 수의 별개의 거리를 갖는다고 말한다.1946년^[1][2] 폴 에르디스가 포즈를 취했고 2015년 래리 거스와 네츠 캣츠가 거의 입증했다.^[3][4][5]

추측

다음에 나오는 항목에서 g(n)는 평면에서 n개의 점 사이의 구별되는 거리의 최소 수를 나타내거나 거리 집합에서 가능한 가장 작은 카디널리티를 동등하게 나타내도록 한다.1946년 논문에서 Erdss는 그 추정치를 증명했다.

${\displaystyle {\sqrt {n-3/4}-1/2\leq g(n)\leq cn/{\sqrt {\logn}}$

$어떤{\displaystyle }$ 상수 c ${\displaystyle c}$에 대해$.$하한선은 쉬운 논쟁에 의해 주어졌다.상한은 $n{\displaystyle \sqrt{}}$ ${\displaystyle \times }$ ${\displaystyle n\sqrt{}}$ ${\$제곱$$ 격자로 지정된다.이러한 그리드의 경우, 큰 O 표기법으로 표현되는 두 제곱의 $합인$ O${\displaystyle }$($n/{\sqrt{\log$ n})보다 작은 $O{\displaystyle }$ (n${\displaystyle }$/ ${\displaystyle \sqrt{\log }}$ $){\displaystyle$ O$(n/{\$sqrt{\log n})의 숫자가$$ 있다. 란도-라마누잔 상수를 참조한다.Erdős는 상한선이 g(n)의 참 값에 가까웠으며, 특히 (큰 오메가 표기법 $사용{\displaystyle }$) g${\displaystyle }$(${\displaystyle n}$) =${\displaystyle \mathrm{\Omega }}$(${\displaystyle n^{}}$) ${\displaystyle g(n)=\Oomega(n^{c})}$가 모든 c < 1을 보유한다고 추측했다.

부분 결과

Paul Erdős의 1946년 하한 g(n) = Ω(n^1/2)은 다음과 같이 연속적으로 개선되었다.

• g(n) = 1952년 Leo Moser by Ω(n^2/3)^[6]
• g(n) = 1984년 팬청 기준 Ω(n^5/7)^[7]

• g(n) = 팬청, 엔드레 스제메르디, 윌리엄 T의 Ω(n/log^4/5 n) 1992년 ^[8]트로터
• g(n) = 1993년^4/5 Laszlo A. Székeley by Laszlo A. Székley,^[9]
• g(n) = Ω(n) by Jozsef Solymosi and Csaba^6/7 D.2001년 ^[10]토스
• g(n) = 2003년 Gabor Tardos by ^[11]Ω(n^{(4e/(5e − 1)) − ɛ})
• g(n) = Ω(n^{((48 − 14e)/(55 − 16e)) − ɛ}) by Nets Katz and Gabor Tardos by 2004,^[12]
• g(n) = 2015년 래리 거스와 네츠 캣츠의 Ω(n/log n)^[3]

상위 치수

Erdds는 또한 문제의 고차원 변형을 고려했다: $d{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 3}$ ${\displaystyle d\geq$ 3$}$의 경우 $g{\displaystyle }$ ${\displaystyle {}_{}n}$) ${\displaystyle g_{d}(n)$은 d ${\displaystyle d}$ -차원$$ 유클리드 공간에 $있는{\displaystyle }$ n ${\displaystystyle n}$ 포인트$$ 사이의 가능한 최소 고유 거리 수를 나타낸다$$.He proved that ${\displaystyle g_{d}(n)=\Omega (n^{1/d})}$ and ${\displaystyle g_{d}(n)=O(n^{2/d})}$ and conjectured that the upper bound is in fact sharp, i.e., ${\displaystyle g_{d}(n)=$$\theta (n^{2/d$ Jozsef Solymosi와 Van H.Vu는 2008년에 $하한{\displaystyle {}_{}}$ ${\displaystyle g_{}}$(${\displaystyle n}$ ${\displaystyle )}$= ${\displaystyle \mathrm{\Omega }}$(${\displaystyle {n\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$/ d${\displaystyle {}^{}}$- ${\displaystyle 2^{}}$/ ${\displaystyle {\mathrm{d}}^{}}$ /${\displaystyle d^{}}$ (${\displaystyle {\mathrm{d}}^{}}$+ 2)$){\d$ 스타일 $g_{d}=\Oomega (n^2/d-2/d+2)}$를 획득했다.^[13]

참고 항목

• 팰커의 추측
• Erd problems 단위 거리 문제

참조

외부 링크

• 윌리엄 가스아치의 문제 페이지