В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 17
Текст из файла (страница 17)
Пусть C1 =(b, c, f ) , C2 = (d). В этом случае устанавливается соответствие между элементами решетки и наборами длины 2 с целочисленными координатами, первая из которых меняется в диапазоне от 0 до 3, а вторая — от 0 до 1:a −→ (0, 0)b −→ (1, 0)c −→ (2, 0)d −→ (1, 1)e −→ (2, 1)f −→ (3, 1)Это соответствие проинтерпретируем как вложение дистрибутивной решетки в двумерный параллелепипед с целочисленными координатами [0, 3] × [0, 1]:f c`@e c`@`@d c`@c`c@`@c`b@@c`a58ГЛАВА 1.
КОМБИНАТОРИКАСледующий интересующий нас вопрос — это кодирование дистрибутивных решеток. В задачах часто бывает удобноработать не с самой дистрибутивной решеткой, а с некоторой ее кодировкой, обладающей наименьшей избыточностьюи, в то же время, однозначной. Ниже строится один из наиболее популярных способов кодировать дистрибутивныерешетки.Пусть (P, 6) — дистрибутивная решетка. Выделим из нее множество всех неприводимых элементов Q и определимновое частично упорядоченное множество (Q, 6), где отношение частичного порядка то же, что и в исходной решетке. Каждому a ∈ P однозначным образом ставится в соответствие подмножество из Q, являющееся его разложением.Отметим, что это подмножество обязательно является антицепью.
Нулю поставим в соответствие пустую антицепь.Каждой такой антицепи S поставим в соответствие ее замыкание вниз S− = {a ∈ Q | ∃ a0 ∈ S : a 6 a0 }. Введем на Q антимонотонную булеву функцию f :(1, x ∈ S− ,f (q) =0, иначе.При этом сама антицепь S окажется для f множеством верхних единиц. Множество S− называется идеалом. В связис тем, что все вышевведенные соответствия оказываются изоморфизмами, можно утверждать, что дистрибутивнаярешетка изоморфна множеству идеалов своих неприводимых элементов. Покроем Q упорядоченным наборомцепей C1 , . .
. ,Cn . Это можно сделать множеством способов, при этом количество цепей меняется от ширины Q до мощности Q. Относительно антимонотонной булевой функции f каждая цепь разбивается на два куска: нижний кусок погружен во множество единиц, а верхний — во множество нулей (какие-то из кусков вполне могут оказаться пустыми).В цепи Ci выберем наибольший элемент, погруженный в единицу — xi (снова считаем, что все элементы цепи пронумерованы от единицы до длины цепи; если такового не оказалось, полагаем номер верхней единицы нулем). В этом случаекодировкой решетки назовем набор x1 , .
. . , xi , . . . , xn .Если покрывать решетку цепями длины единица, то будет получено ее вложение в соответствующий единичныйn-мерный куб. Если брать покрытие меньшим числом цепей, то размерность параллелепипеда падает, однако растетчисло возможных значений координат.Рассмотрим в качестве примера B52 , 6 .f c`` (10100)@c` e@` (10010)` c`HH d (10001)Hc` bcHc` (01001)@@a c` (00101)(P, 6)(01100)(01010)(00110)(11000)(Q, 6)fc`@@c` de `cHHHb c`Hc` c@@c`a`(00011)Неприводимыми в этой решетке являются элементы a, b, c, d, e, f , их частичный порядок указан на соответствующейдиаграмме Хассе.
Несократимые разложения элементов P на неприводимые элементы выглядят следующим образом:(00011) = ∅,(00101) = a,(00110) = b,(01001) = c,(01010) = b ∨ c,(10001) = d,(01100) = e,(10010) = b ∨ d,(10100) = e ∨ d,(11000) = f .В первый раз покроем Q цепями длины 1. Ниже указаны полученные кодировки.(00011) −→ (0, 0, 0, 0, 0, 0) ,(00101) −→ (1, 0, 0, 0, 0, 0) ,(00110) −→ (1, 1, 0, 0, 0, 0) ,(01001) −→ (1, 0, 1, 0, 0, 0) ,1.4. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВА59(01010) −→ (1, 1, 1, 0, 0, 0) ,(10001) −→ (1, 0, 1, 1, 0, 0) ,(01100) −→ (1, 1, 1, 0, 1, 0) ,(10010) −→ (1, 1, 1, 1, 0, 0) ,(10100) −→ (1, 1, 1, 1, 1, 0) ,(11000) −→ (1, 1, 1, 1, 1, 1) .Проинтерпретируем полученный результат как вложение B52 в шестимерный единичный куб (чтобы не загромождать ибез того сложный рисунок мы опускаем кодировки элементов, предполагая, что вершины куба расположены по ярусам,при этом на i-ом ярусе снизу (отсчет начинается с нуля) расположены вершины с i единицами, упорядоченные согласноиндуктивному построению).` XcXXXXB @XXX@ B @XXXXXX B@XXXB` ` Xc` X@BX` X`XXXXX`XXXXX XXXXXXXXX@@B@BB@B@@BXXXB@ @@ XXXXXXXXXXXXXXXBB @B B@@XXXXXXXXXXXX XX@BX@@B BB B XXXXXXXXXX B @ @ XXXXXXX@XB X@@XXXXXXXBBX``BBBXXBX` X`X` XX@` BcX` BcX`@` @`@` XX` X@X`XX`XXXXXXXX`XXXXXXXXXXXXXXXXXXXXXXXXXB@B@@@B@B@@B@@BB@@B@BBXXXXXXXXXXB@ @ @ XB@@X@@@ BBXXXXXXXXXXXXXXXXXXXXXXXXXXXXBBBBBXXXXXXXXXBXXXXXXXXXXB @@B @ @ BB@@@X@@B XBXXXXXXXXXXBB @B BXXXXXXXXXXXXXXXXXXXBXXX XXXXXXXXXX@@@@@ B@@@B BXXXXXXXXXXXXXXXXXBBBBXBBXX BBc` @@@XXXXX` XB@`XB` X`X@@@X` BXBc@` @` XX` XX` X` X` B` @`X`@` XBX` @` XB` XXXXXXXXXXB`XXXXXXX@XXXXXXXXXXXB XX@XXXXXXXXXXXB@@@BB@@@B@BBB@@BBBXXXXX@@ X@B@@@@ @ BXXB XX XXB@BXXXXXXXXXXXXXXXXXXXXXXXXBX@B X BXXXXXXXXXBXXXXXXXX@@@B@@@@BBB @ @ BBB XXXXXXXXXXXXXXXB@@BXB@BXXXXXXXXXXXXXBXX@@XBXXXXXXXXX@X@@ B@BXXB XXXXXX@XXXXXXXXXBBBXBB`XXXXXXXXXXc`XXX@@@BB`XB@BB```@`@@`X X@` @X` @X`XXB` XBcBX`B``XXXXXXXXXXXXXBXX@@ B B @ X XXXX @@@ XBB XXBB @B B @XXB@ @XXXXXXXXXXXXXXXXXXXX XXX XXB @ @ @XX @ B @ B BBB XXXXXXXXXXXX@@@@ B B BXXXXXXXXXXXXXX@BXXBXX@` X@@Bc` @`B` X` @XXXXBXXB`XXX@@ BBXXXXX@ B XXXXXX@ B XX@Bc`Рассмотрим другое упорядоченное покрытие цепями: на этот раз, опираясь на теорему Дилуорса, покроем решетку числом цепей, равным ее ширине.
Пусть C1 = (a, b, e, f ) , C2 = (c, d). В этом случае вершины получат следующиекодировки:(00011) −→ (0, 0) ,(00101) −→ (1, 0) ,(00110) −→ (2, 0) ,(01001) −→ (1, 1) ,(01010) −→ (2, 1) ,(10001) −→ (1, 2) ,(01100) −→ (3, 1) ,(10010) −→ (2, 2) ,(10100) −→ (3, 2) ,(11000) −→ (4, 2) .Такое отображение также имеет геометрическую интерпретацию: оно соответствует вложению указанной решетки в60ГЛАВА 1. КОМБИНАТОРИКАдвумерный параллелепипед с целочисленными координатами, лежащими в пределах [0, 4] × [0, 2].c` (4, 2)@c` (3, 2) @` (4, 1)@@c` (2, 2) @c` (3, 1) @`@@c` (1, 2) @c` (2, 1) @` (3, 0)@@` (0, 2) @c` (1, 1) @c` (2, 0)@@@` (0, 1) @c` (1, 0)@@c` (0, 0)(4, 0)Обычно двумерный параллелепипед такого вида называется прямоугольной решеткой и обозначается L (4, 2)Примеры.1.
Доказать равенство ∑ η k (x, y) = (2δ − ζ )−1 (x, y).k>0 Решение. Используя известные свойства сумм, легко преобразовать левую часть к правой:∑ η k (x, y) = ∑ (ζ − δ )k (x, y) = (δ − (ζ − δ ))−1 (x, y) = (2δ − ζ )−1 (x, y) .k>0k>02. На частичном порядке, представленном на диаграмме Хассе, ввести монотонную нумерацию, в ней найти матрицы дзета-функции и функции Мебиуса, а также определить функцию F , если в скобках указаны значениясуммирующей функции.8(9) a``a 9(3) `a 10(10)@@3(4) a`@`a 6(7) `a 7(4)@@2(3) a``a 4(1)@`a 5(2)@@@a`1(1) Решение.
Непосредственно по определению выписывается матрица дзета-функции:1 1 1 1 1 1 1 1 1 10 1 1 0 0 1 0 1 0 00 0 1 0 0 0 0 1 0 00 0 0 1 0 1 0 1 1 10 0 0 0 1 1 1 1 1 1ζ =0 0 0 0 0 1 0 1 1 10 0 0 0 0 0 1 0 0 10 0 0 0 0 0 0 1 0 00 0 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 0 1Из определяющего функцию Мебиуса свойства, подлежащего доказательству в пункте 2a упражнения 2, находимматрицу функции Мебиуса:1 −1 0 −1 −1 200000 1 −1 00 −1 01000 010000 −1 000 0010 −1 00000 0001 −1 −1 001µ =0 000010 −1 −1 −10 00000100 −10 0000001000 0000000100 000000001611.4.
ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВАВектор суммирующей функции равен (в данной монотонной нумерации)SF = 13412749310Отсюда, используя обращение МебиусаF (x) =∑ SF (y) µ (y, x) ,y6xили, что то же самое, вектор функции F (x) равен произведению вектор-строки на матрицуF = SF · µ.Выполнив необходимые вычисления, получаем, что вектор функции F (x) равенF = 1 2 1 0 1 3 2 1 −4 1 .Упражнения.1. Доказать, что для любой функции алгебры инцидентности справедливо соотношениеf k (x, y) =∑f (x, z1 ) · f (z1 , z2 ) · · · f (zk , y) .x6z1 6z2 6···6zk 6y2.
Доказать следующие равенства:(a)∑ µ (x, z) = ∑ µ (z, y) = δ (x, y),x6z6y(b) ∑x6z6yκ k (x, y) = (2δ− λ )−1 (x, y).k>03. Обосновать следующие утверждения:(a) η k (x, y) = ] {(x, y) -цепи длины ровно k},(b) κ k (x, y) = ] {максимальные (x, y) -цепи длины ровно k},(c) ζ k (x, y) = ] {(x, y) -цепи длины, не превосходящей k},(d) λ k (x, y) = ] {максимальные (x, y) -цепи длины, не превосходящей k}.4. Найти функцию Мебиуса для единичного n-мерного куба.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
