Embed Size (px)
Citation preview
VIGéSIMO NOVENO COLOQUIOVíCTOR NEUMANN - LARADE TEORíA DE LAS GRáFICAS,COMBINATORIAY SUS APLICACIONES
resúmenes y programa
del 10 al 14 de marzo, 2014Boca del Río, Veracruz
XXIX Coloquio Vıctor Neumann-Lara de Teorıa de las
Graficas, Combinatoria y sus Aplicaciones
Boca del Rio, Veracruz
10 al 14 de marzo de 2014
Platicas por invitacion
Nombre: Juan Jose Montellano BallesterosInstitucion: IMUNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Arboles hetero-cromaticos graciososCo-autores: Eduardo Rivera, Ricardo StrauszResumen: En esta platica hablaremos sobre al-gunas condiciones para la aparicion de arbo-les heterocromaticos en coloraciones de grafi-cas. Ademas veremos que bajo ciertas condicio-nes, podemos interpretar a los arboles hetero-cromaticos como arboles graciosos (graceful) yapartir de ahı mostraremos que hay ”muchos”arboles graciosos.
Nombre: Hortensia Galeana SanchezInstitucion: Instituto de Matematicas, UNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Un panorama sobreH-nucleos en digraficasResumen: Se expondra un panorama de re-sultados sobre la existencia de H-nucleos enDigraficas coloreadas en sus flechas.
Nombre: Javier Bracho CarpizoInstitucion: Instituto de Matematicas, UNAM.Correo: [email protected]: InvestigacionTıtulo de la ponencia: Un politopo quiral dedimension chicaResumen:
Nombre: Gilberto Calvillo VivesInstitucion: Instituto de Matematicas Cuerna-vacaCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Cuandrangulacionesintercaladas de la esferaResumen: Una cuadrangulacion de la esfera esuna inmersion de una grafica en la esfera de talforma que cada cara (celda) en esta inmersionsea un 4-ciclo. Desde hace tiempo se conoceque tales cuadrangulaciones donde la grafica estres conexa pueden generarse a partir del cu-bo mediante una serie de transformaciones queproducen a cada paso otras cuadrangulaciones.El tema se ha generalizado para estudiar cua-drangulaciones con propiedades especıficas. Enesta platica abordamos el problema de cuadran-
gulaciones intercaladas. En estas, tenemos unacoloracion por aristas tal que cada cara (4-ciclo)tiene exactamente dos colores. Esta clase decuadrangulaciones es no vacıa pues a ella perte-necen los zonoedros rombicos, donde todas lasaristas paralelas reciben el mismo color. Plan-tearemos los avances para probar la siguienteconjetura: Toda cuadrangulacion intercalada es”suma” de cubos. Donde suma se entiende co-mo la diferencia simetrica dos cuadrangulacio-nes.
Nombre: Silvia FernandezInstitucion: California State University, North-ridgeCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Minimizando crucesen dibujos de la grafica completaCo-autores: Bernardo AbregoResumen: En esta platica describimos los re-sultados mas recientes sobre una de las conje-turas mas famosas de la teorıa topologica degraficas. En 1958 el artista y arquitecto britani-co Antony Hill se intereso en dibujar a la graficacompleta con pocos cruces y encontro construc-ciones que parecıan ser las mejores. Hill con-jeturo que cualquier dibujo de la grafica com-pleta con n vertices en el plano tiene al me-nos (n − 1)2(n − 3)2/64 cruces si n es impary n(n − 2)2(n − 4)/64 si n es par. Su con-jetura, conocida ahora como la Conjetura deHarary-Hill, ha seguido sin resolverse desde en-tonces pero se han logrado serios avances enlos ultimos anos. En particular, la conjetura seha podido confirmar para varias clases infinitasde graficas alrededor de las cuales centraremosnuestra atencion.
Nombre: Miguel PizanaInstitucion: UAM-ICorreo: [email protected]: InvestigacionTıtulo de la ponencia: Las graficas libres de4-, 5- y 6-ruedas son K-convergentesCo-autores: Paco Larrion, Rafael VillarroelResumen: En 2002, Vıctor, Paco y yo proba-mos que las graficas con cuello local al menos 7son K-convergentes. Este teorema se puede re-enunciar diciendo que las graficas que no tienen3-, 4-, 5- y 6- ruedas son K-convergentes.
Lo insatisfactorio de este teorema residıa enque existen grafica K-divergentes bien conoci-das que solamente tienen 4-ruedas (el octae-dro), solo 5-ruedas (el icosahedro) o solo 6-ruedas (triangulaciones regulares de Whitneydel toro), PERO no habıa ninguna grafica K-divergente conocida que tuviera solo 3-ruedas.Resulta ser que la prohibicion de las 3-ruedasera superflua y que el teorema sigue siendo cier-to si eliminamos esta hipotesis, aunque el nuevoteorema requiere de una prueba completamentedistinta.
Un clan de una grafica es una subgraficacompleta maximal. La grafica de clanes de G,K(G), es la grafica de interseccion de los clanesde G. Decimos que G es K-convergente si la su-cesion |G|, |K(G)|, |K2(G)|, . . . esta acotada,caso contrario decimos que G es K-divergente.
Nombre: Jorge UrrutiaInstitucion: Instituto de Matematicas, UNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Sobre permutaciones,subsucesiones crecientes, y familias de puntosetiquetadosResumen: Ponga aquı su Sea P ={p1, . . . , pn} una permutacion de {1, . . . , n}.Una subsucesion creciente de P , es un subcon-junto {pσ1
, . . . , pσk} de P tal que :
1. σ1 < σ2 < . . . < σk, y
2. pσ1< p + σ2 < . . . < pσk
.
Si pσ1> p + σ2 > . . . > pσk
, entoncesdecimos que {pσ1
, . . . , pσk} es una subsuce-
sion decreciente de P . Por ejemplo si P ={3, 5, 1, 4, 2, 6}, {1,4,2} es una subsucesion cre-ciente de P , y {5, 4, 2} es uns subsucesion de-creciente de P . Un resultado bien conocido deErdos y Szekeres nos dice que toda permutacionde {1, . . . , n} contiene una subsucesion crecien-te o decreciente con al menos
√n elementos.
En esta platica, veremos algunos generaliza-ciones del resultado de Erdos y Szekeres quesurgen de etiquetar los elementos de fami-lias de puntos Qn en el plano con los ente-ros {1, . . . , n}. Por ejemplo, encontrar caminossimples con vertices en Qn tal que sus etiquetassean crecientes. Otras variantes que estudiare-mos, incluyen encontrar subsucesiones crecien-tes de una permutacion en las cuales, la sumade los elementos de una subsucesion crecienteo decreciente se maximicen.
Nombre: Bernardo AbregoInstitucion: California State University, North-ridgeCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Sobre el maximonmero de patrones en conjuntos de realesResumen: En esta platica consideraremos elproblema de determinar el maximo numero decopias de un patron fijo que puede haber en unconjunto de n numeros reales. Un conjunto seconsidera una copia del patron si se puede ob-tener del mismo a partir de una transformaciongeometrica predeterminada. Las transformacio-nes mas estudiadas han sido congruencias, ho-motecias, semejanzas y traslaciones. Este pro-blema fue propuesto por Erdos y Purdy en la de-cada de los 1970s y en muchas de sus instanciassigue siendo un problema abierto. Presentare-mos varios resultados exactos para traslacionesy semejanzas cuando el patron es una progre-sion aritmetica y algunas cotas no triviales paraotros patrones.
Nombre: Richard WilsonInstitucion: UAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Topologıas compati-bles en graficas de comparabilidadResumen: Una topologıa en los vertices de unagrafica de comparabilidad G es compatible conG si cada subgrafica H de G es conexo en elsentido de graficas si y solo si es topoloogica-mente conexo. Se discutira condiciones en laestructura de una grafica que implican la exis-tencia de topologıas compatibles y topologıascompactas compatibles.
Nombre: Luis MontejanoInstitucion: Instituto de Matematicas, UNAM.Correo: [email protected]: InvestigacionTıtulo de la ponencia: ¿Quien es ese tal Sze-meredi?Resumen:
Lunes 10 de marzo
Nombre: Criel Merino LopezInstitucion: IMATE-UNAM sede OaxacaCorreo: [email protected]: InvestigacionTıtulo de la ponencia: El numero hetero-cromatico para matroidesCo-autores: Juan Jose MontellanoResumen: El numero heterocromatico h(H) deuna hipergrafica H no vacıa es el menor entero ktal que para toda k-coloracion de los vertices deH con exactamente k colores, hay una hiperaris-ta con todos sus vertices de color distinto. En elColoquio de Graficas de 2013 se menciono queel numero heterocromatico de la hipergrafica decortes de una grafica con n vertices y m aristases m-n+2. En esta platica se revisa el conceptode matroide para dar una una prueba sencillade una generalizacion de este resultado. Tam-bien se habla de otro resultado sobre numeroheterocromatico para una clase interesante dematroides.
Nombre: Juan Carlos Hernandez GomezInstitucion: Universidad Autonoma de Guerre-roCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Un modelo epide-miologico espacio-temporal discretoCo-autores: Dr. Juan Carlos HernandezGomez, Dr. Jose Marıa Sigarreta AlmiraResumen: Tradicionalmente los procesos epi-demiologicos han sido modelados medianteecuaciones diferenciales, ya sean ordinarias oparciales. Sin embargo, cuando se modela deesta manera se presentan muchas limitaciones
al querer incorporar aspectos importantes pro-pios al desarrollo de enfermedades, la heteroge-neidad de la poblacion o aspectos que tienenque ver con la distribucion espacial de los indi-viduos o la modificacion de su comportamientocomo respuesta al estado del sistema o comofuncion del tiempo, son algunos ejemplos. Espor eso que se han buscado nuevas formas demodelar haciendo uso de los avances tecnologi-cos que permitan modelar este tipo de procesos,incorporando cada vez mas caracterısticas im-portantes a dichos modelos. En este trabajo ha-cemos el estudio de un proceso epidemiologicoproponiendo un modelo espacio-temporal dis-creto con automatas celulares en el cual se es-tudia la existencia de un parametro equivalenteal R0, tan estudiado en modelos continuos, quenos permita conocer si la enfermedad se estable-cera dentro de la poblacion en forma epidemi-ca, endemica o si desaparecera por sı misma enalgun momento. Se daran los principios basicosque gobiernan los automatas celulares y se ha-blara de la necesidad del uso de redes complejasen este tipo de modelos.
Nombre: Ilan A. GoldfederInstitucion: Instituto de Matematicas, Univer-sidad Nacional Autonoma de MexicoCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Mas alla de las gene-ralizaciones de torneosResumen: En esta charla platicare sobre algu-nos problemas abiertos relacionados con las ge-neralizaciones de torneos.
Nombre: Isaac Arelio RıosInstitucion: Instituto de Matematicas UNAMCorreo: [email protected]: Reporte de TesisTıtulo de la ponencia: Cuerpos convexos conmuchas secciones elıpticasCo-autores: Luis MontejanoResumen: Hay cuerpos convexos, en el espa-cio euclidiano, con muchas secciones elıpticas.Nuestro objetivo es determinar cuantas y bajoque condiciones estas secciones permiten con-cluir que la frontera de un cuerpo convexo esun elipsoide. Presentaremos algunos de los re-sultados obtenidos.
Nombre: Natalia Garcıa-ColınInstitucion: Instituto de Matematicas, UNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Buscando la perfec-cion en hipergraficasCo-autores: Amanda Montejano, Deborah Oli-verosResumen: A partir de una definicion de orien-tacion y transitividad en 3-hipergraficas, es na-tural estudiar la clase de 3-hipergraficas que ge-neralizan el concepto de compatibilidad, puesen el contexto de graficas simples, las grafi-cas de comparabilidad son perfectas (es decir,su numero cromatico es igual a su numero declan).
En esta platica mostraremos, a traves de tresdistintas familias de 3-hipergraficas que son decompatibilidad, que estas no tienen la propie-dad de que la proporcion entre su numero declan y su numero cromatico es constante. Deforma que las 3-hipergraficas de comparabilidadno podran ser perfectas.
Nombre: Jesus Alva SamosInstitucion: Instituto de MatematicasCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Digraficas conexas porarcoırisCo-autores: Dr. Juan Jose Montellano Balles-terosResumen: Sean D una digrafica y ρ : A(D) →Γ una coloracion por flechas de D, donde Γ ⊆N , una trayectoria (dirigida) entre dos verticeses un arcoıris si no hay dos flechas en la trayec-toria con el mismo color. Si entre cualesquierados vertices de la digrafica hay un arcoıris, dire-mos que ρ es una coloracion por arcoıris y queD es arcoıris conexa.
Dados dos vertices u y v, cualquier trayec-toria entre u y v de longitud mınima es lla-mada geodesicas. Una coloracion por arcoırisen la cual para cada par de vertices exista unageodesica que sea tambien un arcoıris sera de-nominada coloracion fuerte por arcoıris.
Se define al numero de arcoıris de D, deno-tado rc(D), como el mınimo numero de coloresnecesarios para que D sea arcoıris conexa; unacoloracion por arcoıris que use rc(D) colores esllamada coloracion por arcoıris mınima. Analo-gamente el numero fuerte de arcoıris de D, de-notado src(D), es el mınimo entero k tal quehay una k-coloracion fuerte por arcoıris sobreD.
La conexidad por arcoıris en graficas fue pre-sentada inicialmente en 2008 por Chartran yotros autores en el artıculo Rainbow connec-tion in graphs. En nuestro caso, estudiaremoslos numeros de digraficas en distintas familiasde digraficas, ası como su relacion con ciertosinvariantes de la digrafica en cuestion.
Nombre: Ma. Guadalupe Rodrıguez SanchezInstitucion: UAM-ACorreo: [email protected]: InvestigacionTıtulo de la ponencia: Problema de Akiyamay Harary sobre el polinomio cromatico de unagrafica y su complementoCo-autores: Adan Mateos HernandezResumen: Problema: ¿Existe una grafica G,que no es autocomplementaria, tal que G y Gc
tienen el mismo polinomio cromatico? Este pro-blema fue propuesto por Akiyama y Harary en1980.
Sean G = (V (G), E(G)) una grafica sim-ple y n = V (G). Se puede probar que noexisten graficas autocomplementarias que ten-gan el mismo polinomio cromatico si n < 8 on ∼= 2, 3(mod4). En este trabajo se presenta lalista de graficas que resuelven el problema paran = 8.
Nombre: Guadalupe Gaytan GomezInstitucion: Universidad Autonoma Metropo-litana, Iztapalapa.Correo: [email protected]: InvestigacionTıtulo de la ponencia: Digraficas circulantescon nucleoCo-autores: Bernardo LlanoResumen: Sea D una digrafica, un nucleoN en D es un conjunto de vertices de Dtal que entre dos de ellos no hay flechas ypara todo v en V (D) − N existe una flechahacia algun vertice de N . Llamamos a ladigrafica C = Cn(j1, j2, . . . , jk) circulantesi V (C) = {0, 1, . . . , n − 1}, y F (C) =uv|v − u ∼= js(modn) para s = 1, 2, . . . , k.Duchet conjeturo que toda digrafica D, sin
ciclos impares y sin nucleo, contiene unaflecha e tal que la digrafica D − e tampocotiene nucleo. Gurvich, et al. encontraron uncontraejemplo a esta conjetura. Ellos probaronque la digrafica circulante C43(1, 7, 8) no tienenucleo, pero despues de eliminarle cualquierflecha, la digrafica resultante tiene nucleo.Cabe observar que C43(1, 7, 8) es el unicocontraejemplo conocido a la conjetura deDuchet; Gurvich conjetura que existe unafamilia infinita de digraficas circulantes conesta propiedad. Nuestro objetivo es encontrarfamilias de digraficas circulantes que satisfagantener nucleo (este problema fue planteado porBang-Jensen y Gutin). Entre los resultadosque hemos obtenido se encuentra el siguiente:Cn(1, 2, . . . , k), n ≥ 2k + 1 tiene nucleo si ysolo si n ∼= 0mod(k + 1).
Nombre: Ricardo Gomez AızaInstitucion: Instituto de Matematicas de laUNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Caminatas aleatoriasde entropıa maxima en digraficasResumen: Dada una digrafica existen muchasformas de recorrela aleatoriamente. Considera-mos aquellas que inducen una medida de Mar-kov en el espacio shift subyacente: si A es lamatriz de adyacencia de la digrafica, entoncesdicha medida estara dada por una matriz es-tocastica P con el mismo patron que A. Paradiversas construcciones de matrices P a partirde A, consideraremos el problema de determi-nar las graficas tales que la entropıa del sistemaes maxima.
Martes 11 de marzo
Nombre: Jose David Flores PenalozaInstitucion: Facultad de Ciencias, UNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Dibujando el doblecırculo en una malla de tamano mınimoCo-autores: S. Bereg, R. Fabila-Monroy, M. A.Lopez, P. Perez-LanteroResumen: En 1926, Jarnik planteo el problemade dibujar un n-agono convexo usando verticescon coordenadas enteras. El dio una construc-cion usando una malla de tamano [1, c∆n3/2]2,para una cierta constante c, y demostro que esetamano de malla es optimo salvo un factor cons-tante.
Nosotros consideramos el problema analo-go de dibujar el doble cırculo (una cons-truccion importante en geometrıa combinato-ria/computacional), y demostramos que se pue-de hacer en una malla del mismo tamano.Ademas, damos un algoritmo de tiempo O(n)para construir semejante conjunto de puntos.
Nombre: Walter Carballosa TorresInstitucion: Universidad Autonoma de Guerre-roCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Caracterizacion de lahiperbolicidad de algunos productos de graficasCo-autores: Amauris de la Cruz, Jose M.Rodrıguez, Jose M. SigarretaResumen: Sea X un espacio metrico geodesi-co y x1, x2, x3 ∈ X. Un triangulo geodesicoT = {x1, x2, x3} es la union de tres geodesicas[x1x2], [x2x3] y [x3x1] de X. El espacio X es
δ-hiperbolico (en el sentido de Gromov) si todolado de T esta contenido en la δ-vecindad de launion de los otros dos lados, para todo triangu-lo geodesico T de X. Se denota por δ(X) a laconstante de hiperbolicidad optima de X, es de-cir, δ(X) := ınf{δ ≥ 0 : X es δ-hiperbolico }.
El estudio de las graficas hiperbolicas es untema interesante dado que la hiperbolicidad deun espacio metrico geodesico esta relacionadocon la hiperbolicidad de una grafica asociada alespacio. Uno de los principales problemas en es-te area es estudiar la hiperbolicidad de determi-nadas operaciones de graficas. En este trabajose caracteriza la hiperbolicidad de algunos pro-ductos de graficas en terminos de propiedadesde sus factores.
Los productos estudiados son: el productofuerte y el producto lexicografico. Los resulta-dos fundamentales son los siguientes
El producto fuerte G1⊠G2 es hiperbolico siy solo si G1 es hiperbolico y G2 es acotadoo, G2 es hiperbolico y G1 es acotado.
Si G1 no es la grafica trivial E1, el productolexicografico G1 ◦ G2 es hiperbolico si ysolo si G1 es hiperbolico. En particular, seobtiene
δ(G1) ≤ δ(G1 ◦ G2) ≤ δ(G1) + 3/2.
Referencias
[1] Carballosa, W., Casablanca, R. M., De laCruz, A. and Rodrıguez, J. M., Gromovhyperbolicity in strong product graphs,Electr. J. Comb. 20(3) (2013), P2.
[2] Carballosa, W., de la Cruz, A., Rodrıguez,J. M. and Sigarreta J. M., Gromov hyper-bolicity in lexicographic product graphs.Submitted.
Nombre: Alejandro Contreras BalbuenaInstitucion: Universidad Autonoma del Estadode MexicoCorreo: [email protected]: InvestigacionTıtulo de la ponencia: A-nucleosCo-autores: Dra. Hortensia Galeana Sanchez,Dra. Marıa del Rocıo Rojas MonroyResumen: Introducimos el concepto de A-nucleo en Graficas m-coloreadas, el cual es unavariacion de los conceptos de nucleo y nucleopor trayectorias monocromaticas, mezclando lasideas de Absorbencia por Trayectorias Mono-cromaticas e Independencia.
Ademas se presentan algunos resultados queaseguran su existencia en ciertas digraficas.
Nombre: Julian Alberto Fresan FigueroaInstitucion: UAM-ICorreo: [email protected]: InvestigacionTıtulo de la ponencia: Arboles binarios ycoordenadas de JacobiCo-autores: Alma Rocıo Sagaceta Mejıa y LuisFranco PerezResumen: Las coordenadas de Jacobi son usa-das en mecanica celeste para estudiar configura-ciones que presentan simetrıa entre los cuerpos.Son muy importantes en el area pues son unaprimera integral y reducen en uno las dimen-siones del problema. En esta charla se presen-tara una generalizacion de las coordenadas de
Jacobi basada en arboles binarios. Tambien sedara un caso particular de configuracion inicialen el cual el uso de esta tecnica reduce en masde una dimension el problema
Nombre: Christian Rubio MontielInstitucion: UNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Una nueva caracteri-zacion de las graficas trivialmente perfectasResumen: Una grafica G se llama trivialmen-te perfecta si para cada subgrafica inducida, lacardinalidad mas grande de vertices indepen-dientes (esto es, el numero de independenciaα(G))iguala al numero total de clanes (maxi-males) m(G). Se dan caracterizaciones de lasgraficas trivialmente perfectas en termino de co-loraciones de vertices de G y se extienden lasdefiniciones a graficas infinitas.
Nombre: Francisco Javier Zaragoza MartınezInstitucion: UAM AzcapotzalcoCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Otro paso hacia la con-jetura de YuzvinskyCo-autores: Isidoro Gitler y Enrique ReyesResumen: Una matriz de r × s con entradasen {1, . . . , n} se dice intercalada si sus entra-das en cada renglon son distintas, sus entradasen cada columna son distintas y cada submatrizde 2 × 2 tiene dos o cuatro entradas distintas.Sea f(r, s) el mınimo valor de n para el cualexiste una matriz intercalada de r×s. En 1981,Sergey Yuzvinsky (University of Oregon) conje-turo que f(r, s) coincide con la funcion de Pfis-ter. Desde entonces se han demostrado varios
casos especiales de la conjetura, por ejemplopara r ≤ 5 o para r ≤ s = 2k con k ≥ 0. En2007, Kee Yuen Lam (University of British Co-lumbia) demostro un resultado que implica quela conjetura es cierta asintoticamente para 2
3de
las parejas (r, s). En esta platica mostrare unaextension de ese resultado que implica que laconjetura es cierta asintoticamente para 5
6de
las parejas (r, s). Este es un trabajo conjuntocon Isidoro Gitler y Enrique Reyes (Cinvestav).
Nombre: Cesar Hernandez CruzInstitucion: Facultad de Ciencias, UNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Espectros fuertes deconvexidad en rejillasCo-autores: Martha Gabriela Araujo Pardo,Juan Jose Montellano BallesterosResumen: Sea D = (V, A) una grafica orien-tada sin flechas multiples ni lazos. Para verticesdistintos u, v ∈ V , una uv-geodesica es una uv-trayectoria de longitud d(u, v). Decimos que unconjunto S ⊆ V es un conjunto convexo en Dsi para cualquier par de vertices u, v ∈ S, losvertices de toda uv-geodesica estan contenidosen S. El numero de convexidad de una grafi-ca orientada D, con(D), es la cardinalidad delconjunto convexo propio mas grande en D. Pa-ra una grafica G, definimos el espectro fuertede convexidad de G, SSC(G), de la siguienteforma:
SSC(G) = {con(D) : D orientacion fuerte de G}.
Una rejilla de n×m es el producto cartesiano deuna trayectoria de n vertices por una trayectoriade m vertices, Pn2Pm. En este trabajo calcu-
laremos el espectro fuerte de convexidad de G,donde G es cualquier rejilla.
Nombre: Isabel HubardInstitucion: IMATE-UNAMCorreo: [email protected]: DivulgacionTıtulo de la ponencia: Usando graficas paraencontrar generadores de un subgrupoResumen: Dado un grupo G con un conjuntode generadores (y relaciones) y cualquier sub-grupo H de G, construiremos una grafica paraencontrar generadores de H en terminos de losgeneradores de G. Para esto, revisarmos el con-cepto de grafica de Cayley y grafica de claseslaterales y las simetrıas de las mismas. Termi-naremos dando generadores del estabilizador deun elemento, dada una accion transitiva en unconjunto.
Miercoles 12 de marzo
Nombre: DinoInstitucion: IM-UNAMCorreo: [email protected]: DivulgacionTıtulo de la ponencia: Un viejo amorResumen: Vıctor introdujo la nocion de tensionen hipergraficas, mismo que generalizaba la co-nexidad en graficas. Por otro lado, Lovasz intro-dujo la nocion de boscosidad para hipergraficas.Una pregunta natural es si los bosques satura-dos son tensos, hecho que es facil de chocar enel caso de las graficas. En esta charla, demos-trare que si un bosque tiene el maximo numerode aristas que puede tener, entonces es tenso.Sorprendentemente, la prueba usa al productoexterior (o de Grassmann) del algebra lineal.
Nombre: Eugenia O’Reilly RegueiroInstitucion: IMUNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: H-nucleos en digrafi-cas 3-casi-transitivas.Co-autores: Hortensia Galeana SanchezResumen: Una digrafica D es asimetri-ca si todos sus arcos son asimetricos,y es 3-casi-transitiva si ∀x, y, z, w ∈V (D), (x, y), (y, z), (z, w) ∈ A(D) conlos vertices distintos 2 a 2 implica que(x, w) ∈ A(D) o (w, x) ∈ A(D).
Sean H una digrafica cualquiera (posible-mente con lazos) coloreada en vertices, y Duna digrafica H-coloreada, es decir, con sus ar-cos coloreados con los colores de los vertices deH . Un camino (trayectoria (o ciclo)) en H esun H-camino (H-trayectoria (o H-ciclo)) si los
colores consecutivos de sus arcos correspondena un camino (trayectoria (o ciclo)) en H . Unciclo es un casi-H-ciclo si es un H-ciclo salvopor a lo mas el color de un arco.
Un subconjunto N ⊂ V (D) es H-independiente si entre cualesquiera dos de susvertices no hay una H-trayectoria, y es H-absorbente si para todo x ∈ V (D)\N existe uny ∈ N tal que en D hay una H-trayectoria de xa y. Si N es H-independiente y H-absorbenteentonces es un H-nucleo.
Los H nucleos generalizan a los nucleos (sincoloracion) y a los nucleos por trayectorias mo-nocromaticas, en los que todos los arcos de Hson lazos.
En esta charla demostraremos que si unadigrafica D asimetrica, 3-casi transitiva, y H-coloreada es tal que todo C4 es un H-ciclo ytodo C3 es un casi-H-ciclo entonces D tieneun H-nucleo.
Nombre: Leonardo Ignacio Martınez SandovalInstitucion: UNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Conjuntos de puntoscon circunradios distintosCo-autores: Edgardo Roldan PensadoResumen: Fijemos un entero positivo k. En1975 Erdos se pregunto si con una cantidadsuficientemente grande de puntos en posiciongeneral en el plano, digamos nk, siempre es po-sible encontrar k de ellos de modo que todoslos triangulos que determinan tengan circunra-dio distinto.
Posteriormente presento un argumento paramostrar que en efecto esto sucedıa. Sin embargosin darse cuenta dejo de lado un caso no trivial
que ha sido ignorado a traves de los anos.En esta platica retomamos el argumento de
Erdos y presentamos el resultado que completala demostracion. Usaremos herramientas com-binatorias y de geometrıa algebraica.
Nombre: Nahid Yelene Javier NolInstitucion: UAM-IztapalapaCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Numero dicromaticode graficas circulantes planasCo-autores: Bernardo LlanoResumen: El numero dicromatico de unadigrafica D (dc(D)) es el mınimo numero decolores que se requieren para colorear los verti-ces de D de tal manera que las clases cromati-cas induzcan una subdigrafica acıclica en D y elnumero dicromatico de una grafica G se definecomo
dc(G) = max{dc(−→G) :
−→G orientacion de G}
V. Neumann-Lara conjeturo que si D es unaorientacion de una grafica plana, entonces exis-te una particion de V (D) = V1|V2 tal quela subdigrafica inducida D[V i] es acıclica pa-ra i = 1, 2, es decir dc(D) = 2. En esta platicase presentaran dos casos particulares que satis-facen la conjectuta mencionada:
(i) las graficas circulantes planas y
(ii) algunas graficas planas maximales que tie-nen como subgraficas generadoras a grafi-cas circulantes planas.
Jueves 13 de marzo
Nombre: Rafael Villarroel FloresInstitucion: Universidad Autonoma del Estadode HidalgoCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Clan comportamientode graficas con vecindad pequenaCo-autores: Paco Larrion, Miguel PizanaResumen: Resumen: Todas nuestras graficasson simples y finitas. Dadas graficas G, L, de-cimos que G es extension de L si la vecindadabierta de todo vertice de G induce una graficaisomorfa a L. J. Hall demostro que hay exacta-mente 65 graficas de hasta 6 vertices que pue-den extenderse.
La grafica de clanes K(G) es la grafica deinterseccion del conjunto de subgraficas com-pletas maximales (clanes) de G. Si la sucesionde graficas G, K(G), K2(G), . . . es tal que losordenes de los terminos tiende a infinito, deci-mos que G diverge. Si G no diverge, decimosque converge. Dos graficas tienen el mismo clancomportamiento si ambas divergen o bien, siambas convergen.
En el presente trabajo se muestra que si dosgraficas G1, G2 son extensiones de la mismagrafica L, con |L| ≥ 6, entonces G1, G2 tienenel mismo clan comportamiento. Sin embargo,se muestran ejemplos que el comportamientopuede ser distinto considerando graficas L conmas vertices.
Nombre: Marta Cabo NodarInstitucion: ITAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Algoritmo de flujomaximo en graficas bipartitas para la elabora-cion de horarios en una escuela de educacionsuperiorCo-autores: Marcela MaldonadoResumen: Uno de los mayores problemas quese enfrentan las universidades privadas de Mexi-co es la gran cantidad de profesores de tiempoparcial que imparten clases. Estos no formanparte del plantel fijo, y solo estan en la institu-cion el tiempo que duran sus clases. Ademas,si sus clases no son asignadas en el horario queellos eligen es posible que se nieguen a impar-tirla. Por otro lado se encuentran los profesoresde tiempo completo, que deben cubrir su cuotade docencia segun los requisitos de la institu-cion. Entre ambos grupos deben cubrir todoslos grupos de todas las materias que se impar-ten. Sin embargo existen mas restricciones delas que podemos imaginar de inicio, como queciertas materias solo se pueden programar endıas fijos, o que materias del mismo semestreno pueden estar programadas a la misma horaen el mismo dıa.
En esta charla se explicara como desarrollarun horario factible para una institucion de edu-cacion superior a partir de algoritmos de flujomaximo sobre graficas bipartitas sobre las queresolvemos sucesivos problemas de asignacion,que al unirlos ofrecen un horario factible bajolas condiciones de materias, horas y dıas prefe-ridos por cada uno de los profesores que formanel plantel docente de la institucion.
Nombre: Patricio Ricardo Garcıa VazquezInstitucion: Universidad Nacional Autonomade MexicoCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Algunas propiedadesde las digraficas 4-transitivasCo-autores: Cesar Hernandez CruzResumen: Si consideramos a D una digafi-ca con conjunto de vertices V (D) y conjuntode flechas A(D) y k ∈ N , decimos que unadigrafica es k-transitiva si para cualesquiera dosvertices u, v ∈ V (D) tales que existe una uv-trayectoria dirigida de longitud k, se tiene que(u, v) ∈ A(D). Anteriormente se han estudia-do varios resultados relacionados con digraficastransitivas y 3-transitivas. En esta platica abor-daremos algunas de las propiedades que con-ciernen a las digraficas 4-transitivas, cuya carac-terizacion, en el caso fuertemente conexo, fuedada por Hernandez-Cruz. Un k-nucleo de unadigrafica D se define como un subconjunto devertices N ⊆ V (D) tal que es k-independiente y(k-1)-absorbente. En la platica se caracterizarana las digraficas 4-transitivas que contienen un3-nucleo y a las que tienen un 2-nucleo (o sim-plemente nucleo). Ademas, utilizando este ulti-mo resultado se dara una prueba de la conjetu-ra de Laborde-Payan-Xuong para digraficas 4-transitivas, la cual establece que para cualquierdigrafica D se puede encontrar un subconjuntode vertices independiente que intersecta a todatrayectoria de longitud maxima en D.
Nombre: Fernando Andres BenavidesInstitucion: Universidad Nacional Autonomade Mexico - Universidad de Narino (Colombia)Correo: [email protected]: DivulgacionTıtulo de la ponencia: Graficas vistas comotareas distribuidasCo-autores: Sergio RajsbaumResumen: Muchas de las acciones o decisionesque vemos o tomamos hoy en dıa estan en cons-tante interaccion, como por ejemplo entre ungrupo de personas, en redes sociales, en redesbancarias etc. Adicionalmente a esto debemostener en cuenta que estas acciones o decisionespueden estar afectadas por situaciones exter-nas. Un ejemplo mas concreto es el de un grupode personas que tratan, por vias sociales, llegara consensos, pero sus decisiones pueden estarafectadas por fallas en el sistema, por retrasosen los mensajes o simplemente por distorsionesen los mismos. Otro ejemplo esta en considerarun grupo de ordenadores trabajando en para-lelo con el fin de dar solucion a una determi-nada tarea. La Computacion Distribuida es unade las ramas de la computacion que se dedica aanalizar modelos computacionales que permitandecidir si una determinada tarea tiene solucion.En las ultimas dos decadas ha tomado fuerza elanalizar problemas de computo distribuido me-diante el modelamiento de estos via complejossimpliciales, que para el caso de dos procesoslo que se tienen son graficas. En esta platicapretendemos es dar una introduccion basica aproblemas de computo distribuido que involu-cran dos procesos mediante el planteamiento yanalisis de algunos problemas basicos.
Nombre: Adriana HansbergInstitucion: UNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Locating-dominatingsets and identifying codes in graphs of girth atleast 5Co-autores: Camino Balbuena, Florent Fou-caudResumen: Locating-dominating sets and iden-tifying codes are two closely related notions inthe area of separating systems. Roughly spea-king, they consist in a dominating set of a graphsuch that every vertex is uniquely identified byits neighbourhood within the dominating set.We present bounds on the size of a smallestlocating-dominating set or identifying code forgraphs of girth at least 5 and of given minimumdegree. We use the technique of vertex-disjointpaths to provide upper bounds on the minimumsize of such sets, and construct graphs who co-me close to meet these bounds.
Nombre: Marıa Luisa Perez SeguıInstitucion: Fac. Cs. Fısico-Matematicas, Uni-versidad MichoacanaCorreo: [email protected]: DivulgacionTıtulo de la ponencia: A lo mas 3 mentirasseguidas y base 2Resumen: Muchos problemas interesantes dematematicas, aunque no hablen del numero 2,se resuelven usandolo de diversas maneras (apa-reamientos, modulo 2, particion en dos clases,maxima potencia de 2, expansion binaria).
La idea de la platica es explicar esto y resol-ver el siguiente problema que fue una parte deun problema de la Olimpiada Internacional de
Matematicas de 2012:Delia quiere adivinar el numero n que Roy es-
cogio dentro de un conjunto R de 100 enteros(que Delia conoce tambien). Para ello, escogeun S ⊂ R y pregunta si n ∈ S. Esto lo puedehacer tantas veces como quiera. A cada pregun-ta Roy contesta sı o no; puede mentir pero, alo mas, 3 veces seguidas. Probar que llega unmomento que Delia conoce un subconjunto Dde R con 8 elementos tal que n ∈ D.
Nombre: Gelasio SalazarInstitucion: Universidad Autonoma de SanLuis PotosiCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Encajes de graficas enlibrosResumen: Un libro es un espacio topologicoque consta de una lınea, que es el lomo del li-bro, y k semiplanos (las paginas), identificadosa lo largo del lomo. En un encaje de una grafi-ca en un libro, los vertices estan todos en ellomo, y ninguna arista toca en lomo mas queen sus extremos. El problema fundamental eneste campo es encontrar el numero de paginasde una grafica G, que es el mınimo k tal que Gpuede encajarse en un k-libro. En esta platicapresentaremos resultados recientes sobre enca-jes de graficas d-regulares en libros.
Viernes 14 de marzo
Nombre: M. Gabriela Araujo PardoInstitucion: Instituto de MatematicasCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Coloraciones hetero-cromaticas balanceadas en planos proyectivosCo-autores: Gyorgy Kiss y Amanda MontejanoResumen: Un plano proyectivo de orden q defi-ne de manera natural una hipergrafica Πq cuyosvertices e hiperaristas son los puntos y las lıneasdel plano proyectivo respectivamente. Diver-sos autores han estudiado el numero cromati-co superior de estas hipergraficas, denotado porchi(Πq), el cual esta definido como el maximoentero k para el cual existe una k-coloracionde los vertices de Πq en la cual ninguna de sushiperaristas es heterocromatica o arcoiris (contodos sus vertices de colores distintos). En estetrabajo generalizamos este concepto a la nocionde numero cromatico superior balanceado,denotado por χb(H), en este tipo de coloracio-nes las clases cromaticas tienen exactamente elmismo numero de elementos o a lo mas difie-ren en un elemento. Nuestro resultado principales que el numero cromatico superior balancea-do de los planos proyectivos esta acotado de lasiguiente manera:
q2 + q + 1
6≤ χb(Πq) ≤
q2 + q + 1
3.
Cabe mencionar que el valor del numerocromatico es exactamente el valor del numeroheterocromatico menos uno, ya que la definiciondel numero heterocromatico es el mınimo ente-ro h para el cual cualquier h-coloracion de losvertices de Πq induce al menos una hiperarista
heterocromatica o arcoiris. En Mexico existendiversos trabajos en este tema para distintas hi-pergraficas pero en general se trabaja con elnumero heterocromatico.
Nombre: Damien ImbsInstitucion: UNAMCorreo: [email protected]: DivulgacionTıtulo de la ponencia: Computacion distri-buida y topologıaResumen: La computacion distribuida estudiala interaccion de varias entidades computacio-nales, las cuales se pueden comunicar de multi-ples maneras. Tal conjunto de entidades compu-tacionales se llama un sistema distribuido. Debi-do a la incertidumbre que surge con la presenciade varios procesos, los cuales pueden tener ve-locidades diferentes y en ciertos casos puedenfallar, algunos problemas son imposibles de re-solver.
Un avance fundamental en la teorıa de lacomputacion distribuida fue el descubrimientode la relacion entre ejecuciones de sistemas dis-tribuidos y complejos simpliciales. En esta pla-tica veremos como la incertidumbre inherentea un sistema distribuido se puede representarusando complejos simpliciales y como se pue-den ocupar herramientas topologicas para pro-bar imposibilidades en sistemas distribuidos.
Nombre: Juan Pablo Dıaz GonzalezInstitucion: Instituto de Matematicas UnidadCuernavaca UNAMCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Diagramas de graficasanudadas con complementos hiperbolicos en ba-jas dimensionesResumen: Mediante una aplicacion de la con-traccion de aristas de graficas y el estudiogeometrico de poliedros, se dibujan en el planodiagramas de proyecciones que muestran la cla-se de isotopıa de nudos y graficas anudadas cu-yos complementos en la 3-esfera admiten es-tructuras geometricas hiperbolicas.
Ademas, generalizando este metodo se mues-tra una escultura del enlace de 5 superficies to-roidales anudadas cuyo complemento en la 4-esfera admite una estructura hiperbolica.
Nombre: Jose Luis Cosme AlvarezInstitucion: Universidad AutonomaMetropolitana-IztapalapaCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Torneos regulares−→ω 3-crıticosCo-autores: Bernardo LlanoResumen: La inconexion libre de
−→C 3 se define
como el maximo numero de colores necesarios,para colorear los vertices de una grafica dada,de tal manera que no se induzcan triangulosdirigidos heterocromaticos.
Un problema estudiado por Vıctor Neumann-Lara era el siguiente: dado un parametro α aso-ciado a un torneo T y el torneo T\{v} obtenidoal eliminar algun vertice del torneo T , deseamosestudiar que tanto cambia el parametro α, aso-
ciado al torneo T\{v} con respecto al asociadoal torneo original T . Si el parametro α cambiapara cada vertice del torneo, entonces decimosque T es crıtico en vertices respecto al parame-tro α. Ası diremos que un torneo regular T es−→ω 3-crıtico, si para cualquier vertice v ∈ V (T ),se tiene que
−→ω 3(T ) < −→ω 3(T\{v})
En esta platica estudiaremos y mostraremosa la unica familia de torneos regulares que son−→ω 3-crıticos y algunas consecuencias sobre lostorneos semiregulares.
Posters (martes)
Nombre: Pilar CanoInstitucion: Facultad de Ciencias, UNAMCorreo: [email protected]: Reporte de TesisTıtulo de la ponencia: Hamiltonicidad en ge-neralizaciones de torneos bipartitosResumen:
Nombre: Loiret Alejandrıa Dosal TrujilloInstitucion: Instituto de Matematicas UNAMCorreo:[email protected]
Nivel: InvestigacionTıtulo de la ponencia: De graficas arista-coloreadas y politopos regularesCo-autores: Alejandra Ramos RiveraResumen: Una grafica de representacion porpermutaciones o CPR-grafica, es una mul-tigrafica n-arista etiquetada asociada al grupode automorfismos Γ(P ) de un politopo regularP de rango n. Mas aun, se pueden dar con-diciones necesarias y suficientes para que unagrafica sea una CPR-grafica de algun polito-po regular y a traves de dicha grafica cons-truir politopos regulares que tengan como gru-po de automorfismos a algun grupo alternanteAn. Este poster tiene como objetivo principalmostrar como construir CPR-graficas dado unn-politopo regular y como obtener un polito-po regular que tenga como CPR-grafica a unagrafica dada.
Nombre: Marina Duran OrozcoInstitucion: UNAM, Instituto de Matematicas,Unidad CuernavacaCorreo: [email protected]: InvestigacionTıtulo de la ponencia: Estructura de circuitosde Matroides IntercaladosResumen: Estudiaremos las definiciones basi-cas de matrices intercaladas para posteriormen-te analizar los circuitos que se obtienen en elmatroide intercalado de la matriz diadica de4x4.
Nombre: Diego Fernandez HernandezInstitucion: Universidad Autonoma deQueretaroCorreo: [email protected]: PosterTıtulo de la ponencia: Estudio de coloracio-nes libres en teorıa anti-RamseyCo-autores: Amanda Montejano Cantoral,Jose David Suarez GonzalezResumen: La teorıa anti-Ramsey se ocupadel estudio de la existencia de estructurasheterocromaticas en universos coloreados.Una coloracion se llama libre si no contieneestructuras heterocromaticas. El estudio de lascoloraciones libres en diferentes contextos, esuna lınea de investigacion muy reciente congran potencial en la obtencion de resultadosanti-Ramsey. En este poster se presentan dosproyectos de tesis de licenciatura referentes altema. El primero con respecto a progresionesaritmeticas heterocromaticas de longitud tresen intervalos de numeros enteros, el segundocon respecto a soluciones de la ecuacion deSchur en grupos abelianos de orden primo.
Nombre: Ian Andrei Gleason FreidbergInstitucion: UNAMCorreo: [email protected]: Reporte de Tesis de doctoradoTıtulo de la ponencia: El antiprismaCo-autores: Ian GleasonResumen: La motivacion principal de esta te-sis es generalizar la construccion del antiprismaa cualquier politopo abstracto y determinar elgrupo de automorfismos de esta construccion enterminos del politopo original. Para lograr estafaena se desarrollara herramienta fundamentalen el estudio de productos en politopos, se de-finiran cuatro tipos de productos en politoposdistintos, demostraremos teoremas de factoriza-cion unica bajo estos productos y pasaremos adeterminar el grupo de automorfismos en termi-nos de los primos. Una vez que tengamos losresultados necesarios para productos explicare-mos la estrecha coneccion entre los productosy el antiprisma. Determinaremos la funcion delantiprisma como una funcion multiplicativa enlos primos, y podremos encontrar el grupo deautomorfismos de esta manera.
Nombre: Pablo Gonzalez MoctezumaInstitucion: FCiencias. UNAMCorreo: [email protected]: Reporte de Tesis de doctoradoTıtulo de la ponencia: Los espacios shift dearbolCo-autores: Ricardo Gomez AızaResumen: En los ultimos anos se ha diversifi-cado el tipo de espacios shift estudiados en ladinamica simbolica. Los shift de arbol se en-cuentran entre los shift de una y dos dimensio-nes y nos presentan el problema de definir mu-chas propiedades bien conocidas en los espacios
uno dimensionales que se pueden intepretar demuchas formas en dimension dos y para los queen este caso la extencion es muy natural
Nombre: Luis Francisco Hernandez SanchezInstitucion: Universidad Autonoma Metropoli-tana AzcapotzalcoCorreo: [email protected]: PosterTıtulo de la ponencia: Problemas de limpie-za periodica: Algoritmos y analisis de poliedrospara algunas clases de graficasCo-autores: Laura Elena Chavez Lomeli, Fran-cisco Javier Zaragoza MartınezResumen: Imagine que se tiene una ciudad yquiere limpiar todas sus calles. Suponiendo quecada calle de la ciudad es de doble sentido sepuede modelar la ciudad como una grafica diri-gida D = (V, A) con las siguientes caracterısti-cas:
Cada vertice representa una esquina de laciudad.
Cada calle esta representada por arcos queunen dos esquinas. Para cada calle hay dosarcos en sentido opuesto, que representanlos dos lados de la calle. Debido a esto lagrafica dirigida sera fuertemente conexa.
Cada calle tiene un costo de recorrido nonegativo.
A partir de esto, el problema general consisteen encontrar un recorrido de limpieza para dosdıas consecutivos de manera que se limpie cadauna de las calles por ambos sentidos recorrien-do la menor distancia posible. Algunas graficaspermiten resolver el problema en tiempo polino-mial, incluso lineal. Para otras clases de graficas
no se conoce la complejidad, pero se usar ana-lizar el poliedro asociado a la relajacion linealpara intentar descubrir la complejidad de clasesde graficas.
Nombre: Esteban Landerreche CardilloInstitucion: ITAMCorreo: [email protected]: PosterTıtulo de la ponencia: Un protocologeometrico para el intercambio de informacion:El problema de las cartas rusasResumen: Alicia, Bob y Cathy tienen un ma-zo de cartas conocido y se lo reparten entre lostres. Alicia y Bob quieren enterarse de las cartasdel otro, sin que Cathy se entere. pero no es po-sible usar codigos, ya que Cathy esta con ellosen todo momento. ¿Existe una forma para quese intercambien esta informacion y que Cathyno sepa quien tiene que carta? Un protocoloası dependerıa de la informacion a la que Cathyno puede acceder, como la informacion conteni-da en las manos de Alicia y Bob. Un protocoloası se puede generar de varias maneras, una delas cuales es en espacios vectoriales sobre cam-pos finitos. Asociando un punto a cada cartadel mazo, Alicia puede generar un espacio vec-torial en el cual su mano es un subespacio. Bob,a partir de sus cartas, podra descartar todos lossubespacios menos uno, descubriendo la manode Alicia. Cathy, por otro lado, no podra saberni siquiera el paradero de una carta. Se bus-ca presentar las cotas sobre los tamanos de lasmanos que permiten hacer esto posible.
Nombre: Maria Elena Martinez CueroInstitucion: UAMCorreo: [email protected]: PosterTıtulo de la ponencia: Arboles generadorescon grados acotados y peso bajoResumen: Dada una grafica completa G conuna funcion de peso que cumple con la desigual-dad del triangulo: E(G)→ R
+ en las aristas deG. Dado un entero positivo k¡n, un arbol gene-rador T de G es un k- arbol de G si el grado decada vertice no terminal de T es por lo menosk.
En este trabajo presentaremos una heurısticapara encontrar un k-arbol T de G cuyo peso searelativamente bajo y un algoritmo exacto.
Nombre: Sara Jani Murillo GarciaInstitucion: UNAM, Facultad de CienciasCorreo: [email protected]: PosterTıtulo de la ponencia: Combinatioria, geo-metrıa e imaginacionResumen: Se da una construccion no lineal pa-ra una de las tres configuraciones (93), que coin-cide con la tabla combinatoria de incidenciasde la denotada como (93)3 cuya construccionesta racionada con la seccion aureo. A partir dela configuracion, se considera una superconfi-guracion (123) que resulta ser el estrellamientodel icosaedro regular. Tambien se muestra queD6 ≃ Stab(93)3 ≤ Aut(123) ≃ D12.
Nombre: Jose Alberto Pena GarciaInstitucion: Universidad autonoma del Estadode hidalgoCorreo: [email protected]: PosterTıtulo de la ponencia: Problema del final fe-lizResumen: En este trabajo se presenta el pro-blema del ”final feliz”, el cual consiste en en-contrar cual es numero mınimo de puntos enposicion general que se requieren para construirun n-agono.
Nombre: Sergio Luis Perez PerezInstitucion: Universidad Autonoma Metropo-litana - CuajimalpaCorreo: [email protected]: PosterTıtulo de la ponencia: Algoritmos yheurısticas para el problema de asignacionmultidimensionalCo-autores: Francisco Javier ZaragozaMartınez y Carlos Enrique Valencia OletaResumen: El problema de asignacion esun problema de optimizacion que trata conla cuestion de como asignar elementos deuna grafica bipartita ponderada tratando deminimizar el costo de las parejas seleccionadas.En el problema de asignacion multidimensionallo unico que se incrementa es el numero N deconjuntos disjuntos que desean ser asociados,digamos con N ≥ 3. En el caso general paraN dimensiones se tienen aristas que asocianal mismo tiempo a N vertices (hiperaristas),cada uno de ellos de los N conjuntos y quetienen asociado un determinado costo, dondenuevamente se desea encontrar una asignacionde costo mınimo. En 1972 Karp demostro que
este problema es NP-Duro. En este trabajopresentamos algunas tecnicas exactas queresuelven el problema para instancias pequenas(N = 3 y no mas de 20 vertices por conjunto)y algunas heurısticas que se estan desarrollandocon la finalidad de resolver instancias masgrandes de este problema.
Nombre: Eduardo Rojas SilvaInstitucion: UAM AzcapotzalcoCorreo: [email protected]: PosterTıtulo de la ponencia: Problema de ruteo delautobus escolar con recoleccion mixtaCo-autores: Rafael Lopez Bracho, JavierRamırez Rodrıguez.Resumen: El problema de ruteo del autobusescolar consiste es recoger a los estudiantes des-de algun punto y llevarlos a la escuela tratan-do de optimizar una serie de variables. En estetrabajo se considera una recoleccion mixta delos estudiantes, es decir, los estudiantes pue-den caminar a un punto de recoleccion para serrecogidos o son recogidos directamente en suscasas. Se presenta una formulacion del proble-ma donde la funcion objetivo busca minimizarla distancia recorrida por los estudiantes a lospuntos de recoleccion ası como la distancia delas rutas que recorren los autobuses. Ademas sepretende calibrar y presentar una heurıstica queresuelva algunos casos de prueba del problema.
Nombre: Jose David Suarez GonzalezInstitucion: Universidad Autonoma deQueretaroCorreo: [email protected]: PosterTıtulo de la ponencia: Estudio de coloracio-nes libres en teorıa anti-RamseyCo-autores: Diego Fernandez Hernandez yAmanda Montejano CantoralResumen: La teorıa anti-Ramsey se ocupadel estudio de la existencia de estructurasheterocromaticas en universos coloreados.Una coloracion se llama libre si no contieneestructuras heterocromaticas. El estudio de lascoloraciones libres en diferentes contextos, esuna lınea de investigacion muy reciente congran potencial en la obtencion de resultadosanti-Ramsey. En este poster se presentan dosproyectos de tesis de licenciatura referentes altema. El primero con respecto a progresionesaritmeticas heterocromaticas de longitud tresen intervalos de numeros enteros, el segundocon respecto a soluciones de la ecuacion deSchur en grupos abelianos de orden primo.
Nombre: Briseida Guadalupe Trejo EscamillaInstitucion: Universidad Autonoma del Estadode HidalgoCorreo: [email protected]: PosterTıtulo de la ponencia: Representaciones delgrupos simetrico en homologıas.Resumen: El presente trabajo tiene como ob-jetivo analizar la estructura de la homologıa decomplejos simpliciales construidos a partir deuna grafica simple finita en donde actua el gru-po simetrico Sn.
Se define la grafica M(G) de emparejamien-
tos de la grafica simple G como la grafica cu-yos vertices son las aristas de G y dos verticesson adyacentes si las correspondientes aristasson ajenas. En la grafica Gn = M(Kn), el gru-po Sn actua de manera natural, por lo que sushomologıas con coeficientes complejos definenrepresentaciones de Sn.
La descomposicion en irreducibles de taleshomologıas ha sido exhibida por Bouc (1992).En el presente trabajo se muestra el resulta-do correspondiente para la grafica de clanesK(G6).
Nombre: Luis Eduardo Urban RiveroInstitucion: Universidad Autonoma Metropoli-tana Unidad AzcapotzalcoCorreo: [email protected]: PosterTıtulo de la ponencia: Algoritmos para lacaptura de objetos con un intervalo de existen-cia sobre una rectaCo-autores: Rafael Lopez Bracho, FranciscoJavier Zaragoza MartınezResumen: En un enfoque del problema delagente viajero se busca el recorrido mas rapidoque pase por todas las ciudades que debe visitar.Una generalizacion de este problema, conocidacomo el problema del agente viajero con obje-tos moviles, considera que no solo se mueve elagente sino que tambien se mueven los lugaresque debe visitar. Dicho problema se pudiera pre-sentar en el reabastecimiento de combustibles aembarcaciones que siguen una ruta y que nopueden detenerse, o incluso problemas de ındo-le ambiental o de seguridad nacional. Evidente-mente se requieren las siguientes condiciones:
La velocidad del agente debe ser suficientepara alcanzar a todos los objetos moviles.
Se debe conocer la trayectoria de los obje-tos moviles.
En este trabajo se muestran algunos resultadosalgorıtmicos basados en programacion lineal so-bre una variante unidimensional de este proble-ma, en la cual los puntos a visitar existen solodurante un intervalo de tiempo, con tres crite-rios de captura distintos: Tiempo mınimo, mıni-ma distancia total recorrida y maxima cantidadde objetos atrapados.
Nombre: Gualberto Vazquez CasasInstitucion: Universidad Autonoma Metropo-litana Unidad AzcapotzalcoCorreo: [email protected]: PosterTıtulo de la ponencia: Calculo de flujoselegantes en graficas 3-conexasCo-autores: Francisco Javier ZaragozaMartınez, Rodrigo Alexander Castro CamposResumen:
XX
IX C
oloq
uio
Víc
tor
Neu
man
n- L
ara
de T
eorí
a de
las
Grá
fica
s, C
ombi
nato
ria
y su
s A
plic
acio
nes
P R
O G
R A
M A
Lune
s Martes
Miércoles
Jueves
Vierne
s 8:45
-‐9:15
Inau
guración
9:20
-‐10:00
Juan
José M
ontellano
Javier Bracho
Silvia Ferná
ndez
Jorge Urrutia
Richard Wilson
10:00-‐10
:20
Café
10:20-‐10
:45
Criel M
erino
David Flores
Dino
Ra
fael Villaroe
l Gabrie
la Araujo
10:45-‐11
:10
Juan Carlos H
ernánd
ez
Walter C
arballosa
Eugenia O'Reilly
Marta Cabo
Damien Im
bs
11:10-‐11
:35
Ilán A. Goldfed
er
Alejandro Co
ntreras
Leon
ardo
Martín
ez
Patricio García
Juan Pablo Díaz
11:35-‐12
:00
Café
12:00-‐12
:25
Isaac Arelio Ríos
Julián Fresán
Nahid Ja
vier
Fernando
Ben
avides
José Luis C
osme
12:25-‐12
:50
Natalia García-‐Co
lín
Concurso de
Posters
Migue
l Ángel Pizañ
a Ad
riana Hansberg
Luis M
ontejano
12
:50-‐1:05
Comida
Clau
sura
4:00
-‐4:40
Hortensia Galeana
Gilb
erto Calvillo
Excursión
Bernardo
Abrego
4:40
-‐5:05
Jesús A
lva
Christia
n Ru
bio
María Luisa Pérez
5:05
-‐5:20
Café
café
5:20
-‐5:45
Ma. Guadalupe
Ro
drígue
z Francisco Zaragoza
Gelasio Salazar
5:45
-‐6:10
Guadalupe
Gaytán
Cesar H
ernánd
ez
Sesión
de Prob
lemas
6:10
-‐6:35
Ricardo Góm
ez
Isabel Hub
ard
07
:00-‐10
:00
Brindis
