This is a good article. Click here for more information.

Turán의 벽돌 공장 문제

Turán's brick factory problem

수학에 타결되지 않은 문제:

어떤 완전한 이분 그래프는 수 Zarankiewicz에 의해 주어지는 것보다 더 적은 지역을 암시할 수 있나요?

(수학에 더 해결되지 않은 문제).
K4,7의 18지역( 빨간 점들)을 가진 최적의 그림 그리기,.

그래프 그림의 수학에서, Turán의 벽돌 공장 문제 지역의 완전한 양분 그래프의 그림 속의 최소 숫자를 묻는다.문제는 Pál Turán 한 반면, 벽돌 공장 2차 세계 대전 당시 일하도록 강요 받는 그것을 발견이 붙여진 것이다.[1]

그림. 방법 카지미에시 Zarankiewicz에 의해 발견되는 모든 완전한 bipartite 그래프에 대한 정확한 대답을 해 주기 위해 이 성명이 이 진실이 아니다 Zarankiewicz을 건너수 추측에 불과하고 알려진 것으로 추측하고 있다.이런 추측, 단지 약간의 특별한 경우 함께 열려 있다.[2]

기원과 형성

세계 대전 동안, 헝가리 수학자 Pál Turán 벽돌 공장에서 근무하기 위해 저장 사이트에 벽돌 가마에서 장식이나 쿠션 하중 추진하고 수밖에 없었다.공장에는 각 가마에서 각 보관 장소까지 선로가 있었고, 선로가 교차하는 지점에서는 왜건을 밀기가 더 어려웠습니다.Turan은 이 상황에서 영감을 얻어 이 [1]선로들 사이의 교차로를 최소화하기 위해 공장을 어떻게 재설계할 수 있는지 물었습니다.

수학적으로 이 문제는 완전한 이분 그래프의 그래프화를 요청하는 것으로 공식화할 수 있습니다. 정점은 가마 및 저장 장소를 나타내고 가장자리는 각 가마에서 각 저장 장소까지의 트랙을 나타냅니다.그래프는 각 정점을 점으로, 각 모서리를 두 끝점을 연결하는 곡선으로 평면에 그려야 하며, 입사하지 않은 모서리에 정점을 배치하지 않아야 합니다.그래프에서 분리된 두 모서리가 평면에 비어 있지 않은 교차점을 가질 때마다 교차가 카운트됩니다.그렇다면 문제는, 그러한 [2][3]도면의 최소 교차 수는 몇 개인가 하는 것입니다.

이 문제의 Turán의 형성은 종종 하나의 그래프의 그 도하의 숫자가 첫 연구로 인정 받고 있다같은 개념의[4](또 다른 독립 공식화 사회학, sociograms,[5]고 많은 나이 든 퍼즐 그림 그리기 위한 메서드로 발생한다, 3전력 회사 문제, th등과 함께 벽돌 공장 문제에 대한 특별한 경우로 볼 수 있다.리 가마 및 3개의 저장 시설).[6]교차 숫자는 그래프[7] 드로잉의 중심 연구 대상이자 VLSI 설계[8] 및 이산 [9]기하학에서 중요한 도구로서 그 이후로 더욱 중요해졌다.

어퍼를 묶었다

Zarankiewicz와 Kazimierz Urbanik는 Turan이 1952년 [3]폴란드에서 열린 여러 회담에서 벽돌 공장 문제에 대해 말하는 것을 보고,[10][11] 이 문제에 대한 동일한 공식과 함께 시도된 해결책을 독립적으로 발표했다.둘 다 보여주었듯이, 완전한 이분m,n 그래프 K(한쪽에 m개의 정점, 다른 쪽에 n개의 정점, 그리고 양쪽을 연결하는 mn개의 모서리를 가진 그래프)를 다음과 같은 수의 교차로 그릴 수 있다.

구조는 간단합니다. 원점을 피하여 평면의 x축에 m개의 정점을 배치하고 Y축의 왼쪽과 오른쪽에 점의 개수가 같거나 거의 동일합니다.마찬가지로 원점을 피하여 평면의 Y축에 정점 n개를 X축 위와 아래에 동일하거나 거의 동일한 수의 점을 배치합니다.그런 다음 X축의 모든 점을 직선 세그먼트로 Y축의 [3]모든 점에 연결합니다.

그러나 이 공식이 최적이라는, 즉 교차가 적은 도면이 있을 수 없다는 그들의 증거는 잘못된 것이었다.이 차이는 출판된 지 11년이 지나서야 발견되었는데, 거의 동시에 게르하르트 링겔과 폴 카이넨이 [12]이를 발견했다.그럼에도 불구하고, Zarankiewicz와 Urbanik의 공식은 최적이라고 추측된다.이것은 Zarrankiewicz 교차 번호 추측으로 알려지게 되었다.일부 특수한 경우가 사실로 알려져 있지만, 일반적인 경우는 아직 [2]미결로 남아 있습니다.

경계를 낮추어라

K와n,m K는 동형이기 때문에m,n m n n인 경우를 고려해도 충분하다.또한, 2m²의 경우, 자란키에비치의 구조는 교차로를 제공하지 않으며, 이는 물론 최선이 될 수 없다.따라서 m과 n이 둘 다 ≤ 3인 경우는 중요하지 않다.

Zarankiewicz의 추측에 대한 시도 증거는 K의m,n 일반적인 경우 무효이지만, 사례 m = 3에는 효과가 있다.이후 m의 다른 작은 값으로 확장되었으며, m ≤ [13]6의 완전한 초당 그래프m,n K에 대해 Zarankiewicz 추측이 참인 것으로 알려져 있다.이 추측은 K, K7,8, [14]K에도7,9 맞는7,7 것으로 알려져 있다.반례가 존재하는 경우, 즉 자란키에비치 한계보다 적은 교차가 필요한 그래프m,n K는 최소 반례에서 [13]m과 n 모두 홀수여야 한다.

각 고정 선택 m에 대해, 모든m,n K에 대한 추측의 진위는 제한된 수의 선택 [15]n만을 테스트함으로써 검증될 수 있다.보다 일반적으로 모든 완전한 초당 그래프는 (충분히 큰 그래프의 경우) 자란키에비치 한계에서 주어진 숫자의 83% 이상의 교차를 필요로 한다는 것이 입증되었다.이 하한과 상한 사이의 간격을 좁히는 것은 여전히 해결되지 않은 문제입니다.[16]

건널목 숫자 있는 한 직선

모서리를 임의 곡선이 아닌 직선 세그먼트로 그려야 하는 경우 일부 그래프에서는 곡선 모서리로 그릴 때보다 더 많은 교차가 필요합니다.그러나 완전한 초당 그래프의 교차 번호에 대해 Zarankiewicz가 설정한 상한을 직선 에지만 사용하여 달성할 수 있다.따라서 Zarankiewicz 추측이 맞다면 완전한 초당 그래프는 교차 [17]번호와 동일한 직선 교차 번호를 갖는다.

레퍼런스

  1. ^ a b 를 클릭합니다Turán, P. (1977), "A note of welcome", Journal of Graph Theory, 1: 7–9, doi:10.1002/jgt.3190010105.
  2. ^ a b c 를 클릭합니다Pach, János; Sharir, Micha (2009), "5.1 Crossings—the Brick Factory Problem", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 126–127.
  3. ^ a b c 를 클릭합니다Beineke, Lowell; Wilson, Robin (2010), "The early history of the brick factory problem", The Mathematical Intelligencer, 32 (2): 41–48, doi:10.1007/s00283-009-9120-4, MR 2657999, S2CID 122588849.
  4. ^ 를 클릭합니다Foulds, L. R. (1992), Graph Theory Applications, Universitext, Springer, p. 71, ISBN 9781461209331.
  5. ^ Bronfenbrenner, Urie (1944), "The graphic presentation of sociometric data", Sociometry, 7 (3): 283–289, doi:10.2307/2785096, JSTOR 2785096, The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines.
  6. ^ Bóna, Miklós(2011년), AWalkCombinatorics을 통해:.도입된 열거형과 그래프 이론, 세계 과학,를 대신하여 서명함. 275–277, 아이 에스비엔 9789814335232.Bóna 우편 275에, 그리고"비행기 표면에 건널목 없이 K3,3는 것의 문제에 해당합니다"페이지의 주 277에 쓴다 퍼즐(3주택의 세 우물과 연결될 수 있는)을 소개한다.
  7. ^ Schaefer, Marcus (2014), "The graph crossing number and its variants: a survey", The Electronic Journal of Combinatorics: #DS21
  8. ^ Leighton, T. (1983), Complexity Issues in VLSI, Foundations of Computing Series, Cambridge, MA: MIT Press
  9. ^ Székely, L. A. (1997), "Crossing numbers and hard Erdős problems in discrete geometry", Combinatorics, Probability and Computing, 6 (3): 353–358, doi:10.1017/S0963548397002976, MR 1464571
  10. ^ 를 클릭합니다Zarankiewicz, K. (1954), "On a problem of P. Turan concerning graphs", Fundamenta Mathematicae, 41: 137–145, doi:10.4064/fm-41-1-137-145, MR 0063641.
  11. ^ 에서 인용한Urbaník, K. (1955), "Solution du problème posé par P. Turán", Colloq. Math., 3: 200–201 바와 같이
  12. ^ 를 클릭합니다Guy, Richard K. (1969), "The decline and fall of Zarankiewicz's theorem", Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, pp. 63–69, MR 0253931.
  13. ^ a b 를 클릭합니다Kleitman, Daniel J. (1970), "The crossing number of K5,n", Journal of Combinatorial Theory, 9: 315–323, doi:10.1016/s0021-9800(70)80087-4, MR 0280403.
  14. ^ 를 클릭합니다Woodall, D. R. (1993), "Cyclic-order graphs and Zarankiewicz's crossing-number conjecture", Journal of Graph Theory, 17 (6): 657–671, doi:10.1002/jgt.3190170602, MR 1244681.
  15. ^ 를 클릭합니다Christian, Robin; Richter, R. Bruce; Salazar, Gelasio (2013), "Zarankiewicz's conjecture is finite for each fixed m", Journal of Combinatorial Theory, Series B, 103 (2): 237–247, doi:10.1016/j.jctb.2012.11.001, MR 3018068.
  16. ^ 를 클릭합니다de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. (2006), "Improved bounds for the crossing numbers of Km,n and Kn", SIAM Journal on Discrete Mathematics, 20 (1): 189–202, arXiv:math/0404142, doi:10.1137/S0895480104442741, MR 2257255, S2CID 1509054.
  17. ^ Kainen, Paul C. (1968), "On a problem of P. Erdős", Journal of Combinatorial Theory, 5 (4): 374–377, doi:10.1016/s0021-9800(68)80013-4, MR 0231744

외부 링크