Матроид Вамоса
Матроид Вамоса или куб Вамоса — это матроид над восьми элементным множеством, который не изоморфен матричному ни над каким полем. Он назван в честь английского математика Питера Вамоса (Peter Vámos), который первым описал его в неопубликованной рукописи в 1968.
Задание матроида
Пусть . Матроид Вамоса удобно задать, назвав все его зависимые множества: это все подмножества , в которых не менее пяти элементов, а также .
Доказательство матроидной природы
Сначала убедимся в том, что перед нами действительно матроид. Фактически нуждается в проверке лишь тот факт, что если и независимые множества и , , то в найдется такой элемент , что — независимое множество. Когда , это очевидно. В противном же случае множество содержит по меньшей мере два различных элемента. Обозначим их через и . Теперь осталось заметить, что из множеств и хотя бы одно независимое, так как по условию нет двух зависимых множеств из четырtх элементов, отличающихся одним элементом.
Свойства
- Все циклы матроида Вамоса имеют размер по меньшей мере равный его рангу(максимальный размер независимого множества).
- Матроид Вамоса изоморфен своему двойственному матроиду. Однако он не самодвойственен, так как это требует нетривиальную перестановку элементов.
- Матроид Вамоса не представим ни над каким полем. Это значит, что не существует векторного пространства и системы из восьми векторов в нем, таких что матроид линейной независимости этих векторов изоморфен матроиду Вамоса. То есть матроид Вамоса не является матричным.
- Многочлен Татта матроида Вамоса равен
