Listing tutte le sezioni interessanti di un tetraedro

Question

aggiornamento risposta, 12/22: utilizzo di observation che c'è un omomorfismo tra le sezioni distinte e permutazioni degli oggetti sul cubo, elencare tutte queste permutazioni rappresentando un gruppo di simmetrie del cubo Peter Shor come un sottogruppo di SymmetricGroup [8] ed usando GroupElements/permute, trovare le assegnazioni baricentro utilizzando SAT solver di Mathematica, set di punti di selezionare con valori singolari distinti, qualche dettaglio in più e codice completo dato here

domanda

Un'interessante sezione 2D è un piano che attraversa il centro di un normale 3D simplex e altri 2 punti ciascuno dei quali è un centroide di alcuni sottoinsiemi non vuoti di vertici. È definito da due sottoinsiemi di vertici. Ad esempio {{1}, {1,2}} dà un piano definito da 3 punti: il centro del tetraedro, il primo vertice e la media del primo e del secondo vertice.

Un insieme interessante di sezioni è un insieme in cui non esistono due sezioni che definiscono lo stesso piano sotto la rietichettatura vertice. Ad esempio, impostare {{{1}, {2}}, {{3}, {4}}} non è interessante. Esiste un approccio efficace per trovare un'interessante serie di sezioni interessanti? Ho bisogno di qualcosa che possa generalizzare a un problema analogo per le sezioni 3D di 7D simplex e finire tutta la notte.

Il mio tentativo di approccio è sotto. Un problema è che se si ignora la geometria, alcune sezioni equivalenti verranno mantenute, quindi ottengo 10 sezioni anziché 3. Un problema più grande è che ho usato la forza bruta e sicuramente non scala e (richiede 10^17 confronti per 7D simplex)

http://yaroslavvb.com/upload/simplex-sections.png

Ecco il codice per generare Mathematica foto sopra.

entropy[vec_] := Total[Table[p Log[p], {p, vec}]]; 
hadamard = KroneckerProduct @@ Table[{{1, 1}, {1, -1}}, {2}]; 
(* rows of hadamard matrix give simplex vertex coordinates *) 

vertices = hadamard; 
invHad = Inverse[hadamard]; 
m = {m1, m2, m3, m4}; 
vs = Range[4]; 

(* take a set of vertex averages, generate all combinations arising \ 
from labeling of vertices *) 
vertexPermutations[set_] := (
    newSets = set /. Thread[vs -> #] & /@ Permutations[vs]; 
    Map[Sort, newSets, {2}] 
    ); 
(* anchors used to define a section plane *) 

sectionAnchors = Subsets[{1, 2, 3, 4}, {1, 3}]; 
(* all sets of anchor combinations with centroid anchor always \ 
included *) 
anchorSets = Subsets[sectionAnchors, {2}]; 
anchorSets = Prepend[#, {1, 2, 3, 4}] & /@ anchorSets; 
anchorSets = Map[Sort, anchorSets, {2}]; 
setEquivalent[set1_, set2_] := MemberQ[vertexPermutations[set1], set2]; 
equivalenceMatrix = 
    Table[Boole[setEquivalent[set1, set2]], {set1, anchorSets}, {set2, 
    anchorSets}]; 
Needs["GraphUtilities`"]; 
(* Representatives of "vertex-relabeling" equivalence classes of \ 
ancher sets *) 
reps = First /@ StrongComponents[equivalenceMatrix]; 

average[verts_] := Total[vertices[[#]] & /@ verts]/Length[verts]; 
makeSection2D[vars_, {p0_, p1_, p2_}] := Module[{}, 
    v1 = p1 - p0 // Normalize; 
    v2 = p2 - p0; 
    v2 = v2 - (v1.v2) v1 // Normalize; 
    Thread[vars -> (p0 + v1 x + v2 y)] 
    ]; 

plotSection2D[f_, pointset_] := (
    simplex = 
    Graphics3D[{Yellow, Opacity[.2], 
     GraphicsComplex[Transpose@Rest@hadamard, 
     Polygon[Subsets[{1, 2, 3, 4}, {3}]]]}]; 
    anchors = average /@ pointset; 
    section = makeSection2D[m, anchors]; 
    rf = Function @@ ({{x, y, z, u, v}, 
     And @@ Thread[invHad.{1, x, y, z} > 0]}); 
    mf = Function @@ {{p1, p2, p3, x, y}, f[invHad.m /. section]}; 
    sectionPlot = 
    ParametricPlot3D @@ {Rest[m] /. section, {x, -3, 3}, {y, -3, 3}, 
     RegionFunction -> rf, MeshFunctions -> {mf}}; 
    anchorPlot = Graphics3D[Sphere[Rest[#], .05] & /@ anchors]; 
    Show[simplex, sectionPlot, anchorPlot] 
    ); 
plots = Table[ 
    plotSection2D[entropy, anchorSets[[rep]]], {rep, reps}]; 
GraphicsGrid[Partition[plots, 3]] 

Answer 1

La soluzione di programmazione corretta è, a grandi linee:

• osservare che i centri vengono a coppie proiettive - così identificare e mantenere solo la metà dei centri che sono in uno o l'altro coperchi semisferici dell'insieme di centri. Le coppie sono composte da complementi l'una dall'altra. Un esempio di regola: tutte fascicoli comprendenti vertice 1, e di quelle sul "equatore", quelli contenenti vertice 2, e su quella di "equatore" set, quelli contenenti vertice 3, e così via ricorsivamente mantenere la metà confine adiacente al più piccolo indicizzato vertice.
• Osservare che per ogni sottogruppo, il sottogruppo è adiacente al vertice 1 o è distante 1 dal semplice. (Causa: ogni nuovo vertice nel tetraedro è attaccato ad ogni precedente vertice del tetraedro - di conseguenza ogni subsimplex è o incidente sul vertice 1 o vertice 1 è collegato a ogni vertice nel simplex.) Di conseguenza ci sono solo due popolazioni di ciascun tipo di subsimplex (rispetto a un vertice specificato). (Possiamo sostituire questa osservazione con la decisione di mantenere solo il membro più piccolo di ogni coppia proiettiva, ma poi la regola per etichettare i vertici è più complicata.)

• I tetraedri sono completamente simmetrici sotto la permutazione delle etichette dei vertici. Di conseguenza, ogni "sezione interessante" equivale ad un'altra sezione che contiene solo il segmento principale dei vertici, cioè può essere identificata tra i vertici. Gamma [1, n] per alcuni n.

• Raccogliendo quanto sopra, scopriamo che c'è una sorpresa da una sezione interessante a una serie di grafici. Per ogni grafico dobbiamo enumerare le appartenenze ai vertici coerenti (descritte più avanti).Tranne che per un vertice, i vertici del grafo sono a coppie

  • La coppia contiene tutti i centri di cardinalità (tutti subsimplices di una data dimensione).
  • Un membro della coppia contiene centri incidente sul vertice 1.
  • L'altro membro della coppia contiene centri non incidente sul vertice 1.
  • Il vertice speciale è o centro contenente tutti i vertici o la sua coppia proiettivo (il "centro vuoto").
  • Se un grafico contiene un membro di una coppia deve (almeno) contenere il membro che contiene i centri incidente su 1 (oi vertici possono essere rinominati per renderlo tale).
• I bordi del grafico sono ponderati. Il peso è il numero di vertici condivisi dai due centri. Esistono restrizioni sul peso in base alla cardinalità dei centri a ciascuna estremità e in base al fatto che i due vertici siano entrambi i primi membri, entrambi i secondi membri o uno di ciascuno. ("Uno di ogni" non può condividere il vertice 1, per esempio.)
• Un grafico è un sottografo completo sull'insieme di vertici, contenente il vertice speciale. Ad esempio per il tetraedro, un grafo è un K_ {3} sul set di vertici identificato sopra, con un vertice quello speciale e con i pesi dei bordi.
• Una sezione è un grafico con un'applicazione coerente delle etichette ai centri alla fine di ciascun bordo (cioè costantemente etichettata per rispettare il numero di vertici comuni indicati dal peso del bordo e che ciascun sottoinsieme di un insieme di vertici grafico contiene vertice 1). Un dato grafico può quindi rappresentare più sezioni (tramite diverse etichette). (Non ci sono molte opzioni come sembra come se ci fossero avrà senso in un secondo.)
• Una sezione non è interessante se la matrice dalle coordinate dei centri ha zero determinante.

Nel caso di tre dimensioni, con quattro vertici, si ottengono i seguenti set (usiamo la coppia proiettiva breve, perché non c'è sufficiente visibilità in questo esempio di non richiedere il vertice regola di etichettatura rifiuto più semplice):
0 : coppia proiettiva di {1,2,3,4}
1: {1}
1 ': {2}, {3}, {4}
2: {1,2}, {1,3 }, {1,4} 2 ': coppie proiettive a 2 (così omesse)
3: coppie proiettive a 1' (così omesse)
3 ': proiettivo pai rs a 1 (quindi omessi)

vincoli Label:
{0-> x, x}
{0-> x', x}
{1-> 1,1} - non consentiti: centri non sono compresi due volte
{1-> 1' , 0} {
1-> 2,1}
{2-> 2,1}
Nessun altro pesi sono possibili con questi vertici grafico.

un grafo è un K_ {3} incidente 0, grafici seguenti sopravvivono le regole di selezione grafico:
A: {0-> 1,1}, {0-> 1' , 1}, {1 -> 1 ', 0} B: {0-> 2,2}, {0-> 2,2}, {2-> 2,1}

A ha una sola etichetta , {2}, {} ed è il set interessante triangolare.Questa etichettatura non ha determinante zero.
B ha una sola etichetta: {1,2}, {1,3}, {} ed è il tuo set interessante quadrato. Questa etichettatura non ha determinante zero.

La conversione in codice viene lasciata al lettore come esercizio (perché devo partire per lavoro).