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

Матроид Вамоса или куб Вамоса — это матроид над восьми элементным множеством, который не изоморфен матричному ни над каким полем. Он назван в честь английского математика Питера Вамоса (Peter Vámos), который первым описал его в неопубликованной рукописи в 1968.

Задание матроида

Пусть [math] E = \{1, 2, 3, 4, 5, 6, 7, 8\}[/math]. Матроид Вамоса [math]V[/math] удобно задать, назвав все его зависимые множества: это все подмножества [math]E[/math], в которых не менее пяти элементов, а также [math]\{1, 2, 5, 6\}, \{1, 2, 7, 8\}, \{3, 4, 5, 6\}, \{3, 4, 7, 8\}, \{5, 6, 7, 8\}[/math].

Доказательство матроидной природы

Сначала убедимся в том, что перед нами действительно матроид. Фактически нуждается в проверке лишь тот факт, что если [math]A[/math] и [math]B[/math] независимые множества и [math]|B| = 3[/math], [math]|A| = 4[/math], то в [math]A[/math] найдется такой элемент [math]e[/math], что [math]B \cup \{e\}[/math] — независимое множество. Когда [math]B \subset A[/math], это очевидно. В противном же случае множество [math] A \setminus B[/math] содержит по меньшей мере два различных элемента. Обозначим их через [math]e1[/math] и [math]e2[/math]. Теперь осталось заметить, что из множеств [math]B \cup \{e1\}[/math] и [math]B \cup \{e2\}[/math] хотя бы одно независимое, так как по условию нет двух зависимых множеств из четырtх элементов, отличающихся одним элементом.

Свойства

• Все циклы матроида Вамоса имеют размер по меньшей мере равный его рангу(максимальный размер независимого множества).
• Матроид Вамоса изоморфен своему двойственному матроиду. Однако он не самодвойственен, так как это требует нетривиальную перестановку элементов.
• Матроид Вамоса не представим ни над каким полем. Это значит, что не существует векторного пространства и системы из восьми векторов в нем, таких что матроид линейной независимости этих векторов изоморфен матроиду Вамоса. То есть матроид Вамоса не является матричным.
• Многочлен Татта матроида Вамоса равен [math]x^4+4x^3+10x^2+15x+5xy+15y+10y^2+4y^3+y^4.[/math]

Матроид Вамоса не представим ни над каким полем - доказательство

Предположим, что существует изоморфный V векторный матроид [math]M = \langle E, J \rangle[/math], где [math]E = \{x1, x2, {{...}} , x8 \}[/math], и для каждого [math]i[/math] вектор [math]x_i[/math] соответствует элементу [math]i[/math] матроида Вамоса. Множество [math]\{x1, x2, x3, x4\}[/math] является базисом [math]M[/math]. Запишем координаты каждого вектора в этом базисе: [math]x_i = (a_{i1}, a_{i2}, a_{i3}, a_{i4})[/math]. Для дальнейшего нам понадобятся также векторы [math]y_i = (a_i1, a_i2, 0, 0)[/math] и [math]z_i = (0, 0, a_i3, a_i4)[/math], где [math]i = 1, 2, {{...}} , 8[/math]. Ввиду линейной зависимости векторов [math]x1, x2, x5, x6[/math] получаем равенство нулю определителя, составленного из координат этих векторов:

Источники информации

• Vámos matroid, wikipedia
• Элементарное введение в матроиды