Содержание к диссертации
Введение
1. Аналог теоремы Биркгофа-Уитни для наследственных систем 18
1.1. Теорема Биркгофа-Уитни 18
1.2. Решётки замкнутых множеств конечных наследственных систем 24
1.3. Решётки замкнутых множеств бесконечных наследственных систем 31
2. Представление наследственных систем в терминах замы-канияивтерминах циклов 37
2.1. Эквивалентные определения матроида 38
2.2. Обобщение соответствия между матроидами и операторами замыкания 42
2.3. Эквивалентные определения наследственной системы . 45
3. Задачи оптимизации модулярных и супермодулярных функцийнапорядковых идеалах 50
3.1. Задача максимизации модулярной функции на L-матроиде 51
3.2. Задача максимизации модулярной функции на порядковом идеале 59
3.3. Задача минимизации супермодулярной функции на L-матроиде 68
Заключение 73
Литература 74
- Решётки замкнутых множеств конечных наследственных систем
- Решётки замкнутых множеств бесконечных наследственных систем
- Обобщение соответствия между матроидами и операторами замыкания
- Задача максимизации модулярной функции на порядковом идеале
Решётки замкнутых множеств конечных наследственных систем
Работы Дилуорса [47,48], Радо [63,64] и Татта [67-69] вызвали увеличение интереса к матроидам, исследование которых наиболее активно велось в 70-80-х гг. XX в. и продолжается в наше время. Как постепенно выяснилось, матроиды сочетают в себе черты многих объектов из различных областей математики (линейная алгебра, геометрия, теория графов, теория трансверсалей и т. д.). В процессе развития теории матроидов было предложено значительное количество их обобщений, таких как полиматроиды [50], целочисленные полиматроиды [17], суперматро-иды [49] (см. также [30]), базисные системы [19], матроиды Кокстера [44].
Наиболее полно теория матроидов изложена в книгах [70, 71]. Теоретико-множественный подход, базирующийся на определении матроида в терминах замыкания, достаточно подробно представлен в монографии Айгнера [2], где также приводятся некоторые геометрические аспекты теории матроидов. В книге Асанова, Баранского и Расина [3] содержится введение в теорию матроидов, основанное на этом же подходе. Изложение элементарных основ теории матроидов можно найти в учебнике Емеличева, Мельникова, Сарванова и Тышкевич [21].
С каждой наследственной системой Н = (V, Л) тесно связана дополнительная система или косистема Н , семейство зависимых множеств которой определяется как V = {V \ А : А Є А}. Нетрудно проверить, что семейства независимых множеств, баз и циклов системы Н могут быть заданы как А = {V \ D : D Є Т }, В = {V \ С : С Є С}, С = {V \ В : В Є В}. Ясно, что (Н1) = Н, так что наследственные системы Н и Н взаимно дополнительны.
Наследственная система, дополнительная к матроиду, называется коматроидом. Как и матроиды, коматроиды представляют собой универсальные комбинаторные объекты, имеют довольно много различных аксиоматических определений, и также играют ощутимую роль в комбинаторной оптимизации [29]. Решётки
Точной верхней гранью УХ подмножества X частично упорядоченного множества L называется наименьший из элементов множества {а Є L : х а Ух Є X}, а точной нижней гранью /\Х — наибольший из элементов множества {а Є L : х а Ух Є X}. Решёткой называется частично упорядоченное множество L, в котором любое двухэлементное подмножество {х, у} имеет точную нижнюю грань х Л у и точную верхнюю грань х У у.
Наименьший элемент решётки, если он существует, называется нулём решётки и обозначается 0; аналогично, наибольший элемент, если он существует, называется единицей решётки и обозначается 1. В частности, любая конечная решётка содержит нуль и единицу.
Говорят, что элемент решётки у покрывает элемент х (обозначается х -у), если х у и из соотношения х z у следует у = z. Атомами (или точками) решётки называются элементы, покрывающие 0. Решётка называется атомарной (точечной), если каждый её элемент является точной верхней гранью атомов. Решётка называется полумодулярной, если для любых её элементов х, у выполняется соотношение х Л у -х = у -х У у. Решётка называется геометрической, если она является атомарной, полумодулярной и не содержит бесконечных цепей. Решётка называется дистрибутивной, если для любых её элементов х, у, z выполняется соотношение х Л {у У z) = (х Л у) У (х Л z). Известно, что класс конечных булевых алгебр совпадает с классом дистрибутивных геометрических решёток [2].
Фундаментальная теорема Биркгофа-Уитни, раскрывающая связь между матроидами и геометрическими решётками, привела к тому, что понятие матроида стало центральным в комбинаторной теории решёток.
Матроиду М = (V, ср) сопоставим решетку L(V) замкнутых подмножеств V, упорядоченных по включению. Операции определяются следующим образом: X Л У = XP\Y, XyY = X UY для любых X, Y Є L(V). Имеет место следующее утверждение (теорема Биркгофа-Уитни, [2]). Решётка L(V) замкнутых множеств матроида — геометрическая. Обратно, если L — геометрическая решётка с непустым множеством атомов V, то пара М = (V, ср), где tp(X) = {v Є V : v VX}; является обыкновенным матроидом, a f : L — L(V),f(x) = {v Є V : v х} — изоморфизм решёток.
По этой причине в книге Биркгофа [7] геометрические решётки названы матроидными.
В общем случае, рассматривая некоторый конкретный класс С пространств замыкания, можно поставить вопрос о взаимосвязи класса С и класса С 1(C) решёток замкнутых подмножеств пространств, принадлежащих С. Другими словами, в какой степени сложность класса С определяет сложность С 1(C) и какие ограничения на пространства из С следует наложить, чтобы класс С 1(C) обладал определенными решёточными свойствами? Для фиксированного класса С актуальны проблемы описания и аксиоматизации класса С 1(C) и класса конечных решёток, принадлежащих С 1(C), а также описания класса решёток, вложимых в решётки из С 1(C).
Класс С пространств замыкания называется (конечно) решёточно универсальным, если любая (конечная) решётка вложима в решётку замкнутых подмножеств некоторого (конечного) пространства замыкания, принадежащего С.
Проблема вложения алгебраических систем в другие алгебраические системы, обладающие теми или иными свойствами, является классической в алгебре и теории моделей и имеет долгую историю. Одним из первых значительных результатов является теорема Уитмена 1946 г. [72] о представлении решёток решётками полугрупп, утверждающая (в эквивалентной формулировке), что класс всех групп является решёточно универсальным. Тума уточнил [66] результат Уитмена, показав, что интервалы в решётках подгрупп исчерпывают все алгебраические решётки. Другое доказательство этого результата Тумы содержится в работе Репницкого [65]. Исследования строения решёток, вложимых в решёт ки подалгебр различных конкретных классов алгебр ведутся в работах Репницкого [31-33], Семёновой [34-36].
Множество / С L называется порядковым идеалом решётки L, если оно обладает следующим свойством: (х Є I,у х) = у Є I.
Заметим, что данное свойство является аналогом аксиомы наследственности. Таким образом, понятие порядкового идеала является обобщением понятия наследственной системы (семейство независимых множеств наследственной системы мы можем рассматривать как порядковый идеал булевой решётки всех подмножеств конечного множества V).
Дунстан, Инглтон и Уэлш [49] ввели понятие суперматроида как обобщение понятия матроида в частично упорядоченном множестве с нулем. Для конечной решётки L это определение приобретает следующий вид. Пусть I— порядковый идеал в L. Он называется суперматроидом или L-матроидом, если для любого х Є L все максимальные элементы из / П [0, ж] имеют одинаковую высоту h.
Решётки замкнутых множеств бесконечных наследственных систем
Наследственная система Н на множестве V определяется как разбиение семейства 2У всех подмножеств V на два непересекающихся семейства А и Т , где А — система независимости, а Т = 2V \ Л. Множества семейства Т называются зависимыми. Очевидно, что Т обладает свойством наследственности ”вверх”:
Через В обозначается семейство всех баз, т. е. максимальных по включению независимых множеств, через С — семейство циклов, т. е. минимальных по включению зависимых множеств наследственной системы. Очевидно, что каждое из семейств А, В, С и Т однозначно определяет наследственную систему Н, поэтому будем записывать Н = (V, А), Н = (V, В), Н = (V, С) или Н = (V, Т ) в зависимости от того, какая сторона наследственной системы будет нас интересовать.
Понятие матроида было введено Уитни [73]. Наследственная система Н = (V, А) называется матроидом на V, если выполняется аксиома пополнения:
Пусть V — непустое конечное множество, а ср — оператор замыкания. Пара М = (V, ср) называется матроидом (или комбинаторной предгео-метрией) на V, если для всех X (1 V и для любых u,v Е V выполняется аксиома замены: ((/94) (и X, и Є X U {v}) = v Є X U {и}. Можно дать определение и для случая бесконечного V, при этом требуется также выполнение аксиомы конечного базиса: для любого X (1 V ((/95) ЗВ С X (\В\ оо и В = X). Матроид называется обыкновенным (или комбинаторной геометрией), если 0 = 0 и {v} = {v} для любого элемента v Е V. Приведём необходимые определения теории решёток (см. [7]).
Точной верхней гранью УХ подмножества X частично упорядоченного множества L называется наименьший из элементов множества {а Є L : х а Ух Є X}, а точной нижней гранью /\Х — наибольший из элементов множества {а Є L : х а Ух Є X}. Решёткой называется частично упорядоченное множество L, в котором любое двухэлементное подмножество {ж, у} имеет точную нижнюю грань х Л у, и точную верхнюю грань х У у.
Наименьший элемент решётки, если он существует, называется нулём решётки и обозначается 0; аналогично, наибольший элемент, если он существует, называется единицей решётки и обозначается 1. В частности, любая конечная решётка содержит нуль и единицу.
Цепью называется частично упорядоченное множество, в котором для любых двух его элементов х и у имеет место х у или у ж, т. е. X и у сравнимы. Длина конечной цепи из п элементов полагается равной п — \. Длиной решётки L называется точная верхняя грань длин цепей L. Высотой h(x) элемента х Є L, где L — решётка конечной длины, называется точная верхняя грань длин цепей решётки между нулём и х.
Подрешёткой решётки L называется подмножество X С L такое, что если а, & Є I, то а Л ft G X и о V fe G X. Если а Ъ в решётке L, то (замкнутый) интервал [а, &], состоящий из всех элементов х Є L, которые удовлетворяют неравенству а х 6, будет подрешёткой.
Говорят, что элемент решётки у покрывает элемент х (обозначается х -у), если х у и из соотношения х z у следует у = z. Атомами (или точками) решётки называются элементы, покрывающие 0. Решётка называется атомарной (точечной), если каждый её элемент является точной верхней гранью атомов. Решётка называется полумодулярной, если для любых её элементов ж, у выполняется соотношение х Л у -х = у -х V у. Решётка называется геометрической (или мат-роидной), если она является атомарной, полумодулярной и не содержит бесконечных цепей. Здесь и далее будут рассматриваться только решётки конечной длины, т. е. не содержащие бесконечных цепей.
Матроиду М = (V, ср) сопоставим решётку L(V) замкнутых подмножеств V, упорядоченных по включению. Операции в этой решётке определяются следующим образом:
Точно так же будем определять замыкание для наследственных систем, не являющихся матроидами. Как и в случае матроидов, замкнутыми множествами наследственной системы Н = (V, С) называются такие подмножества ІСУ, что X = X. В отличие от матроидов, в наследственных системах аксиома идемпотентности ((/93) X = X может не выполняться (подробнее это будет обсуждаться в главе 2), т. е. замыкание X не обязательно является замкнутым множеством. Определим оператор X — (X) следующим образом: (X)— это минимальное по включению замкнутое множество, содержащее X. Покажем, что оно единственно. Действительно, если предположить, что существуют два таких множества Х\ = Х2, то пересечение Х\ П Х2 будет являться замкнутым, содержать X и содержаться в обоих множествах Х\ и Х2, что противоречит их минимальности. Таким образом, определение корректно.
Легко видеть, что X — (X) — оператор замыкания. Таким образом, замкнутые множества наследственной системы образуют решётку, в которой X AY = XP\Y и X\/Y = (XUY). В случае, когда наследственная система является матроидом, выполнено равенство (X) = X для всех
Наша цель — доказать аналог теоремы Биркгофа-Уитни для наследственных систем. Главная трудность состоит в том, что решётки замкнутых множеств наследственных систем могут не быть атомарными или полумодулярными.
Её замкнутыми множествами являются 0, {4} и V. Решётка L замкнутых множеств системы Н представляет собой цепь из трёх элементов (нуля, единственного атома и единицы). Заметим, что L не атомарна (единицу решётки нельзя представить в виде точной верхней грани атомов). Если мы попытаемся построить для L систему с изоморфной ей решёткой тем же способом, что в теореме 1.1 (прямым сопоставлением атомов решётки элементам системы), то потерпим неудачу. Действительно, легко видеть, что полученная система будет одноэлементным матроидом, содержащим всего лишь два замкнутых множества. Следовательно, нам необходимо предложить и обосновать принципиально иной способ построения по заданной решётке L наследственной системы с изоморфной ей решёткой.
Как будет показано далее, любая непустая решётка, не содержащая бесконечных цепей, изоморфна решётке замкнутых множеств некоторой наследственной системы. В частности, в разделе 1.2 доказывается, что класс решёток замкнутых множеств конечных наследственных систем совпадает с классом всех непустых конечных решёток. Опираясь на этот результат, в разделе 1.3 мы получим аналог теоремы Биркгофа-Уитни для бесконечного случая.
При анализе свойств наследственных систем будет удобно оперировать их наглядным представлением в виде гиперграфов.
Пусть V — непустое конечное множество, Е С 2V— семейство его подмножеств, причём 0 ф Е. Пара G = (V, Е) называется гиперграфом, элементы множества V называются вершинами гиперграфа, а элементы семейства Е — рёбрами гиперграфа. Ребро гиперграфа мощности п называется п-ребром. Ребро гиперграфа мощности 1 называется петлёй. Гиперграф будем называть клаттером, если никакое его ребро не содержит другое ребро в качестве собственного подмножества.
Наследственные системы можно отождествить с клаттерами, рассматривая в качестве рёбер клаттеров циклы наследственных систем. В соответствии с (1.1) можно определить замыкание для наследственных систем в терминах рёбер клаттера: для всех X С V и v Є V Будем называть замкнутыми множествами и независимыми множествами клаттера замкнутые множества и независимые множества соответствующей ему наследственной системы. Рёбра гиперграфов, включающие более двух вершин, будем изображать заштрихованными областями.
Обобщение соответствия между матроидами и операторами замыкания
Рассматриваются задачи оптимизации модулярных и супермодулярных функций на порядковых идеалах и L-матроидах в конечных геометрических решётках. Установлено, что теорема Радо-Эдмондса, справедливая для булевой решётки, не может быть обобщена на геометрические решётки: если для любой модулярной целевой функции жадный алгоритм гарантированно находит оптимальную базу порядкового идеала конечной геометрической решетки, то идеал может и не быть L-матроидом. Для задачи максимизации модулярной функции на порядковом идеале геометрической решётки получена гарантированная оценка точности жадного алгоритма в терминах кривизны порядкового идеала, обобщающая известную оценку Дженкинса-Корте-Хаусмана для задачи максимизации аддитивной функции на системе независимости. Для задачи минимизации неубывающей супермодулярной функции на базах L-матроида, удовлетворяющего аксиоме пополнения, доказана гарантированная оценка точности жадного алгоритма в терминах кривизны целевой функции. Основные результаты третьей главы опубликованы в работах [4–6,14]. 3.1. Задача максимизации модулярной функции на L-матроиде
Приведём необходимые определения. Некоторые определения, относящиеся к теории решёток, уже были даны в начале главы 1.
Решётка L называется модулярной, если для любых x,y,z Є L из условия х z следует равенство х V (у Л z) = (х V у) Л z. Конечная решётка L модулярна в том случае, если она является полумодулярной сверху, т. е. х/\у -х = у -хУу для любых х, у Є L, и полумодулярной снизу, т. е. у -х V у = х Л у -х для любых х,у Е L.
Заметим, что данное свойство является аналогом аксиомы наследственности (A1). Таким образом, понятие порядкового идеала является обобщением понятия наследственной системы (семейство независимых множеств наследственной системы мы можем рассматривать как порядковый идеал булевой решётки всех подмножеств конечного множества).
Дунстан, Инглтон и Уэлш [49] ввели понятие суперматроида как обобщение понятия матроида в частично упорядоченном множестве с нулем. Для конечной решётки L это определение приобретает следующий вид. Пусть I порядковый идеал в L. Он называется суперматроидом или L-матроидом, если для любого х Є L все максимальные элементы из / П [0,х] имеют одинаковую высоту h.
В [49] доказано, что идеал / в конечной модулярной решётке L является L-матроидом, если и только если выполнена одна из следующих эквивалентных аксиом, в некотором смысле обобщающих аксиому пополнения для независимых множеств матроида
Таким образом, в модулярной решётке имеется три эквивалентных определения L-матроида. Но уже в конечной геометрической (немодулярной) решётке аксиомы 1 и 2 неэквивалентны.
В геометрической решётке, учитывая ее атомарность, можно определить аналог матроида, напрямую обобщив аксиому пополнения (A2) для независимых множеств. Обозначим At(L) = {а Є L : а 0}, At(x) = {а Є At(L) : а х] для любого х Є L.
Лемма 3.1. Пусть I — порядковый идеал в конечной геометрической решётке L. Если для него выполняется условие (12) (х, у Є /, h(x) h(y)) = За Є At(x) \ At (у) (у У а Є /), то / является L-матроидом.
Доказательство. Предположим противное: пусть существует х Є L такой, что интервал [0,ж] содержит два максимальных элемента Ъ\ и &2, причём /1(62) h{b\). Из (I2) следует, что существует такой атом а Є At(&2) \ At(bi), что Ъ\У а Є /. Но так как &і х и 62 %, то й &2 і и &і V о і, а так как Ъ\ Ъ\ У а, то &і не может быть максимальным элементом ж, противоречие. Лемма доказана.
Замечание 3.1. Утверждение, обратное лемме 3.1, в общем случае неверно. Не всякий L-матроид обладает свойством (I2).
Пример 3.1. Рассмотрим матроид на множестве {a b c d}, имеющий ровно один цикл {a b c d} (на рис. 3.1 показано его представление в виде гиперграфа). Построим в соответствии с теоремой Биргкофа-Уитни решётку замкнутых множеств этого матроида. Это немодулярная геометрическая решётка, изображённая нарис. 3.2. Метка а соответствует множеству {а}, метка Ъ — множеству {Ь} и т. д. Метками ad и be обозначены базы а У d и Ъ V с порядкового идеала I, являющиеся точными верхними гранями соответствующих Рис. 3.1 атомов. Порядковый идеал I является L-матроидом, но свойство (I2) для него не выполняется (x = bc,y = a). порядковый идеал в конечной геометрической решётке L, w : L — Ш+ — модулярная функция, w(0) = 0. Для решения данной задачи применим жадный алгоритм Gr, который выбирает элементы решётки, начиная с нуля, таким образом, что каждый следующий элемент порядкового идеала должен покрывать предыдущий и возрастание целевой функции на нём должно быть наибольшим.
Задача максимизации модулярной функции на порядковом идеале
Очевидно, что h(sAal) — h(sAal l) 0 для всех і Є 1,..., п. Учитывая (3.5), получаем, что множитель h{s Л аг) — h{s Л аг 1) во всех ненулевых компонентах суммы в правой части равенства должен равняться единице. Заметим также, что этот множитель является ненулевым только при условии s Л аг s Л аг 1. Поэтому равенство (3.6) эквивалентно уже доказанному равенству (3.4).
Доказательство. Рассмотрим произвольный атом а Є At(al) и j — минимальный номер такой, что а Є At(a?) \ At{oi l). Очевидно, j і. В силу полумодулярности L имеем аг- аг 1. Далее, так как а-7-1 V dj = а? 1 V а = а? и a? l l\ dj = а? 1 1\а = 0, то из модулярности w следует w(a) = w{a ) — w{a l) = w(aj) w(ai). Лемма доказана. Лемма 3.5. Пусть L — конечная геометрическая решётка, I — порядковый идеал решётки L, w — модулярная функция на L, w(0) = О, О = Хп ... -Sr, — цепь элементов, построенная в процессе работы жадного алгоритма Gr.
Существует упорядочение множества { 2i,...an} всех атомов решётки L, удовлетворяющее условиям Лемма доказана. Лемма 3.6. Пусть L — конечная геометрическая решётка, I — порядковый идеал решётки L, w — модулярная функция на L, w(0) = О, и атомы L упорядочены в соответствии с леммой 3.5 . Тогда для любого і Є 1,... , п элемент sr, А аг — база аг, где s — база I, найденная G-r Gr г алгоритмом Gr, аг = \J а . Доказательство. Предположим противное, т. е. что для некоторого номера г существует база Ъ элемента аг такая, что b s„ Л аг. Тогда s s /\аг (так как s является базой Л и существует номер к Gr Gr Gr ) шага алгоритма такой, что ж&-1 Ьи Xk Ь. Рассмотрим два возможных случая. 1) Предположим, что ai ф At(xk-i). Покажем, что в этом случае а,-, Ф At(xh). Так как хь Ь, то хь sr, А аг Ь. Учитывая, что хь sr, (как один из элементов, выбранных алгоритмом), получаем Xk а%. Так как Xk-i аг и ai а, то Xk-i У сц о,1, следовательно, Xk-i У сц ф хи. Теперь, поскольку Xk Xk-1, то щ ф At(xk). В силу леммы 3.2 можем выбрать элементы aj Є At(xk) \ At(xk-i) и а Є At(b) \ At(xk-i) (см. рис. 3.9).
Покажем, что dj аг. Заметим, что Xk = Xk-i V dj (так как Xk CLJ и х Xk-i). Если бы имело место aj а, то из Xk-i b аг следовало бы Xk = Xk-i V dj а, противоречие с Xk аг.
Получаем, что j і, откуда в силу упорядочения атомов w(ai) w{a,j). С другой стороны, а b а, откуда в силу леммы 3.4 следует w(a) w{ai). Так как Xk-i Ъ и а 6, то Xk-i V а Є I. Следовательно, если бы имело место и;(а) w(aj), то w(xk) = w(xk-i VCLJ) w{xk-\ Va), и жадный алгоритм на /с-том шаге вместо элемента Xk выбрал бы элемент Xk-i V а. Поэтому w(aj) w(a). Таким образом, w(ai) = w{(ij).
Итак, нашёлся атом aj Є At(xk) такой, что j і и W{CLJ) = w(ai). В силу леммы 3.5 получили противоречие с условием щ ф At(Xk).
Итак, нашелся атом aj ф At(xk-i) такой, что j і и W{CLJ) = w(ai). В силу леммы 3.5 получили противоречие c условием щ Є At(Xk-l).
Таким образом, не существует базы элемента а, большей sr, Л а, значит, sr, Л аг — база аг. Лемма доказана. Рис. 3.11 Следующee утверждение обобщает оценку Дженкинса-Корте-Хаусмана. Теорема 3.4. Пусть L — конечная геометрическая решётка, I — порядковый идеал решётки L, w — модулярная функция на L, w(0) = 0. Тогда для приближённого решения sn задачи (3.1), найденного алго-ритмом Gr, справедлива оценка
Построим нужную нам цепь, удовлетворяющую (3.10). Пусть уже найдены элементы bn = s„, bn-i,..., Ъ;+л. Так как h(bj+-\) = ЫхЛ + 1, то по свойству (I2) существует а Є At(bi+i) \ At(xi) такой, что XiV а Є I (см. рис. 3.12). В силу леммы 3.9 существует элемент Ъ Є CoAt([0 bi+i]), являющийся дополнением атома а в решётке [0,&j+i]. Положим bi = Ъ. По лемме 3.7 da(0) dbi+1(h), в силу леммы 3.10 (1 — Cf)dXiya{xi) rfa(0). Наконец, в силу выбора элемента ХІ+\ жадным алгоритмом
Рис. 3.13 Пример 3.4. На рис. 3.13 изображена атомарная неполумодуляр-ная решётка, рядом с каждым элементом указано значение неубывающей супермодулярной функции f. При любом положительном значении параметра t жадный алгоритм на L-матроиде I находит решение sGr, для которого f(sO) = 8+4 tf(sGr), тогда как величина 1 - cf для данной функции равна 12.
1. Доказан аналог теоремы Биркгофа-Уитни для наследственных систем: показано, что решётка замкнутых множеств любой наследственной системы не содержит бесконечных цепей, и обратно, любая непустая решётка, не содержащая бесконечных цепей, изоморфна решётке замкнутых множеств некоторой наследственной системы. В частности, любая конечная решётка изоморфна решётке замкнутых множеств некоторой конечной наследственной системы.
2. Предложено определение наследственной системы в терминах циклов, эквивалентное определению в терминах замыкания. Охарактеризовано семейство гиперграфов, которое взаимно однозначно соответствует множеству всех операторов слабого замыкания, удовлетворяющих аксиоме замены. Полученное соответствие является обобщением соответствия между матроидами и операторами замыкания, удовлетворяющими аксиоме замены.
3. Для задачи максимизации модулярной функции на порядковом идеале геометрической решётки получена гарантированная оценка точности жадного алгоритма в терминах кривизны порядкового идеала, обобщающая известную оценку Дженкинса-Корте-Хаусмана для задачи максимизации аддитивной функции на системе независимости. Установлено, что теорема Радо-Эдмондса, справедливая для порядкового идеала булевой решётки, не может быть обобщена на геометрические решётки.
4. Для задачи минимизации неубывающей супермодулярной функции на базах L-матроида, удовлетворяющего аксиоме пополнения, доказана гарантированная оценка точности жадного алгоритма в терминах кривизны целевой функции.
