Сильвестр матроид

В теории матроидов матроид Сильвестра — это матроид, в котором каждая пара элементов принадлежит трехэлементной схеме ( треугольнику ) матроида. ^[1]^[2]

Пример

The $n$ -точечная линия (т.е. однородный матроид ранга 2 на $n$ элементы, $U{}_{n}^{2}$ ) является матроидом Сильвестра, поскольку каждая пара элементов является базисом, а каждая тройка — схемой.

Матроид Сильвестра третьего ранга может быть сформирован из любой системы троек Штейнера , определив линии матроида как тройки системы. Матроиды Сильвестра третьего ранга также могут быть образованы из конфигураций Сильвестра – Галлаи , конфигураций точек и прямых (в неевклидовых пространствах) без двухточечной прямой. Например, плоскость Фано и конфигурация Гессе порождают матроиды Сильвестра с семью и девятью элементами соответственно и могут быть интерпретированы либо как тройные системы Штейнера, либо как конфигурации Сильвестра – Галлая.

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

Матроид Сильвестра с рангом $r$ должен иметь по крайней мере $2^{r}-1$ элементы; эта оценка точна только для проективных пространств над GF(2) , примером которых является плоскость Фано. ^[3]

В матроиде Сильвестра каждый независимый набор может быть дополнен еще одним элементом, чтобы сформировать схему матроида. ^[1]^[4]

Матроиды Сильвестра (кроме $U{}_{n}^{2}$ ) не могут быть представлены над действительными числами (это теорема Сильвестра-Галлаи ) и не могут быть ориентированы . ^[5]

История

Матроиды Сильвестра были изучены и названы Мерти (1969) в честь Джеймса Джозефа Сильвестра , поскольку они нарушают теорему Сильвестра-Галлая (для точек и линий на евклидовой плоскости или в евклидовых пространствах более высокой размерности ), согласно которой для каждого конечного набора точек существует представляет собой линию, содержащую только две точки.

Ссылки

^ Перейти обратно: ^а ^б Мурти, USR (1969), «Матроиды Сильвестра», «Недавний прогресс в комбинаторике» (Труды Третьей конференции Ватерлоо по комбинаторике, 1968) , Нью-Йорк: Academic Press, стр. 283–286, MR 0255432 .
^ Уэлш, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 297, ISBN 9780486474397 .
^ Мурти, USR (1970), «Матроиды со свойством Сильвестра», Mathematical Equations , 4 (1–2): 44–50, doi : 10.1007/BF01817744 , MR 0265186 , S2CID 189832452 .
^ Брайант, Фольксваген; Доусон, Дж. Э.; Перфект, Хейзел (1978), «Пространства наследственных цепей» , Mathematical Composition , 37 (3): 339–351, MR 0511749 .
^ Циглер, Гюнтер М. (1991), «Некоторые минимальные неориентируемые матроиды третьего ранга», Geometriae Dedicata , 38 (3): 365–371, doi : 10.1007/BF00181199 , MR 1112674 , S2CID 14993704 .

[m69-1] Перейти обратно: ^а ^б Мурти, USR (1969), «Матроиды Сильвестра», «Недавний прогресс в комбинаторике» (Труды Третьей конференции Ватерлоо по комбинаторике, 1968) , Нью-Йорк: Academic Press, стр. 283–286, MR 0255432 .

[2] Уэлш, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 297, ISBN 9780486474397 .

[3] Мурти, USR (1970), «Матроиды со свойством Сильвестра», Mathematical Equations , 4 (1–2): 44–50, doi : 10.1007/BF01817744 , MR 0265186 , S2CID 189832452 .

[4] Брайант, Фольксваген; Доусон, Дж. Э.; Перфект, Хейзел (1978), «Пространства наследственных цепей» , Mathematical Composition , 37 (3): 339–351, MR 0511749 .

[5] Циглер, Гюнтер М. (1991), «Некоторые минимальные неориентируемые матроиды третьего ранга», Geometriae Dedicata , 38 (3): 365–371, doi : 10.1007/BF00181199 , MR 1112674 , S2CID 14993704 .

[1]

[2]

[3]

[4]

[5]