幾何学格子

マトロイドと格子の数学において、幾何格子は有限の 原子半 モジュラー格子であり、マトロイド格子は有限性を仮定しない原子半モジュラー格子です。幾何格子とマトロイド格子はそれぞれ有限のマトロイド、または有限かつ無限のマトロイドの平面の格子を形成し、あらゆる幾何格子またはマトロイド格子はこのようにマトロイドから生じます。

格子は、任意の 2 つの要素とが、で表される結合または上限と呼ばれる最小の上限と、 で表される会合または下限と呼ばれる最大の下限の両方を持つような半集合です。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle x\vee y}$${\displaystyle x\wedge y}$

以下の定義は、特に明記しない限り、格子だけでなく、一般的な poset に適用されます。

• 最小要素 の場合、となる要素は存在しません。${\displaystyle x}$${\displaystyle y}$${\displaystyle y<x}$
• 要素が別の要素（またはと表記）をカバーする場合、およびと の両方と異なる要素が存在せず、となります。${\displaystyle x}$ ${\displaystyle y}$${\displaystyle x:>y}$${\displaystyle y<:x}$${\displaystyle x>y}$${\displaystyle z}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x>z>y}$
• 最小の元素の被覆は原子と呼ばれます。
• すべての要素が何らかの原子集合の上限である場合、格子は原子論的です。
• poset は、の場合にも の場合にも、 となるような、要素を整数にマッピングするランク関数を与えることができる場合に、段階付けされます。${\displaystyle r(x)}$${\displaystyle r(x)>r(y)}$${\displaystyle x>y}$${\displaystyle r(x)=r(y)+1}$${\displaystyle x:>y}$

次数付き poset に最下位要素がある場合、一般性を失うことなく、そのランクが 0 であると仮定できます。この場合、原子はランク 1 の要素です。

• 次数付き格子が半モジュラであるとは、任意のおよびに対して、その階数関数が恒等式に従う場合である^[1]。${\displaystyle x}$${\displaystyle y}$

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

• マトロイド格子は、原子論的かつ半モジュラー的な格子である。^{[2] [3]} 幾何学的格子は有限マトロイド格子である。^[4]

多くの著者は有限マトロイド格子のみを考慮しており、両方に対して「幾何学格子」と「マトロイド格子」という用語を同じ意味で使用している。^[5]

幾何学的格子は（有限の）単純マトロイドと同等であり、マトロイド格子は有限性を仮定しない単純マトロイドと同等である（無限マトロイドの適切な定義の下では、そのような定義はいくつかある）。対応関係は、マトロイドの要素が格子の原子であり、格子の要素xがマトロイドの原子である要素からなるマトロイドの平面に対応することである。${\displaystyle a\leq x.}$

幾何格子と同様に、マトロイドにはランク関数が与えられていますが、その関数は格子要素を引数として取るのではなく、マトロイド要素のセットを数値にマッピングします。マトロイドのランク関数は単調でなければならず (セットに要素を追加してもランクが下がることはありません)、サブモジュラでなければなりません。つまり、セミモジュラランク付き格子の不等式と同様の不等式に従います。

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

マトロイド要素の集合XとYについて。与えられたランクの最大集合はフラットと呼ばれる。2つのフラットの交差もフラットであり、フラットのペアに対する最大の下限操作を定義する。また、フラットのペアの最小上限を、それらの和集合と同じランクを持つ（唯一の）最大のスーパーセットとして定義することもできます。このように、マトロイドのフラットはマトロイド格子、または（マトロイドが有限である場合）幾何学的格子を形成します。^[4]

逆に、がマトロイド格子である場合、原子の集合のランクをその集合の最大下限の格子ランクと定義することにより、その原子の集合のランク関数を定義できます。このランク関数は必然的に単調かつサブモジュラであるため、マトロイドを定義します。このマトロイドは必然的に単純であり、つまり2要素の集合はすべてランク2になります。^[4]${\displaystyle L}$

格子から単純マトロイドを構築する方法と、マトロイドから格子を構築する方法の2つの構築は、互いに逆の関係にあります。つまり、幾何学的格子または単純マトロイドから始めて、両方の構築を順に実行すると、元の格子またはマトロイドと同型の格子またはマトロイドが得られます。^[4]

幾何格子 の双対性には 2 つの異なる自然な概念があります。1 つは、に対応するマトロイドの基底の補集合を基底セットとする双対マトロイド、もう1 つは、逆の順序で と同じ要素を持つ格子である双対格子 です。これらは同じではなく、実際、双対格子自体は一般に幾何格子ではありません。原子論的であるという特性は、順序反転によって保持されません。Cheung (1974) は、幾何格子 (またはそれから定義されるマトロイド) の随伴を、 の双対格子が順序埋め込まれた最小の幾何格子として定義しています。マトロイドの中には随伴を持たないものもあります。その例として、Vámos マトロイドがあります。^[6]${\displaystyle L}$${\displaystyle L}$${\displaystyle L}$${\displaystyle L}$${\displaystyle L}$

幾何格子（与えられた下限と上限の要素間の格子の部分集合）のあらゆる区間は、それ自体が幾何的である。幾何格子の区間を取ることは、関連するマトロイドのマイナーを形成することに対応する。幾何格子は補完的であり、区間の性質により相対的に補完的でもある。^[7]

すべての有限格子は幾何格子の部分格子である。^[8]

• 「幾何学格子」、PlanetMath
• OEISシーケンス A281574 (n 個の要素を持つラベルなし幾何格子の数)