Usted está aquí: Inicio / Actividades / Seminarios / Seminario Preguntón de Matemáticas Discretas / Actividades / Dibujar gráficas con vértices y aristas en posición convexa

Dibujar gráficas con vértices y aristas en posición convexa

Ponente: Kolja Knauer
Institución: LIRMM, Francia
Tipo de Evento: Investigación
Cuándo 11/08/2015
de 17:00 a 18:00
Dónde Unidad Multidisciplinaria de Docencia e Investigación (UMDI), Aula 1. UNAM Campus Juriquilla, Querétaro
Agregar evento al calendario vCal
iCal

Una gráfica tiene dimensión fuertemente convexa 2, si se puede dibujar con aristas rectas en el plano tal que los vértices están en posición convexa y los baricentros de las aristas están en posición convexa. Halman, Onn y Rothblum conjeturaron que tales graficas son planares y por lo tanto tienen a lo mucho 3n-6 aristas, donde n es el número de vértices.
Mostramos que de hecho toda gráfica de dimensión fuertemente convexa 2 tiene a lo mucho 2n-3 aristas. Por otro lado presentamos una clase de gráficas no-planares de dimension fuertemente convexa 2. Tambien damos cotas inferiores para el número de aristas y discutimos variantes de estos conceptos. 
Esto ha relacionado varios problemas interesantes sobre grandes conjuntos de puntos en posición convexa en sumas de Minkowski.

Este es un trabajo en conjunto con Ignacio García-Marco.