Matematyka.pl

Udowodnić, że liczba matroidów transwersalnych na zbiorze \(\displaystyle{ n}\)-elementowym nie przekracza \(\displaystyle{ 2^{n^2}.}\)

Wydaje mi się, że szacowanie to jest mocno zawyżone bo np. dla n=2

Wypisując bazy zbiorów niezależnych otrzymamy:

1.\(\displaystyle{ \left\{ 1\right\} }\)

2. \(\displaystyle{ \left\{ 2\right\} }\)

3. \(\displaystyle{ \left\{ 3\right\} }\)

4.\(\displaystyle{ \left\{ 1,2\right\} }\)

5. \(\displaystyle{ \left\{ 1,2\right\} \left\{ 1,2\right\} }\)

6.\(\displaystyle{ \left\{ 1\right\} \left\{ 2\right\} }\)

I ewentualnie:

\(\displaystyle{ \emptyset}\)

Co daje 7 rodzin tego typu to jeszcze daleko do:

\(\displaystyle{ 2^{2^2}=16}\)

Chyba, że coś przeoczyłem...

Tranwersalne rodziny kojarzą się z problemem par małżeńskich i grafami dwudzielnymi...

Żeby rodzina: \(\displaystyle{ A_{1}, A_{2},...,A_{n} }\) była tranwersalna to moc zbioru powstałego w wyniku sumy dowolnych \(\displaystyle{ k}\) elementów z tej rodziny musi być większy lub równy \(\displaystyle{ k}\)...

Można do tego podejść w ten sposób, żeby zadać sobie pytanie na ile sposobów:

\(\displaystyle{ A_{1} \cup A_{2} \cup ... \cup A_{s}=S=\left\{ 1,2,3,...,n\right\} }\)

Warunek na zbiory \(\displaystyle{ A_{i}}\) są takie, że są one zbiorami należącymi do rodziny \(\displaystyle{ P(S)}\), mogą być parami równe, ale żaden z nich nie może zawierać się całkiem w jakimś innym...

s takich zbiorów dzieli cały obszar na \(\displaystyle{ 2^s-1}\) rozłącznych obszarów i dość grubym przybliżeniem na rodzinę matroidów o dokładnie k elementach jest ilość funkcji ze zbioru S na zbiór obszarów czyli:

\(\displaystyle{ (2^s-1)^k}\)


Oczywiście rodzina matroidów może mieć od 1 do n elementów zawartych w tych podzbiorach jeżeli jest ich mniej niż n to mogą być wybierane na:

\(\displaystyle{ {n \choose k} }\) - sposobów

wliczając w to zbiór pusty otrzymamy grube szacowanie:

\(\displaystyle{ 1+ \sum_{i=1}^{n} {n \choose i} (2^i-1)^i}\)

Które i tak jest mniejsze od:

\(\displaystyle{ 2^{n^2}}\)...