Матроид

[cyb12]

Никак не могу проверить следующий факт: пусть $(E,F_1)$ и $(E,F_2)$ - матроиды, тогда $(E,F)$, где $F=\{I_1\cup I_2|I_1\in F_1, I_2 \in F_2\}$, -матроид. Подскажите, как это вообще доказывать?

[cyb12]

Задача должна решаться по определению. Но что-то не решается...

Свойство наследственности провеяется легко.
Кстати, второе свойство по-разному формулируется. В такой формулировке для матроида $(E,F)$:

$\forall C \subseteq E$, $\forall A,B \subseteq C$, $A,B\in F$ ($A$ и $B$ максимальны по включению в этом смысле) => $|A|=|B|$

у меня получилось показать, что если $A=I'_1\cup I'_2$, $B=I''_1\cup I''_2$, то $|I'_1|=|I''_1|$ и $|I'_2|=|I''_2|$. Но это не помогает.

[Cave]

Странно, я взял аксиоматическое определение из Википедии и проверил три свойства, всё получилось.
Можете в тех терминах сказать, что у вас не получается?

[cyb12]

2ая аксиома оттуда - это наследственность. С ней все понятно. 3я эквивалентна тому что я говорил.
Но если в тех терминах:
Если взять 2 множества $A,B\subseteq E$, $A,B\in F$, $|A|>|B|.$ Нужно показать, что существует $x\in A\setminus B$, такой, что $B \cup \{x\} \in F$.
$A$ и $B$ представимы в виде: $A=I'_1\cup I'_2$, $B=I''_1\cup I''_2$, где $I'_1,I''_1\in F_1$, $I'_2,I''_2\in F_2$.
И никаких идей, где взять этот $x$.
Кстати, верно ли, что либо $|I'_1|>|I''_1|$,либо $|I'_2|>|I''_2|$?

[cyb12]

cyb12 в сообщении #313094 писал(а):

Кстати, верно ли, что либо $|I'_1|>|I''_1|$,либо $|I'_2|>|I''_2|$?

Неверно. Например, если $|I'_1|=|I'_2|=3$, $I'_1$ и $I'_2$ не пересекаются, $I''_1=I''_2$, $|I''_1|=4$.
Непонятно как пользоваться тем, что исходные две пары -- матроиды.

[Cave]

Вторая аксиома гарантирует, что множество $I_1'$ можно заменить на $I_1' \setminus I_2'$ так, что условие $A=I_1'\cup I_2'$ сохранится, но при этом будет $I_1'\cap I_2' = \varnothing$, и аналогично с $I''_1$. После этого одно из приведенных вами неравенств будет верно. Для соответствующей пары и применяем аксиому 3.

[cyb12]

Cave, спасибо!

[cyb12]

Однако.
Если применить аксиому 3 для новых $|I'_1|>|I''_1|$, то получим, что существует $x\in I'_1\setminus I''_1$, т.ч. $\{x\}\cup I''_1 \in F_1.$ И тогда $\{x\}\cup I''_1 \cup I''_2 \in F$ . Но не факт, что $x\in A\setminus B$.Как это показать? Возможно же, что $x \in I''_2$.

[Cave]

Тогда такой $x$ не будет искомым, однако его можно добавить к $I_1''$, при этом мощность этого множества увеличится на 1, а множество $B$ не изменится никак. Значит, мы вновь приходим к такой же ситуации, и процесс можно повторить (для строго рассуждения примените индукцию). В конце будет невозможной ситуация, что $x\in I_2''$, он и будет искомым.