Матроид, заказываемый на базе

В математике матроид с упорядочиваемым базисом — это матроид , который имеет следующее дополнительное свойство, связанное с базисами матроида . ^[1]

Для любых двух оснований $A$ и $B$ существует допустимая обменная биекция , определяемая как биекция $f$ от $A$ к $B$ , такой, что для каждого $a\in A\setminus B$ , оба $(A\setminus \{a\})\cup \{f(a)\}$ и $(B\setminus \{f(a)\})\cup \{a\}$ являются базами.

Это свойство было представлено Бруальди и Скримгером. ^[2]^[3] Матроид со строгой базой упорядочиваемости обладает следующим более сильным свойством:

Для любых двух оснований $A$ и $B$ , существует сильная допустимая обменная биекция , определяемая как биекция $f$ от $A$ к $B$ , такой, что для каждого $X\subseteq A$ , оба $(A\setminus X)\cup f(X)$ и $(B\setminus f(X))\cup X$ являются базами.

Недвижимость в контексте

Базовая упорядочиваемость налагает два требования на функцию $f$ :

Это должна быть биекция;
Для каждого $a\in A\setminus B$ , оба $(A\setminus \{a\})\cup \{f(a)\}$ и $(B\setminus \{f(a)\})\cup \{a\}$ должны быть базы.

Каждое из этих свойств в отдельности легко удовлетворить:

Все базы данного матроида имеют одинаковую мощность, поэтому существует n ! биекции между ними (где n — общий размер базисов). Но не гарантируется, что одна из этих биекций удовлетворяет свойству 2.
Все базы $A$ и $B$ матроида удовлетворяют свойству симметричного базисного обмена , то есть для каждого $a\in A\setminus B$ , существует некоторый $f(a)\in B\setminus A$ , такой, что оба $(A\setminus \{a\})\cup \{f(a)\}$ и $(B\setminus \{f(a)\})\cup \{a\}$ являются базами. Однако не гарантируется, что результирующая функция f будет биекцией - возможно, что несколько $a$ соответствуют одному и тому же $f(a)$ .

Матроиды, которые можно заказать на базе

Каждый матроид раздела строго упорядочивается по основанию. Напомним, что матроид разбиения определяется конечным набором категорий , где каждая категория $C_{i}$ имеет емкость, обозначаемую целым числом $d_{i}$ с $0\leq d_{i}\leq |C_{i}|$ . Основой этого матроида является множество, содержащее ровно $d_{i}$ элементы каждой категории $C_{i}$ . Для любых двух оснований $A$ и $B$ , каждая биекция, отображающая $d_{i}$ элементы $C_{i}\cap A$ к $d_{i}$ элементы $C_{i}\cap B$ является сильной допустимой обменной биекцией.

Каждый трансверсальный матроид сильно упорядочиваем по основанию. ^[2]

Матроиды, которые нельзя заказать на базе

Некоторые матроиды нельзя заказать на базе. Ярким примером является графический матроид на графе K ₄ , т. е. матроид, базами которого являются остовные деревья клики на 4 вершинах. ^[1] Обозначим вершины K ₄ цифрами 1,2,3,4, а ее ребра — цифрами 12,13,14,23,24,34. Обратите внимание, что базы:

{12,13,14}, {12,13,24}, {12,13,34}; {12,14,23}, {12,14,34}; {12,23,24}, {12,23,34}; {12,24,34};
{13,14,23}, {13,14,24}; {13,23,24}, {13,23,34}; {13,24,34};
{14,23,24}, {14,23,34}; {14,24,34}.

Рассмотрим два базиса A = {12,23,34} и B = {13,14,24} и предположим, что существует функция f, удовлетворяющая свойству обмена (свойство 2 выше). Затем:

f (12) должно равняться 14: оно не может быть 24, так как A\{12} + {24} = {23,24,34}, что не является базисом; оно не может быть 13, поскольку B \ {13} + {12} = {12,14,24}, что не является базисом.
f (34) должно равняться 14: оно не может быть 24, так как B\{24} + {34} = {13,14,34}, что не является базисом; оно не может быть 13, поскольку A \ {34} + {13} = {12,13,23}, что не является базисом.

Тогда f не является биекцией — он отображает два элемента A и тот же элемент B. в один

Существуют матроиды, упорядочиваемые по базовому, но не строго упорядочиваемые. ^[4]^[1]

Характеристики

В матроидах с упорядочением по базе допустимая обменная биекция существует не только между базисами, но и между любыми двумя независимыми множествами одинаковой мощности, т. е. любыми двумя независимыми множествами. $A$ и $B$ такой, что $|A|=|B|$ .

Это можно доказать индукцией по разности размеров множеств и размеров базиса (напомним, что все базисы матроида имеют одинаковый размер). Если разница равна 0, то наборы на самом деле являются базами, и это свойство следует из определения матроидов с упорядочением по базе. В противном случае, используя свойство увеличения матроида, мы можем увеличить $A$ в независимый набор $A\cup \{x\}$ и увеличить $B$ в независимый набор $B\cup \{y\}$ . Тогда по предположению индукции существует допустимая обменная биекция $f$ между $A\cup \{x\}$ и $B\cup \{y\}$ . Если $f(x)=y$ , то ограничение $f$ к $A$ и $B$ является допустимой обменной биекцией. В противном случае, $f^{-1}(y)\in A$ и $f(x)\in B$ , так $f$ можно изменить, установив: $f(f^{-1}(y)):=f(x)$ . Тогда ограничение модифицированной функции на $A$ и $B$ является допустимой обменной биекцией.

Полнота

Класс матроидов, заказываемых по базе, завершен . Это означает, что он замкнут относительно операций миноров, двойников, прямых сумм, усечений и индукции ориентированными графами. ^[1]^: 2 Он также замкнут при ограничении, объединении и усечении. ^[5]^: 410

То же самое справедливо и для класса сильно упорядочиваемых по базе матроидов.

Ссылки

^ Jump up to: ^а ^б ^с ^д
Бонин, Джозеф Э.; Савицкий, Томас Дж. (01 января 2016 г.). «Бесконечная семья исключенных несовершеннолетних для строгой базовой упорядоченности» . Линейная алгебра и ее приложения . 488 : 396–429. arXiv : 1507.05521 . дои : 10.1016/j.laa.2015.09.055 . ISSN 0024-3795 . S2CID 119161534 .
- Джозеф Э. Бонин; Томас Дж. Савицкий (апрель 2016 г.). «Исключенные несовершеннолетние для (строго) базовых матроидов» (PDF) .
^ Jump up to: ^а ^б Бруальди, Ричард А.; Скримгер, Эдвард Б. (1 ноября 1968 г.). «Системы обмена, паросочетания и трансверсали» . Журнал комбинаторной теории . 5 (3): 244–257. дои : 10.1016/S0021-9800(68)80071-7 . ISSN 0021-9800 .
^ Бруальди, Ричард А. (1 августа 1969 г.). "Комментарии к базам в структурах зависимостей" . Бюллетень Австралийского математического общества . 1 (2): 161–167. дои : 10.1017/S000497270004140X . ISSN 1755-1633 .
^ А. В. Инглтон. «Матроиды, не подлежащие базовому заказу». В материалах Пятой Британской комбинаторной конференции (Абердинский университет, Абердин, 1975), страницы 355–359. Конгресс Нумерантиум, № XV, Utilitas Math., Виннипег, Ман., 1976.
^ Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, том. 3, Издательство Оксфордского университета, ISBN 9780199202508 .

[:0-1] Jump up to: ^а ^б ^с ^д Бонин, Джозеф Э.; Савицкий, Томас Дж. (01 января 2016 г.). «Бесконечная семья исключенных несовершеннолетних для строгой базовой упорядоченности» . Линейная алгебра и ее приложения . 488 : 396–429. arXiv : 1507.05521 . дои : 10.1016/j.laa.2015.09.055 . ISSN 0024-3795 . S2CID 119161534 .
Джозеф Э. Бонин; Томас Дж. Савицкий (апрель 2016 г.). «Исключенные несовершеннолетние для (строго) базовых матроидов» (PDF) .

[2] Джозеф Э. Бонин; Томас Дж. Савицкий (апрель 2016 г.). «Исключенные несовершеннолетние для (строго) базовых матроидов» (PDF) .

[:1-2] Jump up to: ^а ^б Бруальди, Ричард А.; Скримгер, Эдвард Б. (1 ноября 1968 г.). «Системы обмена, паросочетания и трансверсали» . Журнал комбинаторной теории . 5 (3): 244–257. дои : 10.1016/S0021-9800(68)80071-7 . ISSN 0021-9800 .

[3] Бруальди, Ричард А. (1 августа 1969 г.). "Комментарии к базам в структурах зависимостей" . Бюллетень Австралийского математического общества . 1 (2): 161–167. дои : 10.1017/S000497270004140X . ISSN 1755-1633 .

[4] А. В. Инглтон. «Матроиды, не подлежащие базовому заказу». В материалах Пятой Британской комбинаторной конференции (Абердинский университет, Абердин, 1975), страницы 355–359. Конгресс Нумерантиум, № XV, Utilitas Math., Виннипег, Ман., 1976.

[5] Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, том. 3, Издательство Оксфордского университета, ISBN 9780199202508 .

[1]

[2]

[3]

[4]

[5]