Геометрическая решетка

редактировать

В математике матроиды и решетки, геометрическая решетка - это конечная атомистическая полумодульная решетка, а решетка матроидов является атомистической полумодулярной решеткой без предположений конечности. Геометрические решетки и решетки матроидов, соответственно, образуют решетки плоскостей конечных и бесконечных матроидов, и каждая геометрическая решетка или решетка матроидов происходит из матроида таким образом.

Содержание

1 Определение
2 Криптоморфизм
3 Двойственность
4 Дополнительные свойства
5 Ссылки
6 Внешние ссылки

Определение

A решетка - это poset, в котором любые два элемента $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ имеют оба элемента верхняя грань, обозначаемая $x ∨ y {\ displaystyle x \ vee y}$ $x \ vee y$ , и infimum, обозначаемая $x ∧ y {\ displaystyle x \ wedge y}$ $x \ wedge y$ .

Следующие определения применяются к позициям в целом, а не только к решеткам, если не указано иное.

Для минимального элемента $x {\ displaystyle x}$ $x$ , нет элемента $y {\ displaystyle y}$ $y$ такого, что $y < x {\displaystyle y$ ${\ displaystyle y <x}$ .
элемент $x {\ displaystyle x}$ $x$ покрывает другой элемент $y {\ displaystyle y}$ $y$ (записывается как $x:>y {\ displaystyle x:>y}$ $x:>y$ или $y <: x {\displaystyle y<:x}$ $y <: x$ ), если $x>y {\ displaystyle x>y}$ $x>y$ и нет элемента $z {\ displaystyle z}$ $z$ , отличного от обоих $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ так что $x>z>y {\ displaystyle x>z>y}$ $x>z>y$ .
Покрытие минимального элемента называется атом.
Решетка является атомистической, если каждый элемент является супремумом некоторого набора атомов.
Позиционирование равно graded, когда ему может быть присвоена функция ранга $r (x) {\ displaystyle r (x)}$ $r (x)$ отображение его элементов в целые числа, например, $р (х)>р (y) {\ displaystyle r (x)>r (y)}$ $r(x)>r (y)$ всякий раз, когда $x>y {\ displaystyle x>y}$ $х>Y$ и, в частности, $r (x) = r (y) + 1 {\ displaystyle r (x) = r ( y) +1}$ $р (Икс) знак равно р (Y) +1$ всякий раз, когда $x:>y {\ displaystyle x:>y}$ $x:>y$ .

Когда оцениваемый позет имеет нижний элемент, можно без ограничения общности предположить, что его ранг равно нулю. В этом случае атомы - это элементы с рангом один.

Градуированная решетка полумодулярная, если для каждого $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ , его функция ранга подчиняется тождеству

r (x) + r (y) ≥ r (x ∧ y) + r (x ∨ y). {\ displaystyle r (x) + r (y) \ geq r (x \ wedge y) + r (x \ vee y). \,}

r (x) + r (y) \ geq r (x \ wedge y) + r (x \ vee y). \,

A решетка матроидов - это решетка, которая является как атомистической, так и полумодулярной. Геометрическая решетка представляет собой конечную решетку матроидов.

Некоторые авторы рассматривают только конечные решетки матроидов и используют термины «геометрическая решетка» и «решетка матроидов» как синонимы для обоих.

Криптоморфизм

Геометрические решетки криптоморфны (конечным, простым) матроидам, а решетки матроидов криптоморфны простым матроидам без предположения о конечности.

Подобно геометрическим решеткам, матроиды наделены функциями ранга, но эти функции отображают наборы элементов в числа, а не принимают отдельные элементы в качестве аргументов. Функция ранга матроида должна быть монотонной (добавление элемента в набор никогда не может уменьшить его ранг), и они должны быть субмодульными функциями, что означает, что они подчиняются неравенству, аналогичному неравенству для полумодулярных решеток:

r (X) + r (Y) ≥ r (X ∩ Y) + r (X ∪ Y). {\ displaystyle r (X) + r (Y) \ geq r (X \ cap Y) + r (X \ cup Y). \,}

{\ Displaystyle г (X) + r (Y) \ geq r (X \ cap Y) + r (X \ cup Y). \,}

максимальные наборы заданного ранга: называется квартирой. Пересечение двух квартир снова является плоскостью, определяющей наибольшую нижнюю границу для пары квартир; можно также определить точную верхнюю границу пары квартир как (единственное) максимальное надмножество их объединения, которое имеет тот же ранг, что и их объединение. Таким образом, плоскости матроида образуют решетку матроида или (если матроид конечный) геометрическую решетку.

И наоборот, если $L {\ displaystyle L}$ $L$ является решеткой матроидов, можно определить функцию ранга на множествах ее атомов, определив ранг множества атомов как решеточный ранг точной нижней границы этого множества. Эта функция ранга обязательно монотонна и субмодулярна, поэтому она определяет матроид. Этот матроид обязательно прост, а это означает, что каждый двухэлементный набор имеет ранг два.

Эти две конструкции, простого матроида из решетки и решетки из матроида, обратны друг другу: начиная с геометрическая решетка или простой матроид, и выполнение обоих построений одно за другим дает решетку или матроид, изоморфный исходной.

Двойственность

Есть два разных естественных понятия двойственность для геометрической решетки $L {\ displaystyle L}$ $L$ : двойственный матроид, который имеет в качестве своей основы наборы дополнений оснований матроида, соответствующего $L {\ displaystyle L}$ $L$ и двойная решетка, решетка, которая имеет те же элементы, что и $L {\ displaystyle L}$ $L$ в обратном порядке. заказ. Это не одно и то же, и, действительно, двойственная решетка сама по себе обычно не является геометрической решеткой: свойство быть атомистическим не сохраняется при изменении порядка. Cheung (1974) определяет сопряженный геометрической решетки $L {\ displaystyle L}$ $L$ (или определяемого из нее матроида) как минимальная геометрическая решетка, в которую двойственная решетка $L {\ displaystyle L}$ $L$ является вложенной в порядок. Некоторые матроиды не имеют сопряжения; пример - матроид Вамоса .

Дополнительные свойства

Каждый интервал геометрической решетки (подмножество решетки между заданными нижними и верхними элементами) сам по себе является геометрическим; взятие интервала геометрической решетки соответствует формированию второстепенного связанного матроида. Геометрические решетки дополняются, и благодаря свойству интервала они также относительно дополняются.

Каждая конечная решетка является подрешеткой геометрической решетки.