Ранг матроида

Максимальный размер независимого множества матроида

В математической теории матроидов ранг матроида — это максимальный размер независимого множества в матроиде. Ранг подмножества S элементов матроида — это, аналогично, максимальный размер независимого подмножества S , а функция ранга матроида отображает множества элементов в их ранги.

Функция ранга является одним из фундаментальных понятий теории матроидов, посредством которого матроиды могут быть аксиоматизированы. Функции ранга матроидов образуют важный подкласс функций субмодулярных множеств . Функции ранга матроидов, определенные из некоторых других типов математических объектов, таких как неориентированные графы , матрицы и расширения полей , важны при изучении этих объектов.

Примеры

Во всех примерах E — базовое множество матроида, а B — некоторое подмножество E.

• Пусть M — свободный матроид , где независимые множества — это все подмножества E. Тогда ранговая функция M имеет вид: r ( B ) = | B |.
• Пусть M — равномерный матроид , где независимые множества являются подмножествами E с не более чем k элементами для некоторого целого числа k . Тогда ранговая функция M имеет вид: r ( B ) = min( k , | B |).
• Пусть M — матроид разбиения : элементы E разделены на категории, каждая категория c имеет емкость k _c , а независимые множества — это те, которые содержат не более k _c элементов категории c . Тогда ранговая функция M имеет вид: r ( B ) = sum _c min( k _c , | B _c |) где B _c — подмножество B , содержащееся в категории c .
• Пусть M — графический матроид , где независимые множества — это все ациклические множества ребер ( леса ) некоторого фиксированного неориентированного графа G. Тогда ранговая функция r ( B ) — это число вершин в графе за вычетом числа связных компонентов B (включая компоненты с одной вершиной).

Свойства и аксиоматизация

Ранговая функция матроида подчиняется следующим свойствам.

(R1) Значение ранговой функции всегда является неотрицательным целым числом , а ранг пустого множества равен 0.

(R2) Для любых двух подмножеств и из , . То есть ранг является субмодулярной функцией множества . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle E}$ ${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)}$

(R3) Для любого множества и элемента , . ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$

Эти свойства могут быть использованы в качестве аксиом для характеристики ранговой функции матроидов: каждая целочисленная субмодулярная функция множества на подмножествах конечного множества, которая подчиняется неравенствам для всех и является ранговой функцией матроида. ^{[1] [2]} ${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$ ${\displaystyle A}$ ${\displaystyle x}$

Вышеуказанные свойства подразумевают дополнительные свойства:

• Если , то . То есть ранг является монотонной функцией . ${\displaystyle A\subset B\subset E}$ ${\displaystyle r(A)\leq r(B)\leq r(E)}$
• ${\displaystyle r(A)\leq |A|}$.

Другие свойства матроида из ранга

Ранговую функцию можно использовать для определения других важных свойств матроида:

• Множество является независимым тогда и только тогда, когда его ранг равен его мощности, и зависимым тогда и только тогда, когда его мощность больше ранга. ^[3]
• Непустое множество является цепью, если его мощность равна единице плюс его ранг, и каждое подмножество, образованное путем удаления одного элемента из множества, имеет равный ранг. ^[3]
• Множество является базисом, если его ранг равен как его мощности, так и рангу матроида. ^[3]
• Множество замкнуто, если оно максимально для своего ранга, в том смысле, что не существует другого элемента, который можно было бы добавить к нему, сохранив тот же ранг.
• Разница называется нулевым подмножеством . Это минимальное количество элементов, которое необходимо удалить, чтобы получить независимое множество. ^[4] ${\displaystyle |A|-r(A)}$ ${\displaystyle A}$ ${\displaystyle A}$
• Коранг подмножества может относиться как минимум к двум различным величинам: некоторые авторы используют его для обозначения ранга в двойственном матроиде, в то время как другие авторы используют коранг для обозначения разности . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle r^{*}(A)=|A|+r(E\setminus A)-r(E)}$ ${\displaystyle r(E)-r(A)}$

Ранги специальных матроидов

В теории графов ранг схемы (или цикломатическое число) графа — это коранг соответствующего графического матроида ; он измеряет минимальное количество ребер, которые необходимо удалить из графа, чтобы оставшиеся ребра образовали лес. ^[5] Несколько авторов изучали параметризованную сложность алгоритмов графа, параметризованных этим числом. ^{[6] [7]}

В линейной алгебре ранг линейного матроида , определяемый линейной независимостью от столбцов матрицы , является рангом матрицы ^[8] , а также размерностью векторного пространства, охватываемого столбцами.

В абстрактной алгебре ранг матроида, определяемый из наборов элементов в расширении поля L / K посредством алгебраической независимости, известен как степень трансцендентности . ^[9]

Функции ранга матроида как функции полезности

Функции ранга матроида (MRF) использовались для представления функций полезности агентов в задачах справедливого распределения предметов . Если функция полезности агента является MRF, это означает, что:

• Полезность агента имеет убывающую доходность (это следует из того факта, что MRF является субмодулярной функцией);
• Предельная полезность агента для каждого элемента является дихотомической (бинарной) — либо 0, либо 1. То есть добавление элемента в набор либо не добавляет полезности, либо добавляет полезность, равную 1.

Для этой настройки известны следующие решения:

• Бабаиофф, Эзра и Фейдж ^[10] разрабатывают детерминированный полиномиальный механизм истины , называемый Prioritized Egalitarian, который выводит доминирующее распределение Лоренца, которое, следовательно, также является EFX ₀ , максимизирует произведение полезностей, достигает 1/2-дробной доли максимина и достигает полной доли максимина, когда оценки являются аддитивными. Со случайными приоритетами этот механизм также является ex-ante свободным от зависти . Они также изучают e -дихотомические оценки, в которых предельная полезность либо неположительна, либо находится в диапазоне [1,1+ e ].
• Бенаббу, Чакраборти, Игараши и Зик ^[11] показывают, что в этой ситуации каждое оптимальное по Парето распределение максимизирует сумму полезностей ( утилитарное благосостояние ), множество распределений, которые максимизируют симметричную строго вогнутую функцию f по всем распределениям с максимальной суммой, не зависит от выбора f , и все эти распределения, максимизирующие f, являются EF1. Это подразумевает, что распределения с максимальным произведением являются лексимин-оптимальными распределениями, и все они являются max-sum и EF1. Они также представляют алгоритм с полиномиальным временем, который вычисляет max-sum и распределение EF1 (которое не обязательно максимизирует вогнутую функцию), и алгоритм с полиномиальным временем, который максимизирует вогнутую функцию для особого случая MRF, основанного на сопоставлении с максимальной мощностью в двудольных графах.

Функции матроидного ранга являются подклассом валовых замещающих оценок .

Смотрите также

• Ранг оракула

Ссылки

1. Шикаре, ММ; Вафаре, БН (2004), Комбинаторная оптимизация, Alpha Science Int'l Ltd., стр. 155, ISBN 9788173195600.
2. Валлийский, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 8, ISBN 9780486474397.
3. Oxley (2006), стр. 25.
4. Оксли (2006), стр. 34.
5. Берж, Клод (2001), «Цикломатическое число», Теория графов, Courier Dover Publications, стр. 27–30, ISBN 9780486419756.
6. Копперсмит, Дон ; Вишкин, Узи (1985), «Решение NP-трудных задач в «почти деревьях»: покрытие вершин», Дискретная прикладная математика , 10 (1): 27–45, doi : 10.1016/0166-218X(85)90057-5 , Zbl  0573.68017.
7. Фиала, Иржи; Клокс, Тон; Краточвил, Ян (2001), «Сложность λ-разметок с фиксированным параметром», Discrete Applied Mathematics , 113 (1): 59–72, doi : 10.1016/S0166-218X(00)00387-5 , Zbl  0982.05085.
8. Оксли, Джеймс Г. (2006), Теория матроидов , Oxford Graduate Texts in Mathematics, т. 3, Oxford University Press, стр. 81, ISBN 9780199202508.
9. Линдстрём, Б. (1988), «Матроиды, алгебраические и неалгебраические», Алгебраическая, экстремальная и метрическая комбинаторика, 1986 (Монреаль, PQ, 1986) , London Math. Soc. Lecture Note Ser., т. 131, Кембридж: Cambridge Univ. Press, стр. 166–174, MR  1052666.
10. Бабаиофф, Моше; Эзра, Томер; Фейге, Уриэль (27.07.2020). «Справедливые и правдивые механизмы дихотомических оценок». arXiv : 2002.10704 [cs.GT].
11. Бенаббу, Навал; Чакраборти, Митхун; Игараши, Аюми; Зик, Яир (2020). Поиск справедливого и эффективного распределения, когда оценки не сходятся . Конспект лекций по информатике. Том 12283. С. 32–46. arXiv : 2003.07060 . doi :10.1007/978-3-030-57980-7_3. ISBN 978-3-030-57979-1. S2CID  208328700.