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

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

Определение

Решетка — это частично упорядоченное множество , в котором любые два элемента $x$ и $y$ имеют как наименьшую верхнюю границу, называемую соединением , так и супремумом , обозначаемую $x\vee y$ и наибольшая нижняя граница, называемая встречей или нижней границей , обозначаемая $x\wedge y$ .

Следующие определения применимы к ЧУМ в целом, а не только к решеткам, если не указано иное.
Для минимального элемента $x$ , нет элемента $y$ такой, что $y<x$ .
Элемент $x$ охватывает другой элемент $y$ (написано как $x:>y$ или $y<:x$ ) если $x>y$ и нет элемента $z$ отличный от обоих $x$ и $y$ так что $x>z>y$ .
Оболочка минимального элемента называется атомом .
Решетка является атомистической , если каждый элемент является супремумом некоторого набора атомов.
ЧУ-множество оценивается , когда ему можно присвоить функцию ранга. $r(x)$ отображает его элементы в целые числа, так что $r(x)>r(y)$ в любое время $x>y$ , а также $r(x)=r(y)+1$ в любое время $x:>y$ .
Когда градуированное ЧУМ имеет нижний элемент, можно без ограничения общности предположить, что его ранг равен нулю. В данном случае атомами являются элементы первого ранга.
Градуированная решетка называется полумодулярной , если для любого $x$ и $y$ , его ранговая функция подчиняется тождеству ^[1]
$r(x)+r(y)\geq r(x\wedge y)+r(x\vee y).\,$
Матроидная решетка — это решетка, одновременно атомистическая и полумодулярная. ^[2]^[3] — Геометрическая решетка это конечная решетка матроида. ^[4]

Многие авторы рассматривают только конечные решетки матроидов и используют термины «геометрическая решетка» и «решетка матроидов» как взаимозаменяемые. ^[5]

Решетки против матроидов

Геометрические решетки эквивалентны (конечным) простым матроидам, а решетки матроидов эквивалентны простым матроидам без предположения конечности (при соответствующем определении бесконечных матроидов; таких определений несколько). Соответствие состоит в том, что элементами матроида являются атомы решетки, а элемент x решетки соответствует плоскости матроида, состоящей из тех элементов матроида, которые являются атомами. $a\leq x.$

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

r(X)+r(Y)\geq r(X\cap Y)+r(X\cup Y)

для множеств X и Y элементов матроида. Максимальные . данного ранга называются квартирами множества Пересечение двух флэтов снова является флэтом, определяющим операцию наибольшей нижней границы для пар флетов; можно также определить минимальную верхнюю границу пары квартир как (уникальное) максимальное надмножество их объединения, имеющее тот же ранг, что и их объединение. Таким образом, плоскости матроида образуют решетку матроида или (если матроид конечен) геометрическую решетку. ^[4]

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

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

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

Существуют два различных естественных понятия двойственности геометрической решетки. $L$ : двойственный матроид, в основе которого лежат множества дополнений баз матроида, соответствующие $L$ и двойственная решетка — решетка, состоящая из тех же элементов, что и $L$ в обратном порядке. Они не одинаковы, и действительно, двойственная решетка сама по себе обычно не является геометрической решеткой: свойство атомистичности не сохраняется при изменении порядка. Чунг (1974) определяет сопряжение геометрической решетки $L$ (или матроида, определенного из него) как минимальная геометрическая решетка, в которую входит двойственная решетка $L$ встроен по порядку . У некоторых матроидов нет сопряженных; примером является матроид Вамос . ^[6]

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

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

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

Ссылки

^ Биркгоф (1995) , Теорема 15, с. 40. Точнее, определение Биркгофа гласит: «Мы будем называть P (верхний) полумодулярным, если оно удовлетворяет условию: Если a ≠ b оба покрывают c , то существует d ∈ P , который покрывает и a, и b » (стр. 39). Теорема 15 гласит: «Градуированная решетка конечной длины полумодулярна тогда и только тогда, когда r ( x ) + r ( y )≥ r ( x ∧ y ) + r ( x ∨ y )».
^ Маэда, Ф.; Маэда, С. (1970), Теория симметричных решеток , Основные принципы математических наук, Том 173, Нью-Йорк: Springer-Verlag, MR 0282889 .
^ Уэлш, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 388, ISBN 9780486474397 .
^ Перейти обратно: ^а ^б ^с ^д Валлийский (2010) , с. 51.
^ Биркгоф, Гарретт (1995), Теория решетки , Публикации коллоквиума, том. 25 (3-е изд.), Американское математическое общество, с. 80, ISBN 9780821810255 .
^ Чунг, Алан LC (1974), «Сопряженные геометрии», Canadian Mathematical Bulletin , 17 (3): 363–365, исправление, там же. 17 (1974), вып. 4, 623, номер документа : 10.4153/CMB-1974-066-5 , MR 0373976 .
^ Валлийский (2010) , стр. 55, 65–67.
^ Валлийский (2010) , с. 58; Уэлш приписывает этот результат Роберту П. Дилворту , который доказал его в 1941–1942 годах, но не приводит конкретной ссылки на его оригинальное доказательство.

Внешние ссылки

«Геометрическая решетка» , PlanetMath.
Последовательность OEIS A281574 (Количество непомеченных геометрических решеток с n элементами)

[1] Биркгоф (1995) , Теорема 15, с. 40. Точнее, определение Биркгофа гласит: «Мы будем называть P (верхний) полумодулярным, если оно удовлетворяет условию: Если a ≠ b оба покрывают c , то существует d ∈ P , который покрывает и a, и b » (стр. 39). Теорема 15 гласит: «Градуированная решетка конечной длины полумодулярна тогда и только тогда, когда r ( x ) + r ( y )≥ r ( x ∧ y ) + r ( x ∨ y )».

[2] Маэда, Ф.; Маэда, С. (1970), Теория симметричных решеток , Основные принципы математических наук, Том 173, Нью-Йорк: Springer-Verlag, MR 0282889 .

[3] Уэлш, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 388, ISBN 9780486474397 .

[w10-51-4] Перейти обратно: ^а ^б ^с ^д Валлийский (2010) , с. 51.

[5] Биркгоф, Гарретт (1995), Теория решетки , Публикации коллоквиума, том. 25 (3-е изд.), Американское математическое общество, с. 80, ISBN 9780821810255 .

[6] Чунг, Алан LC (1974), «Сопряженные геометрии», Canadian Mathematical Bulletin , 17 (3): 363–365, исправление, там же. 17 (1974), вып. 4, 623, номер документа : 10.4153/CMB-1974-066-5 , MR 0373976 .

[7] Валлийский (2010) , стр. 55, 65–67.

[8] Валлийский (2010) , с. 58; Уэлш приписывает этот результат Роберту П. Дилворту , который доказал его в 1941–1942 годах, но не приводит конкретной ссылки на его оригинальное доказательство.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]