허쉬 추측

Hirsch conjecture
추측이 사실인 Icosiddodecahedron의 그래프.

수학 프로그래밍과 다면 결합학에서 허쉬 추측이란 d차원 유클리드 공간에서 n-facet 폴리토프의 엣지-베르텍스 그래프가 n - d 이상 직경을 가지지 않는다는 것을 말한다.즉, 폴리토프의 어떤 두 꼭지점은 최대 n - d의 길이로 서로 연결되어야 한다.그 추측이 먼저 워렌 M의 편지에 실렸다. 허쉬와 [es] 조지 B. 1957년[1][2] 단치히(Dantzig)는 폴리토프의 직경이 심플렉스 방법에 필요한 스텝 수에 대한 하한을 제공하기 때문에 선형 프로그래밍에서 심플렉스 방법의 분석에 의해 동기 부여되었다.그 추측은 현재 일반적으로 거짓으로 알려져 있다.

허쉬 추측은 d < 4와 여러 가지 특수한 경우에 대해 입증된 반면,[3] 지름에 대해 가장 잘 알려진 상한은 n과 d에서 하한에 불과하다.[4]50여 년의 세월이 흐른 2010년 5월 칸타브리아 대학의 프란시스코 산토스 랄(Francisco Santos Leal)이 반례를 발표하였다.[5][6][7]그 결과는 시애틀에서 열린 100년: 클라이와 그룬바움의 수학 콘퍼런스에 발표되었고 수학 연보에 실렸다.[8]구체적으로 논문은 지름이 43이 넘는 86면체의 43차원 폴리토프를 제시했다.counterexample은 더 크지만 여전히 선형 또는 다항식 스텝 수의 가능성을 배제하지 않기 때문에 심플렉스 방법의 분석에 직접적인 결과는 없다.

d차원 유클리드 공간에서 어떤 2차원 면의 폴리토프의 직경이 d에 지나지 않는다는 d-step 추측과 같이 문제의 다양한 등가제형이 주어졌었다; 산토스 렐의 백록샘플 또한 이러한 추측을 반증한다.[1][9]

추측성명

볼록 폴리토프 의 그래프는 displaystyle P}의 정점이 P {\ P의 정점이 P {\의 해당 정점 두 개가 폴리토프의 에지와 결합되는 경우에만 에지로 결합되는 방식으로 daystyp가 그래프다.) 로 표시된P 의 직경은 그래프 중 하나의 직경이다.동일한 폴리토프의 어떤 두 개의 그래프는 그래프와 같이 이형성이어야 하기 때문에 이러한 정의는 잘 정의되어 있다.그러면 우리는 허쉬의 추측을 다음과 같이 진술할 수 있다.

추측 P}은는) 면적이 n개인 d차원 볼록 폴리토프다.그러면 ( )n - 디스플레이 스타일

예를 들어, 3차원의 큐브는 6개의 면을 가지고 있다.허쉬 추측에 따르면 이 입방체의 지름은 3보다 클 수 없다.추측을 수용하는 것은 입방체의 어떤 두 꼭지점이 최대 3단계를 사용하여 꼭지점에서 정점까지의 경로로 연결될 수 있다는 것을 의미한다.최소 8 치수의 모든 폴리탑에 대해, 이 바운드는 실제로 최적이다; 치수 ≥ 의 어떤 폴리토프도 n-d보다 작은 직경을 가지지 않으며, n은 이전과 같이 면의 수가 된다.[10]즉, 거의 모든 경우에 대해, 그 추측은 폴리토프의 가장자리를 따라 가는 경로에 의해 어떤 두 꼭지점(polytope)을 결합하는 데 필요한 최소의 스텝 수를 제공한다.심플렉스 방법은 기본적으로 실현 가능한 지역의 일부 꼭지점에서 최적 지점까지의 경로를 구성하여 작동하기 때문에, 허쉬 추측은 최악의 경우 심플렉스 방법이 종료되는 데 필요한 하한을 제공할 것이다.

허쉬 추측이란 다항식 허쉬 추측의 특수한 경우로서, 모든 P ,( )= O( ) 여기서 n은 P 면의 수이다.

진행 및 중간 결과

허쉬의 추측은 많은 경우에 대해 사실로 증명되었다.예를 들어 치수 3 이하인 모든 폴리토프는 추측을 만족시킨다.- 6과 같은 n 면의 d차원 폴리토프도 추측을 만족시킨다.[11]

그 추측을 해결하기 위한 다른 시도들은 허쉬의 추측을 암시하는 다른 문제를 공식화하려는 열망에서 나타났다.특히 중요한 예로는 d-step 추측이 있는데, 실제로 그것과 동등한 것으로 나타난 허쉬 추측의 이완이다.

정리 다음과 같은 진술은 동등하다.

  1. ) -d 스타일 모든 d차원 폴리포테 에 대한 n 면.
  2. ( ) d {\(P)\ d 2d 면의 모든 d차원 P 에 대한 Δ ( P )

즉, 허쉬 추측을 증명하거나 반증하기 위해서는 치수에 비해 정확히 두 배 많은 면을 가진 폴리토페스만을 고려할 필요가 있다.또 다른 중요한 이완은 Hirsch 추측이 모든 단순한 폴리에스테르를 보유하는 경우에만 모든 폴리에스테르를 보유한다는 것이다.[12]

백작샘플

팔면체는 스핀들의 대표적인 예 중 하나이다.

불행하게도 2011년 프란시스코 산토스에서 보듯이 허쉬의 추측이 모든 경우에 사실인 것은 아니다.산토스의 노골적인 백작 샘플 구축은 단순한 폴리토페즈만을 고려하도록 추측이 완화될 수 있다는 사실과 허쉬와 d-step 추측 사이의 동등함에서 비롯된다.[13]특히 산토스는 스핀들(spindles)이라고 불리는 특정 종류의 폴리토페스를 검사하여 그의 백범시료를 생산한다.

정의 d-spindle은 d-차원 P 이며, 에는 P{\의 모든 면에 이러한 두 정점 중 정확히 하나의 정점이 포함되도록 구별되는 정점 쌍이 존재한다.

이 두 꼭지점 사이의 최단 경로의 길이를 스핀들 길이라고 한다.허쉬 추측의 분산은 스핀들에 대한 강력한 d-step 정리라고 일컬어지는 다음과 같은 정리에 의존한다.

정리(산토스) 을(를) d-spindle로 한다.n은 그 면의 수가 되게 하고, 나는 그 길이가 되게 하라.그리고는(n− d){\displaystyle(n-d)}-spindle이 존재한다면, P′만약 내가>d{\displaystyle l>, d}, P2n− 2d{2n-2d\displaystyle}면과{\displaystyle P의}, 길이 아래 나는+n− 2d{\displaystyle l+n-2d}에 의해. 특히, 경계′{\displaystyle P의}은d-step 사기꾼을 위반한다.jectu리의

산토스는 그 후 길이 6의 5차원 스핀들을 계속 건설하고, 따라서 허쉬 추측에 대한 반증 역할을 하는 또 다른 스핀들이 존재한다는 것을 증명한다.이 두 개의 스핀들 중 첫 번째 스핀들은 48개의 면과 322개의 정점을 가지고 있는 반면, 추측을 실제로 반증하는 스핀들은 86개의 면을 가지고 있고 43차원이다.이 백례는 개방적인 문제로 남아 있는 다항식 허쉬 추측을 반증하지 않는다.[14]

메모들

  1. ^ a b 지글러(1994년), 페이지 84.
  2. ^ 단치히(1963), 페이지 160과 168.
  3. ^ 예: 0-1 폴리토페스는 Naddef(1989)를 참조한다.
  4. ^ Kalai & Kleitman (1992년).
  5. ^ 산토스(2011년).
  6. ^ 칼라이(2010년).
  7. ^ "Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch", Gaussianos, May 24, 2010
  8. ^ 산토스(2011년)
  9. ^ Klee & Walkup (1967년).
  10. ^ 지글러 (1994년)
  11. ^ 지글러 (1994년)
  12. ^ 지글러 (1994년)
  13. ^ 산토스(2011년)
  14. ^ 산토스(2011년)

참조