정점 삽입 시 피라미드 너비(Pyramidal Width)가 증가할 수 있음
요약
다면체에 정점을 추가할 때 피라미드 너비(pyramidal width)가 증가할 수 없다는 기존의 추측을 반박하는 연구입니다. 6개의 정수 점을 이용한 구체적인 반례를 제시하여 정점 삽입이 피라미드 너비를 증가시킴을 증명했습니다.
핵심 포인트
- Lacoste-Julien과 Jaggi의 기존 추측에 대한 반례 제시
- 3차원 공간 내 6개의 정수 점을 활용한 수학적 증명
- 피라미드 너비와 면 거리(facial distance) 사이의 등가성 활용
- 정확한 검증기(exact verifier)를 논문에 함께 제공
Lacoste-Julien과 Jaggi는 2015년에 모든 기존 점이 정점으로 유지된다는 조건 하에, 다면체(polytope)에 정점(vertex)이 추가되더라도 피라미드 너비(pyramidal width)는 증가할 수 없다고 추측했습니다. 우리는 $\R^3$ 공간 내의 6개 정수 점을 이용한 정확한 반례를 제시합니다.
[ P=\conv{v_0,\ldots,v_4},\qquad Q=\conv{v_0,\ldots,v_5}, ]
여기서
[ \begin{aligned} v_0&=(-1,-3,-1), & v_1&=(3,2,-2), & v_2&=(0,2,1),\ v_3&=(-1,-3,3), & v_4&=(-2,0,1), & v_5&=(-1,0,-2), \end{aligned} ]
일 때, $P$의 다섯 개 정점은 모두 $Q$의 정점으로 유지되지만,
[ \PWidth(P)^2=\frac{48}{353} \quad\text{and}\quad \PWidth(Q)^2=\frac{36}{133} ]
입니다. 따라서 정점 삽입은 피라미드 너비를 $\sqrt{1059/532}\approx 1.410886779$ 배만큼 증가시킵니다. 이 증명은 피라미드 너비와 면 거리(facial distance) 사이의 등가성을 사용하며, 정수 지지 초평면(integer supporting hyperplanes)을 통해 두 면 격자(face lattices)를 인증하고, 유한한 유리수 계산을 통해 모든 면 거리를 평가합니다. 논문에는 의존성이 없는 정확한 검증기(exact verifier)가 함께 제공됩니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기