В математике матроидов и решеток , А геометрическая решетка является конечной атомистической полумодулярной решетки , а матроид решеткой является атомистической полумодулярной решетки без предположений конечности. Геометрические решетки и решетки матроидов, соответственно, образуют решетки плоскостей конечных и бесконечных матроидов, и каждая геометрическая или матроидная решетка происходит из матроида таким образом.
Определение
Решетка является ч.у.м. , в котором любые два элемента а также оба имеют супремум , обозначаемый, и нижнюю грань , обозначаемую.
- Следующие определения применяются к множествам в целом, а не только к решеткам, если не указано иное.
- Для минимального элемента , нет элемента такой, что .
- Элемент покрывает другой элемент (написано как или же ) если и нет элемента отличается от обоих а также чтобы .
- Покрытие минимального элемента называется атомом .
- Решетка является атомистической, если каждый элемент является супремумом некоторого набора атомов.
- Посет оценивается, когда ему может быть присвоена функция ранга отображение своих элементов в целые числа, так что в любое время , а также в любое время .
- Когда у градуированного ЧУМ есть нижний элемент, без ограничения общности можно предположить, что его ранг равен нулю. В этом случае атомы - это элементы с рангом один.
- Градуированная решетка полумодулярна, если для каждого а также , его ранговая функция подчиняется тождеству [1]
- Матроид решетка является решеткой , которая является одновременно и атомистической полумодулярным. [2] [3] геометрическая решетка является конечной матроидом решетки. [4]
- Некоторые авторы рассматривают только конечные решетки матроидов и используют термины «геометрическая решетка» и «решетка матроидов» как синонимы для обоих. [5]
Криптоморфизм
Геометрические решетки криптоморфны (конечным, простым) матроидам, а решетки матроидов криптоморфны простым матроидам без предположения конечности.
Подобно геометрическим решеткам, матроиды наделены функциями ранга , но эти функции отображают наборы элементов в числа, а не принимают отдельные элементы в качестве аргументов. Функция ранга матроида должна быть монотонной (добавление элемента в набор никогда не может уменьшить его ранг), и они должны быть субмодулярными функциями , что означает, что они подчиняются неравенству, аналогичному неравенству для полумодулярных решеток:
В максимальные наборы данного ранга называются квартиры. Пересечение двух квартир снова является плоскостью, определяющей наибольшую нижнюю границу для пары квартир; можно также определить точную верхнюю границу пары квартир как (единственное) максимальное надмножество их объединения, имеющее тот же ранг, что и их объединение. Таким образом, плоскости матроида образуют решетку матроида или (если матроид конечный) геометрическую решетку. [4]
Наоборот, если является решеткой матроидов, можно определить функцию ранга на множествах ее атомов, определив ранг множества атомов как решеточный ранг точной нижней границы этого множества. Эта функция ранга обязательно монотонна и субмодулярна, поэтому она определяет матроид. Этот матроид обязательно прост, а это означает, что каждый двухэлементный набор имеет ранг два. [4]
Эти две конструкции, простого матроида из решетки и решетки из матроида, являются обратными друг другу: начиная с геометрической решетки или простого матроида и выполняя обе конструкции одно за другим, получается решетка или матроид, который изоморфна исходному. [4]
Двойственность
Есть два различных естественных понятия двойственности для геометрической решетки : дуальный матроид, в основе которого лежат дополнения к базам матроида, соответствующие, и дуальная решетка , решетка, которая имеет те же элементы, что ив обратном порядке. Это не одно и то же, и, действительно, дуальная решетка сама по себе обычно не является геометрической решеткой: свойство быть атомистическим не сохраняется при изменении порядка. Cheung (1974) определяет сопряженный геометрической решетки (или определенного из него матроида) как минимальную геометрическую решетку, в которую двойственная решетка это порядок встраиваемый . Некоторые матроиды не имеют сопряжения; Примером может служить матроид Vámos . [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 )».
- ^ Maeda, F .; Маэда, С. (1970), Теория симметричных решеток , Die Grundlehren der Mathematischen Wissenschaften, Band 173, Нью-Йорк: Springer-Verlag, MR 0282889.
- ^ Валлийский, DJA (2010), Теория матроидов , Courier Dover Publications, стр. 388, ISBN 9780486474397.
- ^ a b c d Валлийский (2010) , стр. 51.
- ^ Биркгоф, Гаррет (1995), Теория решеток, Публикации коллоквиума, 25 (3-е изд.), Американское математическое общество, стр. 80, ISBN 9780821810255.
- ^ Cheung, Alan LC (1974), "Сопряжения геометрии", Canadian Mathematical Bulletin , 17 (3): 363–365, исправление, там же. 17 (1974), нет. 4, 623, DOI : 10,4153 / КМФ-1974-066-5 , МР 0373976.
- Перейти ↑ Welsh (2010) , pp. 55, 65–67.
- ↑ Валлийский (2010) , стр. 58; Уэлш приписывает этот результат Роберту П. Дилворту , который доказал его в 1941–1942 годах, но не цитирует его оригинальное доказательство.
Внешние ссылки
- «Геометрическая решетка» . PlanetMath .
- Последовательность OEIS A281574 (количество немаркированных геометрических решеток с n элементами)