Вамос матроид

Матроид без линейного представления

В математике матроид Вамоса или куб Вамоса — это матроид над набором из восьми элементов, который не может быть представлен как матрица над любым полем . Он назван в честь английского математика Питера Вамоса, который впервые описал его в неопубликованной рукописи в 1968 году. ^[1]

Определение

Матроид Вамоса имеет восемь элементов, которые можно рассматривать как восемь вершин куба или прямоугольного параллелепипеда . Матроид имеет ранг 4: все наборы из трех или менее элементов независимы, и 65 из 70 возможных наборов из четырех элементов также независимы. Пять исключений — это четырехэлементные контуры в матроиде. Четыре из этих пяти контуров образованы гранями прямоугольного параллелепипеда (исключая две противоположные грани). Пятый контур соединяет два противоположных ребра прямоугольного параллелепипеда, каждое из которых является общим для двух из выбранных четырех граней.

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

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

Матроид Вамоса является мощеным матроидом , что означает, что все его контуры имеют размер, по крайней мере равный его рангу . ^[2]
Матроид Вамоса изоморфен своему двойственному матроиду , но он не является тождественно самодвойственным (изоморфизм требует нетривиальной перестановки элементов матроида). ^[2]
Матроид Вамоса не может быть представлен ни над каким полем. То есть, невозможно найти векторное пространство и систему из восьми векторов в этом пространстве, такую, что матроид линейной независимости этих векторов будет изоморфен матроиду Вамоса. ^[3] Действительно, это один из наименьших непредставимых матроидов, ^[4] и он служил контрпримером к гипотезе Инглтона о том, что матроиды на восьми или менее элементах все представимы. ^[5]
Матроид Вамоса является запрещенным минором для матроидов, представимых над полем , если оно имеет пять или более элементов. ^[6] Однако невозможно проверить за полиномиальное время , является ли он минором данного матроида , если доступ осуществляется через оракул независимости . ^[7] $F$ $F$ $М$ $М$
Матроид Вамоса не является алгебраическим. То есть не существует расширения поля и набора из восьми элементов , таких, что степень трансцендентности наборов из этих восьми элементов равна ранговой функции матроида. ^[8] $Л/К$ $L$
Матроид Вамоса не является матроидом, разделяющим секрет. ^[9] Матроиды, разделяющие секрет, описывают «идеальные» схемы разделения секрета , в которых любая коалиция пользователей, которая может получить любую информацию о секретном ключе, может узнать весь ключ (эти коалиции являются зависимыми множествами матроида), и в которых общая информация содержит не больше информации, чем необходимо для представления ключа. ^[10] Эти матроиды также имеют приложения в теории кодирования . ^[11]
Матроид Вамоса не имеет сопряженного. Это означает, что двойственная решетка геометрической решетки матроида Вамоса не может быть упорядоченно вложена в другую геометрическую решетку того же ранга. ^[12]
Матроид Вамоса может быть ориентированным . ^[13] В ориентированных матроидах форма теоремы Хана–Банаха следует из определенного свойства пересечения плоскостей матроида; матроид Вамоса представляет собой пример матроида, в котором свойство пересечения неверно, но теорема Хана–Банаха тем не менее выполняется. ^[14]
Полином Тутте матроида Вамоса равен ^[15]
$x^{4}+4x^{3}+10x^{2}+15x+5xy+15y+10y^{2}+4y^{3}+y^{4}.$

Ссылки

^ Вамос, П. (1968), О представительстве структур независимости.
^ ab Oxley, James G. (2006), "Пример 2.1.22", Теория матроидов, Oxford Graduate Texts in Mathematics, т. 3, Oxford University Press, стр. 76, ISBN 9780199202508.
^ Оксли (2006), стр. 170–172.
^ Оксли (2006), Предложение 6.4.10, с. 196. Доказательство представимости каждого матроида с меньшим количеством элементов или с тем же числом, но меньшим рангом было дано Фурнье, Жан-Клодом (1970), "Sur la représentation sur un corps des matroïdes à sept et huit éléments", Comptes rendus de Академия наук , сер. АВ, 270 : A810–A813, MR 0263665.
^ Инглтон, AW (1959), «Заметка о независимых функциях и ранге», Журнал Лондонского математического общества , Вторая серия, 34 : 49–56, doi :10.1112/jlms/s1-34.1.49, MR 0101848 .
^ Оксли (2006), стр. 511.
^ Сеймур, PD ; Уолтон, PN (1981), «Обнаружение миноров матроидов», Журнал Лондонского математического общества , Вторая серия, 23 (2): 193–203, doi :10.1112/jlms/s2-23.2.193, MR 0609098 . Йенсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR 0646772 .
^ Инглтон, AW; Мэйн, RA (1975), «Неалгебраические матроиды существуют», Бюллетень Лондонского математического общества , 7 (2): 144–146, doi :10.1112/blms/7.2.144, MR 0369110 .
^ Сеймур, PD (1992), «О матроидах с разделением секрета», Журнал комбинаторной теории , Серия B, 56 (1): 69–73, doi : 10.1016/0095-8956(92)90007-K , MR 1182458.
^ Брикелл, Эрнест Ф.; Дэвенпорт, Дэниел М. (1991), «О классификации идеальных схем разделения секрета», Журнал криптологии , 4 (2): 123–134, doi : 10.1007/BF00196772.
^ Симонис, Юриаан; Ашихмин, Алексей (1998), «Почти аффинные коды», Designs, Codes and Cryptography , 14 (2): 179–197, doi :10.1023/A:1008244215660, MR 1614357 .
^ Cheung, Alan LC (1974), «Сопряженные элементы геометрии», Canadian Mathematical Bulletin , 17 (3): 363–365, исправление, там же, 17 (1974), № 4, 623, doi : 10.4153/CMB-1974-066-5 , MR 0373976.
^ Бланд, Роберт Г.; Лас Верньяс, Мишель (1978), «Ориентируемость матроидов», Журнал комбинаторной теории , Серия B, 24 (1): 94–123, doi : 10.1016/0095-8956(78)90080-1 , MR 0485461 .
^ Бахем, Ахим; Ванка, Альфред (1988), «Теоремы разделения для ориентированных матроидов», Дискретная математика , 70 (3): 303–310, doi : 10.1016/0012-365X(88)90006-4 , MR 0955127.
^ Меринос, Криэль; Рамирес-Ибаньес, Марселино; Санчес, Гваделупе Родригес (2012), Полином Тутте некоторых матроидов , arXiv : 1203.0090 , Bibcode : 2012arXiv1203.0090M.

[1] Вамос, П. (1968), О представительстве структур независимости.

[oxley-2] Oxley, James G. (2006), "Пример 2.1.22", Теория матроидов, Oxford Graduate Texts in Mathematics, т. 3, Oxford University Press, стр. 76, ISBN 9780199202508.

[3] Оксли (2006), стр. 170–172.

[4] Оксли (2006), Предложение 6.4.10, с. 196. Доказательство представимости каждого матроида с меньшим количеством элементов или с тем же числом, но меньшим рангом было дано Фурнье, Жан-Клодом (1970), "Sur la représentation sur un corps des matroïdes à sept et huit éléments", Comptes rendus de Академия наук , сер. АВ, 270 : A810–A813, MR 0263665.

[5] Инглтон, AW (1959), «Заметка о независимых функциях и ранге», Журнал Лондонского математического общества , Вторая серия, 34 : 49–56, doi :10.1112/jlms/s1-34.1.49, MR 0101848 .

[ox511-6] Оксли (2006), стр. 511.

[7] Сеймур, PD ; Уолтон, PN (1981), «Обнаружение миноров матроидов», Журнал Лондонского математического общества , Вторая серия, 23 (2): 193–203, doi :10.1112/jlms/s2-23.2.193, MR 0609098 . Йенсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR 0646772 .

[8] Инглтон, AW; Мэйн, RA (1975), «Неалгебраические матроиды существуют», Бюллетень Лондонского математического общества , 7 (2): 144–146, doi :10.1112/blms/7.2.144, MR 0369110 .

[9] Сеймур, PD (1992), «О матроидах с разделением секрета», Журнал комбинаторной теории , Серия B, 56 (1): 69–73, doi : 10.1016/0095-8956(92)90007-K , MR 1182458.

[10] Брикелл, Эрнест Ф.; Дэвенпорт, Дэниел М. (1991), «О классификации идеальных схем разделения секрета», Журнал криптологии , 4 (2): 123–134, doi : 10.1007/BF00196772.

[11] Симонис, Юриаан; Ашихмин, Алексей (1998), «Почти аффинные коды», Designs, Codes and Cryptography , 14 (2): 179–197, doi :10.1023/A:1008244215660, MR 1614357 .

[12] Cheung, Alan LC (1974), «Сопряженные элементы геометрии», Canadian Mathematical Bulletin , 17 (3): 363–365, исправление, там же, 17 (1974), № 4, 623, doi : 10.4153/CMB-1974-066-5 , MR 0373976.

[13] Бланд, Роберт Г.; Лас Верньяс, Мишель (1978), «Ориентируемость матроидов», Журнал комбинаторной теории , Серия B, 24 (1): 94–123, doi : 10.1016/0095-8956(78)90080-1 , MR 0485461 .

[14] Бахем, Ахим; Ванка, Альфред (1988), «Теоремы разделения для ориентированных матроидов», Дискретная математика , 70 (3): 303–310, doi : 10.1016/0012-365X(88)90006-4 , MR 0955127.

[15] Меринос, Криэль; Рамирес-Ибаньес, Марселино; Санчес, Гваделупе Родригес (2012), Полином Тутте некоторых матроидов , arXiv : 1203.0090 , Bibcode : 2012arXiv1203.0090M.