기하 격자

매트로이드와 격자의 수학에서 기하학적 격자는 유한한 원자론적 반모형 격자이고, 매트로이드 격자는 유한성의 가정이 없는 원자론적 반모형 격자입니다.기하학적 격자와 매트로이드 격자는 각각 유한 또는 유한 및 무한 매트로이드의 평면 격자를 형성하며, 모든 기하학적 또는 매트로이드 격자는 이런 방식으로 매트로이드에서 나옵니다.

정의.

격자는 $임의$의 두 요소 x ${\displaystyle x}$ 및 $y${\$displaystyle y}$가 x ∨${\displaystyle y}$ ${\displaystyle x\vey}$로 표시되는 조인 또는 수프리미엄이라고 하는 최소 상한과$$$x$ ∧${\displaystyle y}$ ${\displaystyle x\wedgey}$로 표시되는 최대 하한을 모두 갖는 집합입니다$.$

다음 정의는 달리 명시된 경우를 제외하고 격자만이 아닌 일반적인 포셋에 적용됩니다.

• 최소 요소 $x{\displaystyle }$ ${\displaystyle x}$의 경우$$y< x ${\displaystyle$ $y$$}$인$요소$가 없습니다
• 요소 $x{\displaystyle }$ ${\displaystyle x}$는 > ${\displaystyle x$$>$$}$인 $경우{\displaystyle }$ 다른 요소 {\$displaystyle$y$}($x ${\$displaystyle $x$$:>y$ 또는 ${\displaystyle$ y$<:x})$를 포함하며, > > >$$y {\$displaystyle x>z>y}$과(와)$$구별되는 요소 z {\$displaystyle$ $z$$}$가 없습니다
• 최소 원소의 덮개는 원자라고 불립니다.
• 격자는 모든 원소가 원자 집합의 최상층이라면 원자론적입니다.
• 포셋은 > ${\displaystyle x>y}$일 때마다 > ${\displaystyle r(x)>r(y)},$:> y {\displaystyle x>$y{\displaystyle \}}$일 때마다 r(x${\displaystyle )}$= ${\displaystyle r(}$y$)$ + 1 {\$displaystyle$ r$(x$)= $r(y)+1}$과 같이 요소를 정수로 매핑하는 랭크 함수 $r{\displaystyle (x)}$ ${\$$displaystyle x:>y}$이 주어질 수 있을 때 등급이 매겨집니다

등급 포셋이 하위 요소를 가질 때 일반성을 잃지 않고 순위가 0이라고 가정할 수 있습니다.이 경우 원자는 1등 원소입니다.

• 등급 격자는 모든 $x{\displaystyle }$ ${\displaystyle x}$ 및 $y$ ${\displaystyle y}$에$$대해 순위 함수가 동일성을^[1] 따르는 경우 반모듈형입니다.

${\displaystyle r(x)+r(y)\geq r(x\wedge y)+r(x\vey).\,}$

• 매트로이드 격자는 원자론적이면서 반모형적인 격자입니다.^[2][3]기하학적 격자는 유한한 매트로이드 격자입니다.^[4]

많은 저자들은 유한 매트로이드 격자만을 고려하고, 기하학적 격자와 매트로이드 격자라는 용어를 혼용하여 사용합니다.^[5]

격자 대 매트로이드

기하학적 격자는 (무한) 단순 매트로이드와 동일하며, 매트로이드 격자는 유한성의 가정이 없는 단순 매트로이드와 동일합니다 (무한 매트로이드의 적절한 정의 하에서; 그러한 정의가 몇 가지 있습니다).대응되는 것은 매트로이드의 원소가 격자의 원자이고, 격자의 원소 x는 매트로이드의 원소로 구성된 매트로이드의 평탄부에 해당하는 원자 ${\displaystyle a}$ ${\displaystyle \le }$ x$.{\displaystyle a\leq x.}$

기하학적 격자와 마찬가지로, 매트로이드는 순위 함수를 부여받지만, 그 함수는 격자 요소를 인수로 삼기보다는 매트로이드 요소 집합을 수에 매핑합니다.매트로이드의 순위 함수는 단조적이어야 하며(집합에 원소를 추가하면 순위가 절대 감소하지 않음), 하위 모듈이어야 하며, 이는 반모듈식 순위 격자의 경우와 유사한 부등식을 준수함을 의미합니다.

${\displaystyle r(X)+r(Y)\geqr(X\cap Y)+r(X\cup Y)}$

매트로이드 원소의 집합 X 및 Y에 대해.지정된 순위의 최대 집합을 플랫이라고 합니다.두 플랫의 교집합은 다시 플랫이며, 플랫 쌍에서 최대 하한 연산을 정의합니다. 또한 플랫 쌍의 최소 상한을 유니크한 유니크한 최대 수퍼셋으로 정의할 수 있습니다.이런 방식으로 매트로이드의 평면은 매트로이드 격자 또는 (매트로이드가 유한한 경우) 기하학적 격자를 형성합니다.^[4]

반대로, $L{\displaystyle }$ ${\displaystyle L}$이 매트로이드 격자라면, 원자 집합의 순위를 그 집합의 가장 큰 하한의 격자 순위로 정의함으로써 원자 집합의 순위 함수를 정의할 수 있습니다.이 순위 함수는 반드시 단조롭고 하위 모듈이므로 매트로이드를 정의합니다.이 매트로이드는 반드시 간단하며, 이는 모든 2개 원소 집합이 2위를 차지한다는 것을 의미합니다.^[4]

격자에서 단순한 매트로이드와 매트로이드에서 격자로 이루어진 이 두 구조는 서로 반대입니다. 기하학적 격자 또는 단순한 매트로이드에서 시작하여 두 구조를 차례로 수행하면 원래와 동형인 격자 또는 매트로이드가 제공됩니다.^[4]

이중성

기하학적 격자 $L{\displaystyle }$ ${\displaystyle L}$에는 두 가지 다른 자연스러운 이중성 개념이 있습니다$:$ $L{\displaystyle }$ ${\displaystyle L}$에 해당하는 매트로이드의 밑면의 보어를 기본으로 설정하는 이중 매트로이드와$$$L{\displaystyle }$ ${\displaystyle L}$과 같은 원소를 역순으로 갖는$$ 격자인 이중 격자.그들은 같지 않고, 실제로 이중 격자는 일반적으로 그 자체가 기하학적 격자가 아닙니다. 원자론적인 특성은 순서 역전에 의해 보존되지 않습니다.Cheung(1974)은 기하학적 $격자{\displaystyle }$ L ${\displaystyle$ L$}($또는 그것으로부터 정의된 매트로이드의)의 인접을 $L{\displaystyle }$ ${\displaystyle L}$의 이중 격자가 순서대로 내장된$$ 최소의 기하학적 격자라고 정의합니다.어떤 매트로이드는 인접 관계가 없습니다. 예를 들면 바모스 매트로이드가 있습니다.^[6]

추가속성

기하학적 격자(주어진 하한 요소와 상한 요소 사이의 격자 부분 집합)의 모든 간격은 그 자체로 기하학적입니다. 기하학적 격자의 간격을 취하는 것은 관련 매트로이드의 작은 부분을 형성하는 것에 해당합니다.기하학적 격자들은 서로 보완되며, 구간 특성 때문에 상대적으로 보완됩니다.^[7]

모든 유한한 격자는 기하학적 격자의 하위 격자입니다.^[8]

참고문헌

외부 링크

• "Geometric lattice", PlanetMath
• OEIS 시퀀스 A281574 (n개의 요소가 있는 레이블이 없는 기하학적 격자의 수)