Rappresentazione geometrica di un matroide di rango 4

Aug 22 2020

Sto elaborando gli appunti di Oxley sulla teoria dei matroidi (https://www.math.lsu.edu/~oxley/survey4.pdf). L'Esercizio 5.8 richiede una rappresentazione geometrica del matroide associato al grafo$K_5$, il grafo completo su 5 vertici. In questa situazione, una rappresentazione geometrica è un insieme di punti che rappresentano gli elementi dei matroidi e un insieme di "linee" e "piani" tale che vale quanto segue:

  1. Gli insiemi indipendenti sono insiemi di 2 o meno vertici, insiemi di 3 vertici non collineari e insiemi di 4 vertici non complanari

  2. 2 linee si intersecano al massimo in 1 punto

  3. 2 piani si intersecano al massimo in 1 linea (cioè tutti i punti nell'intersezione di 2 piani sono colineari)

(Potrebbe essere possibile farlo con linee e piani reali in modo che le condizioni 2 e 3 siano banali; non sono chiaro su questo dalla dichiarazione del problema.)

Ho problemi a risolvere questo problema in modo specifico (ad esempio per il matorid associato a$K_5$) ma apprezzerei anche alcuni suggerimenti per tecniche generali per disegnare rappresentazioni geometriche di matroidi perché lo trovo difficile anche in 2 dimensioni.

Risposte

2 RandyMarsh Aug 22 2020 at 06:40

La costruzione è essenzialmente: inizia con un circuito corrispondente a un triangolo in$K_5$. Questo circuito è rappresentato da una linea con 3 punti su di essa. Ora scegli un secondo circuito triangolare che condivida un bordo con il primo circuito. Nella rappresentazione quindi la linea corrispondente si interseca con la linea che rappresenta il primo circuito. Ma ora hai 4 punti aggiuntivi che si trovano in altri circuiti. Trova questi circuiti, disegna le loro linee e aggiungi punti di intersezione.

Ti consiglio di seguire la costruzione con software di disegno come Cinderella.2 o GeoGebra.

I triangoli dentro$K_5$sono circuiti (ma non tutti i circuiti sono triangoli), quindi i punti corrispondenti nella rappresentazione devono trovarsi sulle stesse linee. Ci sono 10 triangoli dentro$K_5$, quindi ci sono$10$linee nella rappresentazione.

Lascia che i vertici di$K_5$essere etichettato da$\{1,2,3,4,5\}$, Antiorario.

Possiamo iniziare con un circuito triangolare, ad es$\{12,23,13\}$. Questi corrispondono a tre punti$p_{12}$,$p_{23}$,$p_{13}$sulla stessa linea, chiamalo$l_1$.

Il punto$p_{12}$si trova su altre tre linee, corrispondenti ai circuiti$\{12,25,15\}$e$\{12,24,14\}$. Permettere$l_2$essere la linea con i punti$p_{12}$,$p_{25}$,$p_{15}$.

Ora dobbiamo controllare le dipendenze tra i punti su$l_1$e$l_2$. I bordi$23$e$25$appartengono al circuito$\{23,25,35\}$, e$13$e$15$appartengono al circuito$\{13,15,35\}$. Quindi dobbiamo introdurre un nuovo punto$p_{35}$come intersezione delle due rette$l_3=\{13,15,35\}$e$l_4=\{23,25,35\}$.

Finora non abbiamo lasciato l'aereo in quanto non è possibile trovare alcuna base$\{12,13,15,23,25,35\}$.

Non abbiamo ancora esaurito tutte le righe$p_{12}$, quindi lascia$l_5=\{12,24,14\}$. Questa linea non passa per nessuno dei vertici presenti, se non ovviamente$p_{12}$. Inoltre, il tetraedro$\{12,13,15,14\}$è non piatto perché è una base, cioè corrisponde a uno spanning tree di$K_5$, quindi con questa linea ci stiamo muovendo$\mathbb R^3$.

Finora abbiamo 8 punti. Ci mancano i punti$p_{34}$e$p_{45}$. Il punto$p_{45}$è sull'intersezione delle linee definite dai circuiti$\{14,15,45\}$e$\{24,25,45\}$, quindi aggiungiamo le righe$l_6=\{14,15\}$e$l_7=\{24,25\}$insieme a$p_{45}$come loro intersezione.

Allo stesso modo, il punto$p_{34}$è sull'intersezione delle linee definite dai circuiti$\{13,14,34\}$e$\{23,24,34\}$, quindi aggiungiamo le righe$l_8=\{13,14\}$e$l_9=\{23,24\}$insieme a$p_{35}$come loro intersezione.

Quindi abbiamo 10 punti nella rappresentazione ma solo 9 linee. La linea mancante è$l_{10}$corrispondente al circuito$\{34,35,45\}$. Che questa è in realtà una linea in$\mathbb R^3$è garantita dal teorema di Desargues.