다면 결합제

다면 결합체학은 결합체와 이산 기하학 안에서 볼록 다면체와 고차원 볼록 다면체의 얼굴을 세고 설명하는 문제를 연구하는 수학의 한 분야다.

다면 결합술에 관한 연구는 두 가지 뚜렷한 영역으로 나뉜다. 예를 들어, 이 영역의 수학자들은 임의의 폴리에스테스 또는 특정 중요 폴리에스테스 하위 분류에서 정점, 가장자리 및 더 높은 차원의 얼굴 사이의 관계를 설명하는 불평등을 찾고, 그들의 연결과 같은 폴리에스테스의 다른 결합 특성을 연구한다.ivity와 직경(다른 정점으로부터 정점에 도달하는 데 필요한 단계 수). 또한, 많은 컴퓨터 과학자들은 정수 프로그래밍 문제에서 발생하는 특정 폴리토페스(특히 0-1 폴리토페스, 정점이 하이퍼큐브의 서브셋인)의 면에 대한 정확한 설명에 대한 연구를 설명하기 위해 "폴리알 콤비네틱스"라는 문구를 사용한다.

얼굴 및 얼굴 수 벡터

볼록 폴리토프 P의 면은 H의 경계가 P의 내부 점을 포함하지 않도록 P와 닫힌 반공간 H의 교차점으로 정의할 수 있다. 얼굴의 치수는 이 선체의 치수다. 0차원 면은 정점 그 자체로, 1차원 면(가장자리라고 함)은 정점 쌍을 연결하는 선 세그먼트다. 이 정의에는 빈 집합과 전체 폴리토프 P를 마주 보는 것도 포함된다. P자체가 치수 d를 갖는 경우 치수 d - 1을 갖는 P의 얼굴을 P의 면이라고 하고 치수 d - 2를 갖는 면을 능선이라고 한다.^[1] P의 얼굴은 상단 요소 P 그 자체로서 그리고 하단 요소인 빈 세트를 가지는 얼굴 격자를 형성하면서 포함에 의해 부분적으로 주문될 수 있다.

다면 결합술의 핵심 도구는 폴리토프의 ƒ-벡터,^[2] 벡터(f₀, f₁, ..., f_{d − 1})이며 여기서 f는_i 폴리토프의 i차원 형상의 수입니다. 예를 들어, 큐브는 정점 8개, 가장자리 12개, 면 6개를 가지고 있기 때문에 its-벡터는 (8,12,6)이다. 이중 폴리토프에는 역순으로 같은 숫자의 --벡터가 있으므로, 예를 들어 큐브에 대한 이중인 일반 옥타헤드론에는 ƒ-벡터(6,12,8)가 있다. 구성 매트릭스에는 대각선 원소로서 일반 폴리탑의 f-벡터가 포함된다.

확장된 --벡터는 --벡터의 각 끝에서 숫자 1을 연결하여 얼굴 격자의 모든 레벨에서 물체의 수를 세고, 벡터 왼쪽에서 f₋₁ = 1은 빈 세트를 면으로 세고, 오른쪽에서는_d f = 1은 P 자체를 세어 형성된다. 큐브의 경우 확장된 extended-벡터는 (1,8,12,6,1)이고, 팔면체의 경우 (1,6,12,8,1)이다. 이러한 예시 다면체의 벡터는 일면체(좌우 순서로 취해진 계수는 최대치로 증가했다가 감소함)이지만, 이는 사실이 아닌 고차원 다면체도 있다.^[3]

단순한 폴리토페스(모든 면이 심플렉스인 폴리토페스)의 경우, 이러한 벡터를 변환하는 것이 편리하여 h-벡터라고 하는 다른 벡터를 만들어 내는 경우가 많다. If we interpret the terms of the ƒ-vector (omitting the final 1) as coefficients of a polynomial ƒ(x) = Σf_ix^{d − i − 1} (for instance, for the octahedron this gives the polynomial ƒ(x) = x³ + 6x² + 12x + 8), then the h-vector lists the coefficients of the polynomial h(x) = ƒ(x − 1) (again, for the octahedron, h(x) = x³ + 3x² + 3x + 1).^[4] 지글러가 쓰듯이 "단순화된 폴리토페스에 관한 다양한 문제들에 대해 h-벡터는 ƒ-벡터보다 얼굴 번호에 대한 정보를 인코딩하는 훨씬 편리하고 간결한 방법이다."

평등과 불평등

폴리토프의 of-벡터 계수 중에서 가장 중요한 관계는 오일러의 공식 σ(-1)ⁱf_i = 0으로, 여기서 확장된 --벡터의 계수를 초과하는 합계 범위의 항이 있다. 3차원에서 확장 ƒ벡터(1, v, v, e, f, 1)의 좌우 끝에 있는 두 개의 1을 움직여 이 정체성을 보다 친숙한 형태 v - e + f = 2로 변환한다. 3차원 다면체의 각 면에 적어도 3개의 가장자리가 있다는 사실에서 2e ≥ 3f, 2e ≥ 3f, 2를 곱하여 계산한다. 그리고 이 불평등을 사용하여 오일러의 공식에서 e와 f를 제거하면 e ≤ 3v - 6과 f ≤ 2v - 4가 더 큰 불평등으로 이어진다. 이중성에 의해 e ≤ 3f - 6과 v ≤ 2f - 4가 된다. 이러한 평등과 불평등을 만족시키는 어떤 3차원 정수 벡터가 볼록한 다면체의 ƒ-벡터라는 것이 슈타인리츠의 정리로부터 따르게 된다.^[5]

더 높은 차원에서는 간단한 폴리토페스의 h-벡터_{kd − k} 단위로 표현되는 Dehn-Sommerville 방정식을 포함하여 폴리토페의 얼굴 수 사이의 다른 관계도 중요해진다. k = 0인 이 방정식의 예는 오일러의 공식과 동일하지만 d > 3의 경우 이 방정식의 다른 예들은 서로 선형적으로 독립되어 있으며, 추가적인 방법으로 h-벡터(따라서 --벡터)를 구속한다.^[4]

폴리토프 얼굴 수에 대한 또 다른 중요한 불평등은 상계 정리(McMullen(1970년)에 의해 주어지는데, 이 정리에서는 정점을 가진 d-차원 폴리토프는 정점의 수가 동일한 인접 폴리토프처럼 다른 차원의 최대 수만큼의 얼굴을 가질 수 있다고 명시하고 있다.

${\displaystyle f_{k-1}\leq \sum _{i=0}^{d/2}{}^{*}\왼쪽-i}{d-i}}{k-i}+{\binom {i}{k-d+i}\right){\binom {n-d-1},},}},},}$

여기서 별표는 d가 짝수일 때 합계의 최종 기간이 반감되어야 함을 의미한다.^[6] 점증적으로 이는 모든 차원의 최대 $O{\displaystyle ({}^d}$ d${\displaystyle {}^{}}$/ ${\displaystyle {2\mathrm{}}^{}}$ ) ${\$ 면들이$$ 있음을 의미한다.

4차원에서도 볼록폴록의 가능한 ƒ-벡터 집합은 4차원 정수 격자의 볼록한 부분집합을 형성하지 않으며, 이들 벡터의 가능한 값에 대해서는 많이 알려져 있지 않다.^[7]

그래프-이론적 특성

연구자들은 폴리토페스의 얼굴 수를 조사하는 것과 함께 폴리토페스의 정점과 가장자리에서 얻은 그래프의 설명과 같은 폴리토페스의 다른 결합 특성을 연구했다.

발린스키의 정리에는 어떤 d차원 볼록 폴립토프에서 이런 식으로 얻은 그래프가 d-베르텍스 연결돼 있다고 명시돼 있다.^[8] 3차원 다면체의 경우 다면체의 그래프를 정확하게 특성화하는 데 이 특성 및 평면성을 사용할 수 있다. 슈타인리츠의 정리에는 G가 3Vx로 연결된 평면그래프일 경우에만 G가 3차원 다면체의 골격이라고 명시되어 있다.^[9]

블라인드&마니레비츠카(1987)의 정리(이전의 미차 펄스가 추측한 것)는 단순한 폴리토프의 얼굴 구조를 그 그래프에서 재구성할 수 있다고 말한다. 즉, 주어진 비방향 그래프가 단순한 폴리토프의 골격이라면, 이것이 사실인 폴리토페는 단 한 개(결합성 등가까지)밖에 없다. 이것은 그래프가 완전한 그래프인 (단순하지 않은) 인접 폴리토페스와 극명한 대조를 이룬다; 동일한 그래프에 대해 많은 다양한 인접 폴리토페스가 있을 수 있다. 독특한 싱크 방향을 바탕으로 한 이 정리의 또 다른 증거는 칼라이(1988년)에 의해 제시되었고, 프리드먼(2009년)은 이 정리를 사용하여 그들의 그래프에서 간단한 폴리토페스의 얼굴 격자를 재구성하는 다항 시간 알고리즘을 도출하는 방법을 보여주었다. 그러나 주어진 그래프나 격자가 단순한 폴리토프의 얼굴 격자로 실현될 수 있는지를 시험하는 것은 (극성에 의해) 단순한 폴리토페스의 실현과 동등하며, 이는 아디프라시토&파드롤(2014년)에 의한 실존 이론에 대해 완결된 것으로 나타났다.

선형 프로그래밍을 위한 심플렉스 방법의 맥락에서, 폴리토프의 직경, 즉 다른 정점으로부터의 경로를 통해 어떤 정점에 도달하는 데 필요한 최소 에지 수를 이해하는 것이 중요하다. 선형 프로그램의 선형 불평등 시스템은 프로그램에 대한 모든 실현 가능한 해결책을 나타내는 폴리토프의 면을 정의하며, 심플렉스 방법은 이 폴리토프의 경로를 따라 최적의 해결책을 찾는다. 따라서 지름은 이 방법에 필요한 단계 수에 대한 하한을 제공한다. 지금 반증하고 있는 허쉬의 추측은 지름이 얼마나 클 수 있는가에 대해 강한 구속을 시사했다.^[10] 직경에 대한 약한 (준시-폴리노말) 상한이 알려져 있으며,^[11] 폴리토페의 특별한 등급에 대한 허쉬 추측의 증거도 알려져 있다.^[12]

계산 속성

주어진 폴리토프의 정점 수가 어떤 자연수 k에 의해 제한되는지 여부를 결정하는 것은 계산적으로 어려운 문제로서 복잡도 등급 PP에 대해 완성된다.^[13]

0-1 폴리토페스의 면

정수 프로그래밍이 결합 최적화 문제의 해법에 해당하는 정점을 갖는 폴리토페스의 면을 정확하게 설명할 수 있는 것은 절단면 방법의 맥락에서 중요하다. 종종 이러한 문제들은 이진 벡터로 설명할 수 있는 해결책을 가지고 있으며, 해당 폴리탑스는 모두 0이거나 1인 정점 좌표를 가지고 있다.

예를 들어, 순열 매트릭스의 볼록한 조합으로 형성될 수 있는 n × n 행렬의 집합인 Birkhoff polytope를 고려한다. 마찬가지로, 그것의 정점은 완전한 양분 그래프로 모든 완벽한 일치를 설명하는 것으로 생각할 수 있으며, 이 폴리토프의 선형 최적화 문제는 양분 최소 중량 완벽 일치 문제로 해석될 수 있다. 비르코프-본 노이만 정리는 이 폴리토프는 두 종류의 선형 불평등이나 평등에 의해 설명될 수 있다고 명시하고 있다. 첫째, 각 매트릭스 셀에 대해 이 셀이 음수가 아닌 값을 갖는 제약조건이 있다. 그리고 둘째, 행렬의 각 행 또는 열에 대해, 해당 행 또는 열의 셀 합계가 1과 같다는 제약이 있다. 행과 열의 제약조건은 비르코프 폴리토프가 있는 차원 n² - 2n + 1의 선형 하위공간을 정의하며, 비부정성 제약조건은 그 하위공간 내에서 비르코프 폴리토프의 면을 정의한다.

그러나 비르코프 폴리토프는 그 면에 대한 완전한 설명이 가능하다는 점에서 특이하다. 다른 많은 0-1 폴리탑의 경우 기하급수적으로 많거나 지나치게 많은 면들이 존재하며, 면에 대한 부분적인 설명만 이용할 수 있다.^[14]

참고 항목

• 추상폴리토프
• 콤비네이터 역수학
• 마트로이드 폴리토프
• 폴리토프 주문
• 단순구
• 안정적 매칭 폴리토프

메모들

참조

외부 링크

• Kalai, Gil (2008), Five Open Problems Regarding Convex Polytopes.