Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Orientiertes Matroid realisieren
Autor
Universität/Hochschule Orientiertes Matroid realisieren
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1679
Wohnort: Chile, Ulm
  Themenstart: 2018-04-12

Ausgehend von einer nichtentarteten Chirotopiefunktion (Mächtigkeit 6, Rang 3) für ein uniformes orientiertes Matroid möchte ich eine Vektoren-Grundmenge in $\mathbb{Q}^3$ dazu finden, oder aber zum Schluss kommen, dass keine solche existiert. Jedes uniforme Matroid ist $\mathbb{Q}$-linear und hat demzufolge auch irgendeine Orientierung, aber es ist (mir) nicht klar, dass jede mögliche Orientierung so herleitbar ist. Wenn ich die Literatur richtig verstanden habe, benötigen mögliche Gegenbeispiele freilich mehr als 6_Vektoren. Ich weiß nicht, wie ich dafür systematisch vorgehen kann; für die Chirotopiefunktion habe ich nur eine Grundmenge von Indices $\{0,1,\ldots,5\}$ und keinerlei Vektoren. Selbst falls dieses Problem $\mathcal{NP}$-schwierig sein sollte, dürfte das bei nur $\left(6\atop3\right)=20$ Vektorbasen eigentlich kein Thema sein. Von diesem Webort erfahre ich, dass meine Chirotopiefunktion zu maximal einem von vier Matroiden gehören kann, aber ich wüsste auch nicht herauszufinden, zu welchem der dort aufgezählten. Meine Chirotopiefunktion ist von allen diesen verschieden, aber vermutlich "isomorph" zu einer davon. Wer kennt sich auf diesem namensträchtigen Planeten mit orientierten Matroiden aus?


   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1679
Wohnort: Chile, Ulm
  Beitrag No.1, vom Themenstarter, eingetragen 2018-05-05

Mir ist inzwischen klar geworden, dass es für jede Mächtigkeit $n$ der Matroid-Grundmenge und für jeden Rang $r$ mit $1\le r\le n$ ein uniformes orientiertes Matroid gibt, das rational realisierbar ist und ein Chirotop aus lauter Pluszeichen hat. Aber gibt es auch orientierte uniforme Matroide, die NICHT rational realisierbar sind? Jedem orientierten uniformen Matroid kann man ein nichtorientiertes uniformes Matroid zuordnen, welches dann auch rational realisierbar ist, aber es werden ja verschiedenene orientierte Matroide demselben nichtorientierten Matroid zugeordnet.


   Profil
Ren
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 18.02.2021
Mitteilungen: 1
  Beitrag No.2, eingetragen 2021-02-18

Hallo Goswin, Ein Beispiel für ein orientiertes nicht rational realisierbares Matroid (sehe nicht, warum es nicht uniform sein sollte), kenne ich von Arrangements von Hyperebenen: Man nehme das reguläre Pentagon in der reellen projektiven Ebene \(\mathbb{P}^2(\mathbb{R})\) und betrachte das Arrangement gegeben durch die 5 Geraden durch die Seiten des Pentagons und die 5 Geraden gegeben durch die Symmetrieachsen. Diese 10 Geraden korrespondieren zu 10 reellen Ebenen, welche durch Linearformen aus \((\mathbb{R}^3)^*\) beschrieben werden können, die dann wiederum die Grundmenge eines orientierten Matroids bilden (Man bemerke, dass lineare Abhängigkeit von 3 Linearformen bedeutet, dass die 3 korrespondierenden Ebenen sich in einer Gerade schneiden, bzw im Projektiven schneiden sich die 3 Geraden dann in einem Punkt). Dieses Matroid ist über \(\mathbb{Q}\) nicht realisierbar, sondern erst über \(\mathbb{Q}(\sqrt{5})\). Hoffe, das hilft und habe nichts übersehen. Liebe Grüße, Ren


Wahlurne Für Ren bei den Matheplanet-Awards stimmen
   Profil
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1679
Wohnort: Chile, Ulm
  Beitrag No.3, vom Themenstarter, eingetragen 2021-02-21

Hallo Ren, vielen Dank für deine informative Antwort und herzlich willkommen auf Matroids Matheplaneten! Für mich bist du bereits als "Neukommer des Jahres 2021" nominiert, da es extrem unüblich ist, dass Neukommer da weiterhelfen, wo der Rest dieses doch relativ gut beratenen Planeten anscheinend am Ende seiner Kunst bzw Zeit war (die Frage war fast drei Jahre alt!). Deine Antwort motiviert mich, lineare orientierte Matroide etwas näher zu betrachten. Mein eigentliches Interesse sind Pivotverfahren in der Linearen Optimierung, und in der Praxis sind die Aufgaben dort immer rationalzahlig, obwohl sich die Theorie auch für reelle Zahlen bewahrheitet. Die genaue Beziehung zwischen Pivotverfahren, Johnsongraphen, und linearen orientierten Matroiden ist mir noch nicht ganz klar, aber irgendwie wichtig, denn verschiedene Ergebnisse der orientierten Matroiden wurden in die Lineare Optimierung hinübertransponiert. Auf ein Wiederschreiben grüßt Goswin


Wahlurne Für Goswin bei den Matheplanet-Awards stimmen
   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
StefanVogel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.11.2005
Mitteilungen: 3969
Wohnort: Raun
  Beitrag No.4, eingetragen 2021-12-04

\quoteon(2018-04-12 19:56 - Goswin im Themenstart) Ausgehend von einer nichtentarteten Chirotopiefunktion (Mächtigkeit 6, Rang 3) für ein uniformes orientiertes Matroid möchte ich eine Vektoren-Grundmenge in $\mathbb{Q}^3$ dazu finden... \quoteoff Hallo Goswin, eine Chirotopiefunktion \(\chi(i,j,k)="+"\) verstehe ich so, dass von Punkt \(P_i\) aus in Richtung \(P_j\) gesehen der Punkt \(P_k\) links von \(P_j\) liegt und so kann ich schon diese drei Punkte zeichnen. Dann nehme ich die Chirotopiefunktion zu einem weiteren Punkt \(P_l\) hinzu, beispielsweise \(\chi(i,j,l)="-"\), \(\chi(i,k,l)="-"\), \(\chi(j,k,l)="+"\). Das bedeutet dann, \(P_l\) liegt von \(P_i\) aus gesehen rechts von \(P_j\) und rechts von \(P_k\) und von \(P_j\) aus gesehen links von \(P_k\). So zeichne ich \(P_l\) ein. Auf die genauen Koordinaten kommt es nicht an, nur die Lagebeziehung muss erfüllt sein. Genauso zeichne ich die restlichen drei Punkte. Damit es Punkte in $\mathbb{Q}^3$ werden, genügt es, eine dritte Koordinate z=1 zu ergänzen. \quoteon Von diesem Webort erfahre ich, dass meine Chirotopiefunktion zu maximal einem von vier Matroiden gehören kann, aber ich wüsste auch nicht herauszufinden, zu welchem der dort aufgezählten. Meine Chirotopiefunktion ist von allen diesen verschieden, aber vermutlich "isomorph" zu einer davon. \quoteoff Das ist jetzt dieser Webort IC(6,3,1) bis IC(6,3,4). Die Zuordnung geht über einen Zwischenschritt, zu welcher Punktkonfiguration OT(6,3,1) bis OT(6,3,16) die gezeichneten Punkte gehören. Dazu gibt es eine graphische Darstellung dieser Punktkonfigurationen in A graph theoretical approach for reconstruction and generation of oriented matroids Seite 153 (pdf-Viewer Seite 173) die ersten 16 Skizzen. Da kann man vergleichen, zu welcher Lagebeziehung die gezeichneten Punkte gehören, ob die konveke Hülle ein Drei-, Vier-, Fünf-, oder Sechseck ist und wie die restlichen Punkte im Inneren verteilt sind. Dann muss man nur noch (einmalig) feststellen, zu welchem orientierten Matroíd die einzelnen Punktkonfigurationen gehören. Mit der Methode aus dem anderen Thread (Richtung einzelner Vektoren umdrehen) erhalte ich OT(6,3,1) und OT(6,3,2) gehören zu IC(6,3,1), OT(6,3,3) bis OT(6,3,7) zu IC(6,3,2), OT(6,3,8) bis OT(6,3,14) zu IC(6,3,3) und OT(6,3,15) und OT(6,3,16) zu IC(6,3,4). Viele Grüße, Stefan


Wahlurne Für StefanVogel bei den Matheplanet-Awards stimmen
   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]