listado todas las secciones interesantes de un tetraedro

Question

actualización respuesta, 12/22: El uso de observation que hay un homomorfismo entre las secciones y permutaciones de objetos en el cubo distintas, una lista de todas esas permutaciones mediante la representación de un grupo de simetrías del cubo Peter Shor como un subgrupo de SymmetricGroup [8] y el uso de GroupElements/Permute, encontrar las asignaciones de los centroides utilizando solucionador SAT de Mathematica, seleccione los conjuntos de puntos con valores singulares distintos, algunos detalles más y código completo dado here

pregunta

Una sección 2D interesante es un plano que pasa por el centro de un 3D simplex regular y otros 2 puntos, cada uno de los cuales es un centroide de un subconjunto no vacío de vértices. Está definido por dos subconjuntos de vértices. Por ejemplo, {{1}, {1,2}} da un plano definido por 3 puntos: centro del tetraedro, primer vértice y promedio del primer y segundo vértices.

Un conjunto interesante de secciones es un conjunto en el que no hay dos secciones que definan el mismo plano debajo del reetiquetado de los vértices. Por ejemplo, establecer {{{1}, {2}}, {{3}, {4}}} no es interesante. ¿Existe un enfoque eficiente para encontrar un interesante conjunto de secciones interesantes? Necesito algo que pueda generalizarse a un problema análogo para secciones 3D de 7D simplex y terminar de la noche a la mañana.

Mi intento de aproximación está a continuación. Un problema es que si se ignora la geometría, se conservarán algunas secciones equivalentes, así que obtendré 10 secciones en lugar de 3. Un problema mayor es que utilicé la fuerza bruta y definitivamente no escala y (necesita 10^17 comparaciones para 7D simplex)

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

Aquí está el código Mathematica para generar imagen de arriba.

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 solución correcta programación es, a grandes rasgos:

• observar que los centros vienen en pares proyectivas - así identificar y mantener únicamente la mitad de los centros que se encuentran en una o las otras cubiertas semiesféricas del conjunto de centros. Los pares se establecen complementando entre sí. Una regla de ejemplo: todos los subconjuntos que contienen el vértice 1 y los del "ecuador", los que contienen el vértice 2 y el "ecuador" de ese conjunto, los que contienen el vértice 3, y así sucesivamente manteniendo la mitad del límite adyacente al índice más pequeño vértice.
• Observe que para cada subsimplex, el subsimplex es adyacente al vértice 1 o está a una distancia 1 de simplex. (Causa: cada vértice nuevo en el tetraedro está unido a cada vértice anterior del tetraedro; por lo tanto, cada subimplejo es incidente en el vértice 1 o el vértice 1 está conectado a cada vértice en el símplex.) En consecuencia, solo hay dos poblaciones de cada uno. tipo de subsimplex (con respecto a un vértice especificado). (Podemos reemplazar esta observación con la decisión de mantener solo el miembro más pequeño de cada par proyectivo, pero luego la regla para etiquetar vértices es más complicada).

• Los tetraedros son completamente simétricos bajo la permutación de las etiquetas de vértices. En consecuencia, cualquier "sección interesante" es equivalente a otra sección que contiene solo el segmento principal de vértices, es decir, se puede identificar entre los vértices Rango [1, n] para algunos n.

• Recopilando lo anterior, encontramos que hay una superación de la sección de interés en un conjunto de gráficos. Para cada gráfico, debemos enumerar membresías de vértices consistentes (que se describen más adelante).A excepción de un vértice, los vértices de la gráfica vienen en pares

  • El par contiene todos los centros de una cardinalidad dado (todos subsimplices de una dimensión dada).
  • Un miembro del par contiene centros incidente en el vértice 1.
  • El otro miembro del par contiene centros no incidente sobre vértice 1.
  • El vértice especial es o bien el centro que contiene todos los vértices o su par proyectiva (el "centro vacío").
  • Si un gráfico contiene cualquier miembro de un par, debe (al menos) contener el miembro que contiene los centros que inciden en 1 (o los vértices se pueden volver a etiquetar para que así sea).
• Los bordes del gráfico son ponderados. El peso es la cantidad de vértices compartidos por los dos centros. Existen restricciones en el peso en función de la cardinalidad de los centros en cada extremo y en función de si los dos vértices son ambos primeros miembros, ambos segundos miembros, o son uno de cada uno. ("Uno de cada" no puede compartir el vértice 1, por ejemplo).
• Un gráfico es un subgrafo completo en el conjunto de vértices, que contiene el vértice especial. Por ejemplo, para el tetraedro, un gráfico es un K_ {3} en el conjunto de vértices identificados anteriormente, con un vértice especial y con los pesos de los bordes.
• Una sección es un gráfico con una aplicación consistente de etiquetas en los centros al final de cada borde (es decir, etiquetado consistentemente para respetar el número de vértices compartidos indicado por el peso del borde y que cada subconjunto en un conjunto de vértices del gráfico contiene vértice 1). Un gráfico dado, por lo tanto, puede representar secciones múltiples (a través de diferentes etiquetas). (Que no hay tantas opciones como suena como si hubiera sentido tendrá sentido en un segundo.)
• Una sección no es interesante si la matriz hecha a partir de las coordenadas de sus centros tiene cero determinante.

En el caso de tres dimensiones, con cuatro vértices, se obtienen los siguientes conjuntos (usamos el corto par proyectiva porque no hay suficiente visibilidad en este ejemplo para no requerir el vértice más simple regla de rechazo etiquetado):
0 : par proyectivo de {1,2,3,4}
1: {1}
1 ': {2}, {3}, {4}
2: {1,2}, {1,3 }, {1,4}
2 ': pares proyectivos a 2 (omitido)
3: pares proyectivos a 1' (omitido)
3 ': proyectivo pai rs a 1 (por lo que se omite)

restricciones de etiqueta:
{0-> x, x}
{0-> x', x}
{1-> 1,1} - no permitidos: centros no se incluyen dos veces
{1-> 1' , 0}
{1-> 2,1}
{2-> 2,1}
no hay otros pesos son posibles con estos vértices del gráfico.

Una gráfica es una K_ {3} incidente en 0, los siguientes gráficos sobreviven las reglas de selección gráfica:
A: {0-> 1,1}, {0-> 1' , 1}, {1 -> 1 ', 0}
B: {0-> 2,2}, {0-> 2,2}, {2-> 2,1}

A solo tiene una etiqueta: {1} , {2}, {} y es su conjunto triangular interesante.Este etiquetado no tiene un determinante cero.
B tiene solo una etiqueta: {1,2}, {1,3}, {} y es su conjunto cuadrado interesante. Este etiquetado no tiene un determinante cero.

La conversión al código se deja como un ejercicio para el lector (porque tengo que irme al trabajo).