난제 작업실

하나의 난제, 세 번의 몰입

이야기에서 내 추측까지

난제 이야기는 호기심을 여는 입구이고, 난제 작업실은 그 호기심을 검증 가능한 생각으로 발전시키는 다음 장소입니다.

  1. 1 · 발견질문 만나기언제 태어나 왜 아직 사람을 붙잡는지 이야기로 이해합니다.
  2. 2 · 도전한 사례 시험하기그림·계산·색칠로 5분 안에 내 첫 관찰을 만듭니다.
  3. 3 · 발전지금 여기생각 이어 붙이기관찰을 공개하고 다른 시도와 비교해 추측·반례·부분 풀이로 키웁니다.
Week 21 · MathOverflow미해결
1차 출처

다항 허시 추측 — 다포체의 지름은 다항식인가

연구급· 제기 1957

문제

dd차원 유계 볼록 다포체가 *nn개 면(facet)을 가질 때, 그래프 지름(한 꼭짓점에서 다른 꼭짓점까지의 최단 모서리 경로 길이)이 n,dn, d의 다항식*으로 유계인가?

Klee–Walkup 1967. 강한 형태 *≤n−d\le n - d (Hirsch 1957)는 Santos 2010에서 반증*됨.

왜 흥미로운가

Simplex method 효율의 진짜 이유는 다포체 지름이 작기 때문이라 추정됨. 최악 케이스 지름 Δ(d,n)\Delta(d, n)의 진짜 성장률은 50년 미해결. Klee–Minty 1972 cubes: simplex가 *2d2^d pivot을 요구할 수 있지만 그래프 자체의 지름은 작음. 다항 허시는 조합론 + 다포체 기하 + 최적화가 만나는 교차로. 해답이 다항이면 — 선형계획법의 진정한 다항 시간 알고리즘* 가능성.

현재까지의 진척

Santos 2010-12-08 (arXiv) — 43차원 86-facet 다포체가 *Hirsch 추측 86−43=4386-43=43을 초과하는 지름 44 발견 → 강한 Hirsch 반증. Kalai–Kleitman 1992*: Δ(d,n)≤n1+log⁡2d\Delta(d, n) \le n^{1 + \log_2 d} — 50년 가장 좋은 상한. Todd 2014가 Δ(d,n)≤(n−d)log⁡2d\Delta(d, n) \le (n-d)^{\log_2 d}로 미세 개선.

더 읽기

💡 한 줄부터 함께 탐구하기(0건)

참여를 인기 순으로 등급화하지 않습니다. 큐레이터는 무엇이 명료하고 재현 가능한지 말하고, 동료 신호는 누군가 이해했거나 직접 따라 해봤다는 뜻입니다.

무엇을 발견했나요?

완전한 풀이가 아니어도 좋습니다. 작은 관찰 하나가 다음 탐구의 길을 엽니다.

마크다운 + KaTeX 지원 (`$x^2$` 인라인, `$$\sum_{k=1}^n k$$` 디스플레이)
0 / 3000자

모더레이션 정책을 확인해 주세요. 로그인하면 다른 기기에서도 이 시도를 이어서 편집·삭제할 수 있습니다.

불러오는 중…

연결된 개념

  • 조합론

    다포체 그래프 지름의 조합 구조 — vertex 사이 최단 경로 길이

  • 선형계획법

    simplex method 효율의 진짜 이유가 다포체 지름과 직결 — 다항 지름이면 다항 시간 알고리즘 가능성

  • 최적화

    선형계획법은 본질적으로 다포체 vertex traversal — 지름이 곧 worst-case