Logo
DATOS DEL INVESTIGADOR PRINCIPAL
Nombre Sandor Ortegon
Nombre del perfíl Investigador Por Proyecto
Grupo de investigación Ciencias Básicas
Línea de investigación Algebra, Lógica y Combinatoria
Equipo del proyecto
TÍTULO DEL PROYECTO GEOMETRIA DISCRETA Y POLINOMIOS
PALABRAS CLAVE Discrete Geometry, Graph Theory, Polyhedral Combinatorics, Convex Polytopes
OBJETIVOS DEL PROYECTO El objetivo de este proyecto es realizar investigación teórica sobre aspectos en Geometría Discreta relacionados con simplices y politopos enteros. Este trabajo puede considerarse como una extensión del trabajo realizado en el proyecto de investigación del año 2009, donde se buscaba aplicar teoría de combinatoria algebraica sobre politopos al análisis del número de equilibrios en juegos estratégicos finitos. En esta ocasión, se quiere trabajar en un nuevo tema (ver la sección de pertinencia epistemológica), explorando el mismo contexto de símplices y politopos enteros estudiado en el pasado.
PERTINENCIA ESPISTEMOLÓGICA DEL PROYECTO Uno de los problemas propuestos del proyecto fueron planteados por Richard Stanley; profesor de MIT y quizás la principal autoridad mundial en Combinatoria Algebraica. Preparando una edición nueva de su clásico libro "Enumerative Combinatorics (vol. 1)", ha escrito a varios de sus estudiantes sobre preguntas abiertas que considera relevantes y de las cuáles quiere saber su evolución para referirlas en su libro. El problema que se ha recibido de su parte es el siguiente:

"In connection with a new exercise for EC1, do you know if anyone has found a combinatorial interpretation of the h*-vector of a hypersimplex? It would be a refinement of the Eulerian number A_{n,k}."

Es importante observar al respecto, que dar interpretaciones combinatoricas a ciertos números representa en Matemáticas un gran avance para comprender una estructura o generar un algoritmo más eficiente de cálculo. En este sentido, podría considerarse que trabajar en una pregunta abierta surgida de una autoridad en la materia podría generar conocimiento valioso dentro de la amplia comunidad que trabaja en Combinatoria Algebraica. Además, el problema al cual hace referencia es relacionado directamente con estimación de volúmenes y estimación de puntos de coordenadas enteras en poliedros; este último es un tema de gran aplicacion en Ciencias de la Computación en el área específica de Geometría Computacional (también llamada Geometría Discreta).
RELEVANCIA DEL PROYECTO PARA LA INSTITUCIÓN Y PARA LOS BENEFICIARIOS DEL PROYECTO Este proyecto tendrá un impacto en asignaturas relacionadas con Análisis de Algoritmos, Teoría de Grafos y electivas como Geometría Computacional y Métodos Discretos en Teoría de la Computación, donde este tema es pertinente. Temas relacionados con politopos enteros pueden hacer parte de proyectos de Aula en estas materias, dada la conexión con algoritmos geométricos.

De otro lado, este tema puede servir para la tesis de grado de un estudiante de Ingeniería de Sistemas, con interés hacia las matemáticas. Además de la investigación pura en los problemas propuestos, hay un asunto de relevancia y es la parte experimental. Dado que se desea encontrar un patrón en una sucesión de números, se necesita hacer experimentos para descubrir el mismo; dichos ensayos consisten de algoritmos no triviales que generen números grandes como auxiliares para establecer conjeturas que lleven a la interpretación deseada.


Por último, este es un proyecto de interés conjunto, que involucra la presencia del profesor Richard Stanley (Massachusetts Institute of Technology), quien ha planteado las preguntas (para incluir los avances en su libro) y el profesor Federico Ardila (San Francisco State University), quien ha contactado al investigador del proyecto (Sandor Ortegón) para iniciar un trabajo conjunto. De este modo, investigación relevante en este tema puede vincularse con futuras colaboraciones entre estas universidades. En particular, el profesor Ardila ha manifestado su interés, debido a un reconocimiento que ha recibido de la NSF en Estados Unidos y que involucra planes de colaboración en Combinatoria con universidades del país; este trabajo puede ser un primer acercamiento en esa dirección.
PROBLEMA DE INVESTIGACIÓN El polinomio de Ehrhart de un politopo P de coordenadas enteras esta definido para m entero positivo como E(m) = numero de puntos reticulares en mP; donde mP representa la homotecia de P por un factor de m. Se puede demostrar que E(m) es en efecto un polinomio para cualquier politopo entero P, y además, cumple la siguiente fórmula: $\sum E(m)x^m = h*(x)/(1-x)^n$, donde h*(x) es una función entera. Richard Stanley demostró que h*(x) es un polinomio en $x$ con coeficientes enteros.

La pregunta que plantea Stanley es si es posible dar una interpretación combinatoria a los coeficientes de h*(x) cuando P es el hipersimplex Delta(n,k). Dicho hipersimplex se define como la envolvente convexa de los (n con k) vectores de k 1s y n-k 0s, definido por las ecuaciones y desigualdades x_1+...+x_n=k con x_i >0 para cada i. Stanley demostro que el volumen de Delta(n,k) es el "numero Euleriano" A(n,k) = número de permutaciones de n con k descensos, dividido por n!. Dado que el volumen tiene relación con E(1), se considera que una posible interpretación para los coeficientes será un refinamiento de dichos números Eulerianos y esto es lo que se quiere investigar.
METODOLOGÍA - En primer lugar, con el profesor Stanley y el profesor Ardila se trabajará en estar familiarizado con la bibliografía existente en el tema. Siendo el profesor Stanley la principal autoridad en el asunto, bastará una comunicación directa con él para empezar a trabajar.

- En segundo lugar, contando con la colaboración de un estudiante para la parte algoritmica y de implementación (en el peor de los casos, el investigador principal se encargará de ello), se realizará una tabulación de cálculos relacionados con el problema para intentar encontrar patrones relacionados con los coeficientes pedidos.

- En tercer lugar, se establecerán conjeturas sobre la interpretación de los valores analizados en la parte previa y se consultará su viabilidad con expertos en el tema.

- Se procederá luego a hacer demostraciones algebraiccas de las conjeturas que resulten viables.

- Por último, se trabajará en las pruebas combinatorias (biyectivas) de dichas conjeturas, que son aquellas de mayor interés para la comunidad que trabaja en Combinatoria Algebraica.
RESULTADOS ESPERADOS Se espera publicar un artículo de investigacion (ITC) escrito en un Journal Internacional (bien sea individual, o conjunto, según la colaboración con los profesores) con resultados que brinden un mayor conocimiento de los coeficientes del polinomio de Ehrhart en el politopo sugerido por el profesor Stanley. Dado que se trabaja sobre una pregunta abierta, de la calidad de los resultados dependerá el tipo de journal al cual se envía el artículo, pero cumpliendo el requisito del envío de artículo a un journal internacional.

Dependiendo la calidad de los resultados obtenidos, estos podrían aparecer también referidos en la última edición del libro Enumerative Combinatorics (Volume 1) que está en proceso.

En adición, se entregará un artículo de revisión y divulgación (IPP) sobre el tema a ser publicado en una revista latinoamericana (en idioma español).
DURACIÓN DEL PROYECTO
POSIBLES FUENTES DE FINANCIACIÓN EXTERNA
REVISIÓN BIBLIOGRÁFICA Las siguientes son referencias bibliográficas clásicas para el tema. Podemos clasificar dicha bibliografía en tres tipos: Libros de Texto, como los clásicos de R. Stanley, L. Comtet y G. Ziegler; Artículos Clásicos y Monografías, como el artículo original de Ehrhart, el artículo de Takayuki y la monografía de Marden sobre geometría de polinomios, así como los restantes artículos modernos que profundizan las conexiones entre estos polinomios y otros conceptos de Combinatoria Algebraica, como los anillos de Cohen-Macauley, Polinomios Eulerianos y h-vectores. El artículo de Beck, Stanley, et.al. (Coefficients and roots of Ehrhart polynomials), representa una referencia concreta al tema de dar interpretaciones nuevas a coeficientes de polinomios de Ehrhart; cualquier avance de este proyecto se obtendrá en esa dirección de dar nuevas interpretaciones y pruebas biyectivas.

A continuación está una lista preliminar, siendo digitada usando los comandos de LaTeX.


\begin{thebibliography}{10}

\bibitem{AthVectors}
Christos A. Athanasiadis, \emph{{$h\sp \ast$}-vectors, {E}ulerian polynomials
and stable polytopes of graphs}, Electron. J. Combin. \textbf{11} (2004/06),
no. 2, Research Paper 6, 13 pp. (electronic).


\bibitem{BDDPSCoefficients}
M. Beck, J. A. De Loera, M. Develin, J. Pfeifle, and R. P. Stanley,
\emph{Coefficients and roots of {E}hrhart polynomials}, Integer points in
polyhedra---geometry, number theory, algebra, optimization, Contemp. Math.,
vol. 374, Amer. Math. Soc., Providence, RI, 2005, pp.~15--36.

\bibitem{BRComputing}
Matthias Beck and Sinai Robins, \emph{Computing the continuous discretely},
Undergraduate Texts in Mathematics, Springer, New York, 2007.

\bibitem{BMLattice}
U. Betke and P. McMullen, \emph{Lattice points in lattice polytopes}, Monatsh.
Math. \textbf{99} (1985), no. 4, 253--265.

\bibitem{ComAdvanced}
Louis Comtet, \emph{Advanced combinatorics}, enlarged ed., D. Reidel Publishing
Co., Dordrecht, 1974.

\bibitem{ehrhartpolynomial}
Eug{\`e}ne Ehrhart, \emph{Sur les poly\`edres rationnels homoth\'etiques \`a
{$n$}\ dimensions}, C. R. Acad. Sci. Paris \textbf{254} (1962), 616--618.

\bibitem{HibSome}
Takayuki Hibi, \emph{Some results on {E}hrhart polynomials of convex
polytopes}, Discrete Math. \textbf{83} (1990), no.~1, 119--121.

\bibitem{KSPrimitive}
J. M. Kantor and K. S. Sarkaria, \emph{On primitive subdivisions of an
elementary tetrahedron}, Pacific J. Math. \textbf{211} (2003), no.~1,
123--155.


\bibitem{lagariasziegler}
Jeffrey C. Lagarias and G{\"u}nter M. Ziegler, \emph{Bounds for lattice
polytopes containing a fixed number of interior points in a sublattice},
Canad. J. Math. \textbf{43} (1991), no.~5, 1022--1035.


\bibitem{leetriangulations}
Carl~W. Lee, \emph{Subdivisions and triangulations of polytopes}, Handbook of
discrete and computational geometry, CRC Press Ser. Discrete Math. Appl.,
CRC, Boca Raton, FL, 1997, pp.~271--290.

\bibitem{MarGeometry}
Morris Marden, \emph{Geometry of polynomials}, Second edition. Mathematical
Surveys, No. 3, American Mathematical Society, Providence, R.I., 1966.

\bibitem{StanleyAlgebra}
Richard P. Stanley, \emph{Combinatorics and Commutative Algebra}, Birkhauser
Boston, 2nd edition, 2004

\bibitem{StanleyEnumerative}
Richard P. Stanley, \emph{Enumerative Combinatorics, Vol. 1}, Cambridge University Press,
2nd edition, 2000.

\bibitem{StaDecompositions}
Richard~P. Stanley, \emph{Decompositions of rational convex polytopes}, Ann.
Discrete Math. \textbf{6} (1980), 333--342.

\bibitem{YoInequalities}
Alan Stapledon, \emph{Inequalities and {E}hrhart $\delta$-vectors},
arXiv:0711.4382, to appear in Trans. Amer. Math. Soc.

\bibitem{ziegler}
Gunther M. Ziegler, \emph{Lectures on Polytopes}, Springer, 1994

\end{thebibliography}
ENTREGABLES
CRONOGRAMA
TIPO DESCRIPCIÓN F.INICIO F.FINAL
Actividad Revisión más detallada de estado del arte y contacto con matemáticos especialistas. 15/01/2011 15/02/2011
Actividad Introducción a los polinomios de Ehrhart y politopos enteros. Charla y diapositivas de la misma. 16/02/2011 20/03/2011
Actividad Elaboración de los cálculos algoritmicos a fin de buscar correlación entre los valores que se quieren y sucesiones conocidas relacionadas con permutaciones 01/03/2011 02/05/2011
Actividad Documento de análisis de los cálculos hechos, que incluye conjeturas sobre las posibles interpretaciones combinatorias. 02/05/2011 15/05/2011
Actividad Busqueda de demostraciones de las conjeturas planteadas 15/05/2011 01/07/2011
Actividad Documento con demostraciones de conjeturas sobre propiedades de Polinomios de Ehrhart para el hipersimplex de interés 15/05/2011 01/07/2011
Actividad Borrador Artículo Divulgativo 01/07/2011 02/08/2011
Actividad Borrador Artículo de Investigación 02/08/2011 02/09/2011
Entregable Artículo Divulgativo 02/09/2011 01/10/2011
Entregable Artículo de Investigación 01/10/2011 08/11/2011
PEDIDO DE BIBLIOGRAFÍA
AUTOR TÍTULO EDITORIAL
Richard Stanley Enumerative Combinatorics (Volume 1) Cambridge University Press
Richard Stanley Enumerative Combinatorics (Volume 2) Cambridge University Press
Miklos Bona Combinatorics of Permutations Chapman and Hall/CRC
Bernd Sturmfels y Erza Miller Combinatorial Commutative Algebra Springer
ANEXOS