Геометрическая решетка
Алгебра соединения-встречи на матроидных квартирах

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

Определение

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

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

  • Для минимального элемента не существует такого элемента, что . х {\displaystyle x} у {\displaystyle у} у < х {\displaystyle у<х}
  • Элемент покрывает другой элемент (обозначается как или ), если и нет элемента, отличного от обоих и , так что . х {\displaystyle x} у {\displaystyle у} х :> у {\displaystyle x:>y} у <: х {\displaystyle y<:x} х > у {\displaystyle х>у} з {\displaystyle z} х {\displaystyle x} у {\displaystyle у} х > з > у {\displaystyle x>z>y}
  • Оболочка минимального элемента называется атомом .
  • Решетка является атомистической , если каждый элемент является супремумом некоторого набора атомов.
  • Посет считается градуированным , если ему можно задать функцию ранга, отображающую его элементы в целые числа, так что всякий раз, когда , а также всякий раз, когда . г ( х ) {\displaystyle r(x)} г ( х ) > г ( у ) {\displaystyle r(x)>r(y)} х > у {\displaystyle х>у} г ( х ) = г ( у ) + 1 {\displaystyle r(x)=r(y)+1} х :> у {\displaystyle x:>y}
Когда градуированный ЧУМ имеет нижний элемент, можно предположить, не теряя общности, что его ранг равен нулю. В этом случае атомы являются элементами с рангом один.
  • Градуированная решетка является полумодулярной , если для любых и ее ранговая функция подчиняется тождеству [1] х {\displaystyle x} у {\displaystyle у}
г ( х ) + г ( у ) ≥ г ( х ∧ у ) + г ( х ∨ у ) . {\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 \ кепка Y) + г (X \ чашка Y)}

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

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

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

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

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

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

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

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

Ссылки

  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), Теория симметричных решеток , Die Grundlehren der mathematischen Wissenschaften, Band 173, Нью-Йорк: Springer-Verlag, MR  0282889.
  3. ^ Валлийский, DJA (2010), Теория Матроида , Courier Dover Publications, стр. 388, ISBN 9780486474397.
  4. ^ abcd Welsh (2010), стр. 51.
  5. ^ Биркгофф, Гарретт (1995), Теория решеток, Colloquium Publications, т. 25 (3-е изд.), Американское математическое общество, стр. 80, ISBN 9780821810255.
  6. ^ Cheung, Alan LC (1974), «Сопряженные элементы геометрии», Canadian Mathematical Bulletin , 17 (3): 363–365 , исправление, там же, 17 (1974), № 4, 623, doi : 10.4153/CMB-1974-066-5 , MR  0373976.
  7. ↑ Уэлш (2010), стр. 55, 65–67.
  8. ↑ Welsh (2010), стр. 58; Welsh приписывает этот результат Роберту П. Дилворту , который доказал его в 1941–1942 годах, но не приводит конкретной ссылки на его оригинальное доказательство.
  • «Геометрическая решетка», PlanetMath
  • Последовательность OEIS A281574 (Число немаркированных геометрических решеток с n элементами)
Взято с "https://en.wikipedia.org/w/index.php?title=Геометрическая_решетка&oldid=1201476563"