철썩철썩

Thrackle

스랙클은 각 가장자리가 요르단 호이고 모든 가장자리 쌍이 정확히 한 번 일치하도록 평면에 그래프를 내장한 것이다.가장자리는 공통 끝점에서 만날 수도 있고, 공통적인 끝점이 없는 경우 내부 지점에서 만날 수도 있다.후자의 경우 횡방향으로 교차해야 한다.[1]

선형 스래클

라인하르트 폴리곤 4개.그들의 직경(파란색)은 선형 스패클을 형성한다.

선형 스래클은 가장자리가 직선 세그먼트인 방식으로 그려진 스래클이다.모든 선형 스랙클에는 정점만큼 많은 가장자리가 있는데, 이 사실은 폴 에르디스에 의해 관찰되었다.Erdős는 정점 v가 세 개 이상의 에지 vw, vx 및 vy에 선형 스랙클에서 연결된 경우, 이러한 에지 중 적어도 하나는 다른 두 에지를 구분하는 선에 놓여 있다고 관찰했다. 일반성을 잃지 않고 vw가 선 vw에 의해 경계를 두고 닫힌 반경간에 놓여 있는 x와 y가 그러한 에지라고 가정한다.그러면 ww 이외의 에지는 vx와 vy 둘 다 건드릴 수 없기 때문에 w는 도 1이 있어야 한다.철망에서 w를 제거하면 가장자리와 꼭지점 사이의 차이를 바꾸지 않고 더 작은 철망이 생성된다.반면에, 모든 꼭지점에 최대 두 개의 이웃이 있는 경우, 악수하는 보조정리기로 가장자리 수는 최대 정점의 수입니다.[2]Erdős의 증거를 바탕으로, 모든 선형적인 트라클이 사이비 숲이라는 것을 유추할 수 있다.홀수 길이의 모든 사이클은 선형 스래클을 형성하도록 배열될 수 있지만, 이것은 짝수 길이 사이클의 경우 가능하지 않다. 사이클의 한쪽 가장자리가 임의로 선택되면 다른 사이클 정점이 이 에지를 통과하는 선의 반대편에 번갈아 놓여져야 하기 때문이다.

Micha Perles는 선형 스패클에서 모든 에지는 끝점이 있고 가장 각도가 최대 180°이고 이 범위 내에서 가장 시계방향인 끝점이 있다는 사실에 기초하여 선형 스패클이 최대 가장자리 n개까지 가지고 있다는 또 다른 간단한 증거를 제공했다.그렇지 않다면, 가장자리의 반대쪽 끝점에 대한 사고와 가장자리를 통해 선의 반대편에 놓여 있는 두 개의 가장자리가 있을 것이고, 이것은 서로를 가로지를 수 없다.그러나 각 꼭지점에는 단일 가장자리와 관련된 이 속성만 있을 수 있으므로 가장자리 수는 최대 정점의 수와 동일하다.[3]

Erdős 또한 관찰했듯이, 점 집합의 직경을 실현하는 점 쌍들은 선형 스래클을 형성해야 한다. 두 직경은 서로 분리될 수 없다. 만약 그것들이 그들의 네 개의 끝점이라면 두 개의 분리된 가장자리보다 더 먼 거리에 쌍이 있을 것이기 때문이다.이러한 이유로, 비행기의 모든 n개의 점들은 1934년 하인츠 홉프와 에리카 판위츠가 제기한 질문에 답하면서 최대 n개의 직경 쌍을 가질 수 있다.[4]Andrew Vazsonyi는 이 문제를 일반화하면서 더 높은 차원의 지름 쌍의 수에 대한 한계를 추측했다.[2]

계산 기하학에서, 회전 캘리퍼스는 점의 볼록한 선체에 접하는 평행선을 지지하는 점 쌍을 연결함으로써 볼록한 위치의 어떤 점 집합으로부터 선형 스래클을 형성하는 데 사용될 수 있다.[5]이 그래프에는 직경 쌍의 전열이 하위 그래프로 포함되어 있다.[6]

라인하르트 폴리곤의 직경은 선형 스패클을 형성한다.직경에 상대적인 최대 면적을 가진 n-곤을 찾는 가장 큰 작은 폴리곤 문제를 해결하기 위해 선형 스랙의 열거형을 사용할 수 있다.[7]

트라클 추측

수학의 미해결 문제:

스랙클이 정점보다 더 많은 모서리를 가질 수 있는가?

(수학에서 더 풀리지 않은 문제)
6사이클 그래프를 포함하는 스패클.

존 H. 콘웨이는 어떤 격투에서든 가장자리 수가 정점의 수와 최대 동일하다고 추측했다.콘웨이 자신은 (각각 가장자리와 꼭지점에 대해) 용어 경로와 지점을 사용했기 때문에, 콘웨이의 스패클 추측은 원래 모든 스패클이 최소한 경로만큼의 지점을 갖는 형태로 명시되었다.콘웨이는 콘웨이의 99그래프 문제, 댄저 세트의 최소 간격, 16세트의 이동 이후 실버 코인지 우승자 등 일련의 시상 문제의 일부로서 이러한 추측을 증명하거나 반증하는 대가로 1000달러의 상금을 제공했다.[8]

마찬가지로, 모든 격투는 사이비 숲이기 때문에 격투 추측이 명시될 수 있다.좀 더 구체적으로 말하면, 만약 철통 같은 추측이 사실이라면 철통 같은 이 철통들은 정확히 우달의 결과로 특징지어질 수 있다: 그들은 길이 4의 주기가 없고 기껏해야 한 번의 홀수 주기가 있는 사이비 숲이다.[1][9]

C를4 제외한 모든 사이클 그래프에는 스크래클 임베딩이 있어 추측이 날카롭다는 것이 증명됐다.즉, 경로와 같은 수의 지점을 가진 격투가 있다.다른 극단에서 최악의 시나리오는 지점 수가 경로 수의 두 배라는 것이다. 이 또한 달성할 수 있다.

철썩철썩한 추측은 모든 가장자리가 x-모노톤 곡선이 될 정도로 그려진 철썩철썩한 것에 대해 사실인 것으로 알려져 있다.[3]

알려진 한계

로바스, 파치 & 세게디(1997)는 모든 초당파적 난투극이 평면적으로 그려지지는 않았지만 평면 그래프라는 것을 증명했다.[1]그 결과, 정점이 n개 있는 모든 스러클링 가능한 그래프는 최대 2n - 3개의 가장자리를 갖는다는 것을 보여준다.이후 이 바운드는 여러 차례 개선됐다.첫째, 3(n - 1)/2로 개선되었고,[10] 또 다른 개선으로 인해 약 1.428n의 경계선이 되었다.[11]더욱이 후자의 결과를 증명하기 위해 사용된 방법은 ε > 0에 대해 한정된 알고리즘을 산출하는데, 이 알고리즘은 (1 + ))n에 대한 구속을 개선하거나 추정을 반증한다.현재 기록은 풀렉&파치(2017년)가 1.3984n으로 바운드 증명했기 때문이다.[12]

만약 추측이 틀렸다면, 최소의 counteexample은 정점을 공유하는 두 개의 짝수 사이클의 형태를 가질 것이다.[9]따라서, 그 추측을 증명하기 위해서는, 이런 유형의 그래프를 트라클로서 그릴 수 없다는 것을 증명하는 것으로 충분할 것이다.

참조

  1. ^ a b c Lovász, L.;Pach, J.;Szegedy, M.(1997년),"콘웨이의thrackle 추측이라고 전제하며", 이산과 해석 기하학, 18(4):369–376, doi:10.1007/PL00009322, MR1476318.이런 결과 중 예비 버전 O'Rourke, J.(1995년),"계산기 하학 칼럼 26", ACMSIGACT 뉴스, 26(2):15–17, arXiv:cs/9908007, doi:10.1145/202840.202842에서 호평을 받았다
  2. ^ a b Erdős, P. (1946), "On sets of distances of n points" (PDF), American Mathematical Monthly, 53 (5): 248–250, doi:10.2307/2305092, JSTOR 2305092.
  3. ^ a b Pach, János; Sterling, Ethan (2011), "Conway's conjecture for monotone thrackles", American Mathematical Monthly, 118 (6): 544–548, doi:10.4169/amer.math.monthly.118.06.544, MR 2812285.
  4. ^ Hopf, H.; Pannwitz, E. (1934), "Aufgabe Nr. 167", Jahresbericht der Deutschen Mathematiker-Vereinigung, 43: 114.
  5. ^ Eppstein, David (May 1995), "The Rotating Caliper Graph", The Geometry Junkyard
  6. ^ 회전 캘리퍼 그래프에 모든 직경 쌍이 포함되어 있다는 사실은 을 참조하십시오.직경 쌍이 스래클을 형성한다는 사실은 예를 들어, Pach & Sterling(2011)을 참조한다.
  7. ^ Graham, R. L. (1975), "The largest small hexagon" (PDF), Journal of Combinatorial Theory, Series A, 18 (2): 165–170, doi:10.1016/0097-3165(75)90004-7.
  8. ^ Conway, John H., Five $1,000 Problems (Update 2017) (PDF), Online Encyclopedia of Integer Sequences, retrieved 2019-02-12
  9. ^ a b Woodall, D. R. (1969), "Thrackles and deadlock", in Welsh, D. J. A. (ed.), Combinatorial Mathematics and Its Applications, Academic Press, pp. 335–348, MR 0277421.
  10. ^ Cairns, G.; Nikolayevsky, Y. (2000), "Bounds for generalized thrackles", Discrete and Computational Geometry, 23 (2): 191–206, doi:10.1007/PL00009495, MR 1739605.
  11. ^ Fulek, R.; Pach, J. (2011), "A computational approach to Conway's thrackle conjecture", Computational Geometry, 44 (6–7): 345–355, arXiv:1002.3904, doi:10.1007/978-3-642-18469-7_21, MR 2785903.
  12. ^ Fulek, R.; Pach, J. (2017), "Thrackles: An improved upper bound", Graph Drawing and Network Visualization: 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers, Lecture Notes in Computer Science, vol. 10692, pp. 160–166, arXiv:1708.08037, doi:10.1007/978-3-319-73915-1_14, ISBN 978-3-319-73914-4.

외부 링크