Politopos.

Este post es una compilación de enlaces sobre politopos. Añado, cómo hilo conductor, algunos comentarios propios.  

1. Politopos abstractos: http://en.wikipedia.org/wiki/Abstract_polytope). De un artículo de wikipedia: «The abstract polytopes arose out of an attempt to study polytopes apart from the geometrical space they are embedded in. They include the tessellations of spherical, euclidean and hyperbolic space, tessellations of other manifolds, and many other objects that do not have a well-defined topology, but instead may be characterised by their «local» topology. There are infinitely many in every dimension. See this atlas for a sample».

2. Politopos Complejos:http://en.wikipedia.org/wiki/Complex_polytope. De este artículo: «A complex polytope is a generalization of a polytope in real space to an analogous structure in a complex Hilbert space, where each real dimension is accompanied by an imaginary one».

3. Politopos (reales): http://en.wikipedia.org/wiki/Polytope. Cómo siempre los problemas en el caso más general inabordables. ¿ Solución ? Restringir !! Que otra cosa se puede hacer…Nos podemos restringir a los casos convexos o se pueden fijar la dimensión y para d=3 estudiamos los polihedros o se puede restringir otros parametros (por ejemplo el tipo de vectores que pueden ser vertices del politopo y estudiamos  por ejemplo los permutahedros etc…

4. Politipos uniformes y regulares:

–uniformes: http://en.wikipedia.org/wiki/Uniform_polytope. De este artículo: «A uniform polytope is a vertex-transitive polytope made from uniform polytope facets. A uniform polytope must also have only regular polygon faces».

–regulares: http://en.wikipedia.org/wiki/Regular_polytope. De este artículo: «A regular polytope is a polytope whose symmetry is transitive on its flags, thus giving it the highest degree of symmetry»; son por lo tanto un subconjunto de los uniformes; para su realización en un espacio euclideo, elíptico (n-esfera) o hiperbolico ver http://en.wikipedia.org/wiki/List_of_regular_polytopes#Tessellations. Luego veremos los muy estudiados politopos regulares convexos 3 y 4 dimensionales y las tres familias con realización en cualquier dimensión. 

5. Politopos (reales) convexos: http://en.wikipedia.org/wiki/Convex_polytope, programación lineal: http://en.wikipedia.org/wiki/Linear_programming y su complejidad: http://rjlipton.wordpress.com/2010/06/26/stating-pnp-without-turing-machines/ y el importante (al menos para el tema que nos ocupa) Teorema de Balinski, de Wikipedia: «It states that, if one forms an undirected graph from the vertices and edges of a convex d-dimensional polyhedron or polytope (its skeleton), then the resulting graph is at least d-vertex-connected: the removal of any d − 1 vertices leaves a connected subgraph»,    http://en.wikipedia.org/wiki/Balinski%27s_theorem y el paper: http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pjm/1103037323. Notese que la motivación inicial era la hamiltionicidad…

6. Permutahedro: http://en.wikipedia.org/wiki/Permutohedron  y su estructura subyacente si nos olvidamos de la geometria( su 1-esqueleto): un grafo de cayley generado por n-1 transposiciones de elementos adyacentes (n, la dimensión del espacio en el que está inmerso el politopo).  Relacionado con esto el:

7. Politopo de Birkhoff (caso especial nxn del Transportation polytope mxn): http://en.wikipedia.org/wiki/Birkhoff_polytope, algunos de los problemas que se estudian sobre este objeto:   http://www.ojac.org/vol4/CanfieldMcKayBirkhoff.pdf . Más en: http://www.math.ucdavis.edu/~ekim/talks/gscc_graphsoftransportationpolytopes.pdf. Interesante el teorema de Loera, Onn (2004) que desconocia. Atención!: La conjetura de Hirsch ha sido recientemente resuelta negativamente: http://gaussianos.com/francisco-santos-encuentra-un-contraejemplo-que-refuta-la-conjetura-de-hirsch/. Desconocía también completamente la conjetura de Barnette: http://en.wikipedia.org/wiki/Barnette’s_conjecture.  Un teorema interesante relacionado con estos politopos, el de Birkhoff-Von Newman (toda matriz doblemente estocástica es una combinación convexa de matrices de permutaciones; la proposición conversa es cierta también: http://mingus.la.asu.edu/~hurlbert/papers/SPBVNT.pdf) y algunas de sus generalizaciones: https://ritdml.rit.edu/bitstream/handle/1850/5967/NReffThesis05-18-2007.pdf?sequence=1  o bien  http://mathoverflow.net/questions/6890/generalizations-of-the-birkhoff-von-neumann-theorem, y una serie de teoremas equivalentes: http://robertborgersen.info/Presentations/GS-05R-1.pdf. !! Muy interesante !!…pero off-topic para este blog. 

8. Policoros (polychores) o politopos 4-dimensionales: http://en.wikipedia.org/wiki/Polychoron

9. Policoros convexos: de Wikipedia, «A polychoron is convex if its boundary (including its cells, faces and edges) does not intersect itself and the line segment joining any two points of the polychoron is contained in the polychoron or its interior; otherwise, it is non-convex. Self-intersecting polychora are also known as star polychora, from analogy with the star-like shapes of the non-convex Kepler-Poinsot polyhedra».

10. Policoros convexos regulares (análogos 4-dimensionales de los cinco solidos platonicos): http://en.wikipedia.org/wiki/Convex_regular_4-polytope. En 4 dimensiones solo hay 6.

Para dimensiones mayores, d >=5,  solo hay tres posibles d-politopos convexos regulares.

— el hipertetrahedro o n-simplex, generalización del triangulo http://es.wikipedia.org/wiki/Simplex. Su construcción es sencilla «Un n-símplex regular puede construirse a partir de un (n-1)-símplex regular conectando un nuevo vértice a todos los vértices originales por la longitud común del lado», y de esta se puede ver facilmente que su 1-esqueleto, el grafo completo Kn+1, que es isomorfo a un grafo de Cayley.

–el hipercubo o n-cube (http://en.wikipedia.org/wiki/Hypercube), generalizacion del cubo, y su 1-esqueleto los grafos del hipercubo (http://en.wikipedia.org/wiki/Hypercube_graph, isomorfos a un determinado tipo de grafos de Cayley.

–el n-ortoplex o polítopo de cruce o hiperoctaedro (http://en.wikipedia.org/wiki/Cross-polytope), y su 1-esqueleto el grafo de Turan http://en.wikipedia.org/wiki/Tur%C3%A1n_graph .  Tampoco lo dicen pero estos grafos son isomorfos a un tipo de circulantes (http://mathworld.wolfram.com/CrossPolytope.html). Sí, también estos son o se pueden realizar cómo grafos de Cayley.

Es interesante ver las diferentes realizaciones de sus coordenadas, cómo politopos. El grafo completo sería la red de interconexión óptima…si escalase bien. Lo mismo le pasa al grafo n-cubo.    

11. Polihedros o los politopos 3-dimensionales: http://en.wikipedia.org/wiki/Polyhedron y su estudio, Polyhedral combinatorics: http://en.wikipedia.org/wiki/Polyhedral_combinatorics. La parte sobre la conjetura de Hirsch no está actualizada (ver más abajo). Sobre la hamiltonicidad de polihedros: Brown: http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pjm/1103036906  (la nota «Hamiltonian paths on convex polyhedron» del mismo autor no parece accesible). Sobre el mismo tema Grunbaum y Motzkin:   http://jlms.oxfordjournals.org/cgi/pdf_extract/s1-37/1/152, y más en http://en.wikipedia.org/wiki/Polyhedral_graph. Desde un punto de vista más general:  «A survey and comparison of methods for finding all vertices of convex polyhedral sets» de Matheics and Rubin (1980).  Contraejemplos:  el primero, el  Tutte graph: http://en.wikipedia.org/wiki/Tutte_graph y  el más pequeño posible el grafo de Herschel: http://en.wikipedia.org/wiki/Herschel_graph. Ninguno de los es vertice transitivo.    

12. Polihedros convexos (y el importante teorema de Steinitz): copiado de wikipedia «every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron», http://en.wikipedia.org/wiki/Steinitz_theorem.

13. Polihedros convexos regulares (o Cinco solidos platonicos). http://en.wikipedia.org/wiki/Platonic_solid. Son los unicos cinco posibles. Por determinadas razones, mi favorito el Cubo.   

PREGUNTA: Me pregunto  a que tipo de politopos se corresponden los digrafos de Cayley 2-generados de Sn y An smooth y convertidos a grafos añadiendo los generadores que faltan, si es que se corresponden algún tipo de politopo. No tengo tiempo que dedicarle a este tema. Solo expongo algunos links que he encontrado sobre politopos y grafos:  

–un primer paper sobre poliedros y grafos: https://dlib.lib.washington.edu/dspace/bitstream/handle/1773/2276/Graphs+of+polyhedra.pdf?sequence=1 nos indica de nuevo que estamos recorriendo un camino ya transitado y nos confirma que el pasar de grafo a politopo no es trivial: el politopo tiene más estructura (geometrica) que el grafo. De este paper extraigo el siguiente comentario:

» Even such otherwise very critical thinkers as Thomas Kirkman seemed to believe that if you draw in the plane a figure that seems to represent a polyhedron, there actually is a convex polyhedron that looks much like this figure (see [40]). The first to publicly question this attitude was Ernst Steinitz, in Section 21 of his 1916 contribution [60] to the great «Encyklopedie der mathematischen Wissenschaften». In the following thirteen sections Steinitz shows how one can formulate the criteria that are necessary and sufficient for the existence of a convex geometric polyhedron that is combinatorially given, and establishes that all such convex realizations are determined up to isomorphism of convex polyhedra«. Es decir parece que la motivación de Steinitz para obtener su famoso teorema fue precisamente una pregunta similar.  

Otro comentario del mismo paper: «As for polygons, for polyhedra it is convenient to distinguish the combinatorial structure of a polyhedron from its geometric realization. Hence we shall start with combinatorial or abstract polyhedra and obtain geometric polyhedra as images of abstract ones in a Euclidean space».  Ya hemos visto que la representación no tiene que ser necesariamente en el espacio euclideo.

Actualización 28/07/2010

Del mismo autor (con un co-autor) he encontrado este muy claro e interesante survey sobre «convex polytopes». Hay que decir que uno de los autores es un experto de primer orden en este tema (Grünbaum). Este es el tipo de paper que estaba buscando sobre politopos. Comenta: el paper consta de dos partes, primera parte titulada «The combinatorial theory of polytopes» que trata de éstos de una manera abstracta (politopos cómo reticulos), y una segunda parte, «Metrical theory of politopes», que trata de su realización geometrica en un espacio. En la primera parte comenta:

«The central problem of the combinatorial theory may be stated as follows: find necessary and sufficient conditions for a given lattice L to be isomorphic to the face lattice F(P) of some polytope P. In this generality this problem seems completely intractable except for the fact that the lattices of 3-polytopes may be characterized by Steinitz theorem. As this result is more naturally stated in terms of graphs, we defer details…». Sorprendente. Pensaba que mi pregunta sería evidente para un especialista (y a lo mejor lo sigue siendo), y resulta que en su forma más general forma parte del problema central del tema (por cierto ¿cual será el vínculo de los retículos con los grafos en mayores dimensiones ?)…En fin, este tema de politopos, que empiezo a ver con un poquito más de claridad, me está enganchando definitivamente. Gracias Grünbaum !   Para descargarse el paper es el PDF titulado Convex polytopes que aparece en quinto lugar en

http://www.google.es/#hl=es&source=hp&q=convex+polytopes&aq=f&aqi=&aql=&oq=&gs_rfai=&fp=6430d67890100ed

Fin actualización-

–un link sobre algunos grafos parametricos etiquetados y su realización cómo politopos: http://gilkalai.wordpress.com/2009/02/28/ziegler%c2%b4s-lecture-on-the-associahedron/ . Parece que pasar de un grafo parametrico http://en.wikipedia.org/wiki/Category:Parametric_families_of_graphs)de a un politopo no es cosa trivial. Tampoco está claro que este post hable exactamente de mi pregunta. Para mi las familias parametricas de grafos son de gran interés y a lo mejor haré un post.  

–otro links relacionados: http://infoscience.epfl.ch/record/121636/files/trancio.pdf., http://www.iasi.cnr.it/~gentile/ClaudioGentileFiles/papers/ORL2.pdf, y otro sobre el mismo problema http://www.labri.fr/publications/combalgo/2006/PW06e/ClawFree_ISMP.pdf.

 P.d´s.

1. Sigo estudiando la teoria average-case. Tras recopilación, lectura. Todo más o menos claro pero todavia con dudas importantes por aclarar. Cuando las aclare haré un post con las conclusiones (es decir si merece la pena o no seguir con este tema de SP o no).

2. Buscando documentación para este post por accidente he encontrado u paper que no puedo evitar citar: http://www.ece.ucsb.edu/Faculty/Parhami/pubs_folder/parh06-ipl-cayley-small-world.pdf.  Me ha llamado la atención pues en la teoria average-case  un punto clave es la generación aleatoria de casos. Conocía algunos procesos o modelos aleatorios de generación de redes-mundo pequeño (small world networks) pero no modelos o procesos deterministas, y menos que los Grafos de Cayley sirviesen como modelos para redes mundo pequeño…