Embed Size (px)
Citation preview
Programa
del 4 al 9 de marzo de 2018Universidad de La Habana, Cuba
XXXIII COLOQUIO VÍCTOR NEUMANN-LARADE TEORÍA DE LAS GRÁFICAS, COMBINATORIA Y SUS APLICACIONES
XXXIII Coloquio Víctor Neumann-Lara de Teoría de las
Gráficas, Combinatoria y sus Aplicaciones
Universidad de La Habana
del 4 al 9 de marzo de 2018
Lunes
Nombre: Alfredo SomozaInstitución: Facutad de Matemáticas y Cien-cias de la Computación, Universidad de La Ha-banaCorreo: [email protected]
Nivel: PlenariaTítulo de la ponencia: Sobre un problema declusteringCo-autores:
Resumen: Dado un conjunto de puntos delplano y un entero k, encontrar el agrupamien-to de tamaño k que minimiza la suma de lasdistancias entre los puntos que pertenecen agrupos distintos es un problema interesante declustering de tipo geométrico. Sobre su comple-jidad algorítmica, relación con el problema declique de costo máximo y posibles alternativasde solución, se estará comentando en la charla.
Nombre: Miguel Raggi PérezInstitución: ENES Morelia, UNAMCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Espigas
Co-autores: Édgar Chávez, Luis GuillermoRuízResumen: Una espiga es un objeto geométricoque consta de un vértice y algunos ángulos a sualrededor. Consideraremos el problema compu-tacional de decidir si dos espigas son isomorfas.Después generalizaremos y daremos algunos al-goritmos eficientes para tres problemas que re-sultan equivalentes.
Nombre: José Antonio Montero AguilarInstitución: UNAM-Centro de Ciencias Mate-máticasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: De un ejemplo congráficas a un problema con torosResumen: En esta charla exploraremos con de-talle una estructura de incidencia sobre K6. Estaconstrucción nos servirá para motivar un proble-ma general de mapas con cuadrados en el toro.Finalmente, mostraremos algunos resultados re-lativos a este problema.
Nombre: Ismael Ariel Robles MartínezInstitución: Universidad AutónomaMetropolitana-Iztapalapa
Correo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Sobre clanes ybiclanesCo-autores: Miguel Ángel PizañaResumen: La gráfica de clanes K(G) deuna gráfica G es la gráfica intersección delconjunto de todos los clanes maximales de G(y K2
(G) = K(K(G)) ). La suspensión S(G)
de una gráfica G es la gráfica que se obtienede G añadiendo dos nuevos vértices que sonadyacentes a todos los demás vértices, exceptoentre ellos dos. Un biclan (X, Y ) es un parordenado de subconjuntos de vértices de G (nonecesariamente disjuntos) tal que cada vérticex 2 X es adyacente o igual a cada vérticey 2 Y y (X, Y ) es maximal bajo inclusiónde componentes. Denotamos por B(G) a lagráfica cuyos vértices son los biclanes de G,con adyacencias dadas por (X, Y ) ' (X 0, Y 0
)
si y sólo si X \X 0 6= ? o Y \ Y 0 6= ?.Estudiamos la segunda gráfica de clanes de
suspensiones de gráficas, K2(S(G)), y las ca-
racterizamos en términos de un operador de bi-clanes auxiliar B, el cual transforma una grá-fica G en su gráfica de biclanes B(G). Dichacaracterización es: K2
(S(G))
⇠=
B(K(G)). En-contramos una caracterización de las gráficas,G, que maximizan |B(G)| para cualquier ordenn = |G|. Esta versión particular del operadorde biclanes es nuevo en la literatura. La moti-vación principal para estudiar B(G) es el inten-tar caracterizar las gráficas G que maximizan|K2
(G)|.
Nombre: Antonio de Jesús Torres HernándezInstitución: Universidad Autónoma de SanLuis Potosí
Correo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Inflando secuenciascirculares en busca de dibujos con pocos crucesCo-autores: Gelasio Salazar AnayaResumen: El número de cruce rectilíneo cr(n),es el mínimo número de cruces de aristas de-terminado por cualquier conjunto de n puntosen el plano. Este parámetro fue propuesto porel artista plástico Anthony Hill e inspirado enel problema de la fábrica de ladrillos de Pál Tu-rán. Encontrar el número de cruce rectilíneo pa-ra cualquier n, sigue siendo un problema abier-to. En esta charla hablaremos de los avances eneste tema y daremos un algoritmo que generadibujos con pocos cruces mediante el procesode “inflado” de secuencias circulares de dibujosconocidos.
Nombre: Ana Paulina FigueroaInstitución: Instituto Tecnológico Autónomode MéxicoCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Programación enteray jaulasCo-autores: Gabriela Araujo, Jesús de Loera,Edgar PossaniResumen: En esta charla discutiremos sobremodelar el problema de encontrar una jaulausando programas de programación lineal en-tera.
Nombre: Joaquín TeyInstitución: Universidad AutónomaMetropolitana-IztapalapaCorreo: [email protected]
Nivel: Investigación
Título de la ponencia: Galaxias conservati-vasCo-autores: Ilán GoldfederResumen: Una gráfica de tamaño n esconservativa si para sus aristas existen unaorientación y una asignación de pesos distintosen {1, 2, ..., n} tales que, en cada vértice degrado al menos tres, la suma de los pesos delas flechas que entran coincide con la suma delos pesos de las flechas que salen.
En esta charla veremos cómo construir ga-laxias conservativas de tamaño n y cómo es-tas determinan cierta descomposición en ciclosde las aristas de la gráfica completa de orden2n+ 1.
Nombre: Miguel PizañaInstitución: Universidad AutónomaMetropolitana-IztapalapaCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Lógica, clanes yjuegosCo-autores: Carmen CedilloResumen: Usando teoría de juegos. Probamosque la clan-divergencia no puede ser expresadacon lógica de primer orden de teoría de lasgráficas.
Nombre: Citlalli Zamora MejíaInstitución: Universidad Autónoma del Estadode HidalgoCorreo: [email protected]
Nivel: DivulgaciónTítulo de la ponencia: Gráficas localmente3K2 usando GAPCo-autores: Rafael Villarroel FloresResumen: Usando el sistema computacional
GAP se implementó un paquete que sirve deayuda para generar gráficas localmente 3K2, asícomo para analizar algunas de sus propiedades.La charla pretende mostrar su funcionamiento eincitar al uso de la tecnología para experimentarsobre algunas posibles líneas de investigación.
Nombre: Claudia Marlene de la Cruz TorresInstitución: Universidad AutónomaMetropolitana-CuajimalpaCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Sobre las gráficask-probe completas y las gráficas k-probe splitCo-autores: Luciano GrippoResumen: Sea G una familia de gráficas. Unagráfica G = (V,E) es probe-G si existe unconjunto independiente N ✓ V y un conjuntoF (posiblemente vacío) de pares no ordenadosuv de vértices en N tales que uv 62 E, de formatal que la gráfica G⇤
= (V,E [ F ) pertenecea la familia G. A la gráfica G⇤ se le llamaprobe-G amalgamiento de G. Las gráficasprobe-G han sido estudiadas para diversasfamilias de gráficas G, tanto desde un punto devista estructural como algorítmico. Una gráficaG = (V,E) es k-probe-G si existen k conjuntosindependientes N1, N2, . . . , Nk
de V (G) talesque existe una gráficas G⇤
= (V,E [ F ) (conF \ E = ;) donde cada arista uv 2 F tieneambos extremos en N
i
, para algún i = 1, . . . , k.Una gráfica split es una gráfica tal que su
conjunto de vértices puede ser particionado enun clique Q y un conjunto independiente S.El parámetro split width de una gráfica G,spw(G), es el número mínimo k de conjuntosindependientes N1, N2, . . . , Nk
de V (G) tal queexiste un amalgamiento de G a G⇤, de mane-
ra que G⇤ sea una gráfica split y que para todaarista xy en E(G⇤
) que no pertenezca a G, per-tenezca a N
i
para algún i = 1, . . . , k.Mostraremos la complejidad de decidir si
spw(G) k en una gráfica G conexa y cómoconstruir una gráfica G⇤ tal que tenga paráme-tro spw(G⇤
) = k, entre algunas propiedades dedicho parámetro.
Nombre: Miklos RuszinkoInstitución: Rényi Institute of MathematicsCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: A modified bootstrappercolation on a random graph coupled with alatticeResumen: In this talk a random graph modelGZ2
N ,pdwill be introduced, which is a combina-
tion of fixed torus grid edges in (Z/NZ)2 andsome additional random ones. The random ed-ges are called long, and the probability of havinga long edge between vertices u, v 2 (Z/NZ)2with graph distance d on the torus grid is p
d
=
c/Nd, where c is some constant. We show that,whp, the diameter D(GZ2
N ,pd) = ⇥(logN). Mo-
reover, we consider a modified non-monotonousbootstrap percolation on GZ2
N ,pd. We prove the
presence of phase transitions in mean-field ap-proximation and provide fairly sharp bounds onthe error of the critical parameters.
Nombre: José Miguel Díaz-BáñezInstitución: Universidad de SevillaCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Algunos problemas dematemáticas para el análisis de la música fla-menca
Resumen: Los lazos entre matemáticas y músi-ca existen al menos desde que los antiguos grie-gos comenzaron a formalizar los aspectos mate-máticos de la música. En esta charla hablaremosde problemas de matemáticas que aparecen enel estudio de la música flamenca. Estas cuestio-nes pueden ser útiles para estudiar la naturalezade la música flamenca y proporcionan, a la vez,retos para la matemática combinatoria y algo-rítmica.
Martes
Nombre: Gabriela Araujo-PardoInstitución: UNAM-Instituto de MatemáticasCorreo: [email protected]
Nivel: PlenariaTítulo de la ponencia: Sobre como quedaratrapado en la jaula de la combinatoria en Mé-xicoResumen: El objetivo de esta charla es contar-les a los estudiantes y a la comunidad en generalcuales son la combinatoria y las matemáticasdiscretas que, según mi opinión, surgieron, si-guieron y se desarrollan en México a partir dela existencia del Coloquio Víctor Neumann-Larade Teoría de las Gráficas, Combinatoria y susAplicaciones en México, para después relacio-narlas con mi trabajo de investigación, dandoresultados y técnicas que utilizo en el mismo deuna manera sencilla y de divulgación.
Nombre: Christian Rubio MontielInstitución: UNAM-FES AcatlánCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: El 4-girth-thickness
de la gráfica multipartita completaResumen: El g-girth-thickness ✓(g,G) de unagráfica G es el número más pequeño de subgrá-ficas planas de cuello al menos g cuya unión esG. En esta charla explicaremos como obtenerel 4-girth-thickness ✓(4, G) de la gráfica multi-partita completa G, cuanto cada parte tiene unnúmero par de vértices.
Nombre: Fabio RodríguezInstitución: Universidad de La Habana-Facultad de Matemáticas y Ciencias de laComputaciónCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Algoritmos eficientespara la detección de colisiones en un sistema derobots con direcciones restringidas.Co-autores: L. E. Caraballo; J.M. Díaz-Báñez;Ruy Fabila; A. FernándezResumen: Estudiamos un problema de detec-ción de colisiones para un número dado n derobots que, partiendo de posiciones iniciales co-nocidas, pueden elegir entre k direcciones po-sibles. El objetivo fundamental es diseñar algo-ritmos que determinen si es posible asignar unadirección a cada robot evitando colisiones. Eneste escenario aparecen diversas variantes delproblema que dependen del concepto de coli-sión (un robot se modela por un punto o uncírculo) o velocidades (pueden ser distintas oiguales) de los robots.
Nombre: Mazay Oswaldo Jiménez SalinasInstitución: UNAM-IIMASCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Programación lineal
y problemas de corte en segmentos de línea ypuntos en movimientoCo-autores: Gerardo González Martínez, Car-los Seara, Jorge UrrutiaResumen: Sea P = {p1, . . . , pn} un conjun-to de n puntos en el plano. Supongamos queen el tiempo t = 0 comienzan a moverse en ladirección vertical a velocidad unitaria; es decir,si p
i
= (ai
, bi
), en el tiempo t, pi
se movió alpunto p
i
(t) = (ai
, bi
+ t). Sea lit
el segmentode línea cerrada con puntos finales p
i
y pi
(t),i = 1, . . . , n. En este trabajo abordamos el si-guiente problema: Encuentre el tiempo más pe-queño t tal que haya una línea ` que intersequea todos los segmentos de línea l1
t
, . . . , lnt
. Proba-mos que nuestro problema puede resolverse entiempo lineal. También mostramos que el mis-mo problema cuando los elementos de P sonpuntos en el espacio d-dimensional Rd que semueven hacia arriba y a diferentes velocidades,también se puede resolver en tiempo lineal paradimensión fija d.
Nombre: Marco Antonio Castillo RubiInstitución: Universidad Autónoma del Estadode MéxicoCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Segundo producto si-métrico de una gráfica finitaResumen: Sea X un espacio topológico y con-sideremos el espacio
2
X
= {A : A es un subconjunto cerradono vacío de X}
el cual está dotado con la topología de Vieto-ris. Si X es T1 y n � 1, entonces el n-ésimo
producto simétrico de X es Fn
(X) = {A 22
X
: |A| n}. Si G es una gráfica finita, lacaracterística de Euler �(G) es el número devértices menos el número de aristas de G. Porotro lado se sabe muy bien que F2(I) tiene elmismo tipo de homotopía que un punto (dondeI = [0, 1]), F2(S1
) (es homeomorfo a la bandade Moebius) tiene el mismo tipo de homotopíaque S1 (donde S1 es la circunferencia unitaria).En general, en esta charla, mostraremos el tipode homotopía de F2(G) donde G es una gráficafinitay discutiremos el siguiente resultadoTeorema Sea G una gráfica finita. Los gruposde homología de F2(G) con coeficientes en Zson
Hq
(F2(G);Z) =
8>>>><
>>>>:
Z si q = 0,
Z1��(G) si q = 1,
Z(1��(G)
2 ) si q = 2,
0 si q � 3.
Nombre: Carlos SearaInstitución: Universidad Politécnica de Cata-lunyaCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Antimagic labelingsof caterpillarsCo-autores: Antoni Lozano, Mercè MoraResumen: A k-antimagic labeling of a graph Gis an injection from E(G) to {1, 2, . . . , |E(G)|+k} such that all vertex sums are pairwise dis-tinct, where the vertex sum at vertex u is thesum of the labels assigned to edges incidentto u. We call a graph k-antimagic if it has ak-antimagic labeling, and antimagic if it is 0-antimagic. Hartsfield and Ringel [2] conjectured
that every simple connected graph other thanK2 is antimagic, but the conjecture is still openeven for trees. Here we study k-antimagic labe-lings of caterpillars, which are defined as treessuch that the removal of their leaves produces apath, called its spine. As a general result, we useconstructive techniques to prove that any cater-pillar of order n is (b(n� 1)/2c� 2)-antimagic.Furthermore, if C is a caterpillar with a spineof order s, we prove that when C has at leastb(3s + 1)/2c leaves or b(s � 1)/2c consecuti-ve vertices of degree at most 2 at one end ofa longest path, then C is antimagic. As a con-sequence of a result by Wong and Zhu [3], wealso prove that if p is a prime number, any ca-terpillar with a spine of order p, p� 1 or p� 2
is 1-antimagic.
[1] Joseph A. Gallian. Graph labeling. Elec-tron. J. Combin., 6:Dynamic Survey 6,415, 2017.
[2] Nora Hartsfield and Gerhard Ringel. Pearlsin graph theory. A comprehensive introduc-tion. Academic Press, Inc., Boston, MA,1994.
[3] Tsai-Lein Wong and Xuding Zhu. Antima-gic labelling of vertex weighted graphs. J.Graph Theory, 70(3):348–350, 2012.
Nombre: Gerandy BritoInstitución: Georgia Institute of TechnologyCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Spectral gap in ran-dom bipartite biregular graphs with applicationsCo-autores: Ioana Dumitriu, Kameron HarrisResumen: This talk concerns to spectral gap
of random regular graphs. First, we prove thatalmost all bipartite biregular graphs are almostRamanujan by providing a tight upper boundfor the non trivial eigenvalues of its adjacencyoperator, proving Alon’s Conjecture for this fa-mily of graphs. Also, we use a spectral algorithmto recover hidden communities in a random net-work model we call regular stochastic block mo-del. Our proofs rely on a technique introducedrecently by Massoullie, which we developed forrandom regular graphs.
Nombre: Alejandro Flores LamasInstitución: CICESECorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Algoritmo distribuidopara encontrar un conjunto 2-packing maximalen la gráfica HalinCo-autores: José Alberto Fernández Zepeda,Alejandro Flores Lamas, Joel Antonio TrejoSánchezResumen: En este trabajo discutimos el pro-blema bien conocido que consiste en encontrarun conjunto 2-packing maximal en una gráfi-ca Halin. Una gráfica Halin es una incrusta-ción plana de un árbol T , tal que |T | � 4,8v 2 T, deg(v) > 2, y un conjunto de aristasC que conecta todas las hojas de T en el or-den cíclico dado por la incrustación plana. SeaG = (V,E) una gráfica simple no dirigida, elsubconjunto S ✓ V es un conjunto 2-packing sipara cada par de vértices u, v 2 S el uv-caminomás corto tiene longitud al menos tres. El con-junto S es maximal si no existe otro conjuntoS 0 tal que S ⇢ S 0.
La solución al problema 2-packing tiene unaamplia gama de aplicaciones, tales como el es-
tudio de moléculas, modelado de redes y asig-nación de frecuencias. Asimismo, los algoritmosdistribuidos se aplican en áreas como telecomu-nicaciones, computo científico y procesamientodistribuido de información.
Hemos diseñado un algoritmo distribuido queidentifica una cara externa de la gráfica Haliny posteriormente calcula un conjunto 2-packingmaximal en O(n) rondas, donde n es el númerode vértices en la gráfica. Hasta donde tienenconocimiento los autores, no existe un algoritmodistribuido que cumpla este objetivo en tiempopolinomial.
Nombre: Mickel GonzálezCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Ley 0-1 para oracio-nes cortas monádicas de segundo orden
Miércoles
Nombre: Bernardo ÁbregoInstitución: California State University, North-ridgeCorreo: [email protected]
Nivel: PlenariaTítulo de la ponencia: Cruces en dibujos con-vexos de gráficasResumen: Un dibujo de una gráfica finita esconvexo si sus nodos se pueden representar co-mo los vértices de un polígono convexo y susaristas como diagonales del mismo.
En esta charla presentaremos varios resulta-dos acerca del mínimo número de cruces quepuede haber en un dibujo convexo. En particular
mostraremos una versión mejorada del llamado“crossing lemma” para dibujos convexos.
Nombre: Dolores Lara CuevasInstitución: CINVESTAVCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Thrackles y familiasde cruce en gráficas geométricas.Co-autores: Christian Rubio-MontielResumen: Una familia de cruce es una colec-ción de segmentos que se cruzan, en su inte-rior, dos a dos. Un thrackle es una colecciónde segmentos que se cruzan dos a dos, o bienque comparten extremos. En esta charla presen-taremos una generalización de la definición defamilia de cruce, y algunos resultados respectoa la búsqueda de las mismas y a la búsqueda dethrackles en conjuntos de puntos.
Nombre: María Elena Martínez CueroInstitución: Universidad AutónomaMetropolitana-IztapalapaCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: (1, 3)-árboles gene-radoresCo-autores: Eduardo Rivera CampoResumen: Un árbol generador T de unagráfica G es una subgráfica simple conexa deG que no contiene ciclos, donde el conjunto devértices de T es igual al conjunto de vérticesde G.
Un árbol generador T de G es un (1, 3)-árbolgenerador si d
T
(u) = 1 o dT
(u) = 3, para to-do vértice u de T . Esta definición nos conducea preguntarnos cuáles son las condiciones sufi-cientes que debe de tener G para asegurar que
tiene al menos un (1, 3)-árbol generador. En es-ta charla daremos a conocer algunos resultadosque aseguran que G tiene al menos (1, 3)-árbolgenerador.
Nombre: Isaac Arelio RíosInstitución: UNAM-Instituto de MatemáticasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Una aplicación de laTeoría de Gráficas al estudio de la red del cere-broCo-autores: Sarael Alcauter, Juan Carlos Díaz,Zeus GraciaResumen: El cerebro es una red con billones deneuronas que pueden interactuar a diferentes ni-veles de organización. En la actualidad la tecno-logía permite la exploración del cerebro humanoa través de regiones, conocidas como regionesde interés. Dichas regiones están constituidaspor conjuntos de neuronas con una función es-pecializada.
Una de las técnicas usuales para analizar lared del cerebro es la teoría de gráficas, la cualpermite describir y caracterizar la topología delas redes. El cerebro es modelado como una grá-fica constituida por un conjunto de regiones deinterés y la conectividad entre dichas regiones.No hay un parámetro general para definir lasconexiones de la red; recientemente se ha intro-ducido la homología persistente como una he-rramienta para analizar la evolución de la red através de distintos parámetros de conectividad.A partir de la gráfica asociada a la red es posibleconstruir complejos simpliciales, la cantidad deconexiones determina ciertas propiedades topo-lógicas que pueden permanecer o desaparecercon la evolución de la red.
En esta charla presentaremos una aplicaciónde las técnicas conocidas de la homología per-sistente en el análisis de la red cerebral de dis-tintos sujetos para comparar grupos de estudio.
Nombre: Luis Evaristo Caraballo de la CruzInstitución: Universidad de SevillaCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Particionando grafosusando árboles abarcadoresCo-autores: José Miguel Díaz-Báñez, NadineKroherResumen: Sea G un grafo conexo con una fun-ción de peso asociada a las aristas. Esta funciónde peso indica la similitud entre los nodos queune. Sea C una componente conexa de G. De-finimos la medida �(C) como la división entreel peso de la arista más pesada que conecta unnodo en C con otro fuera de C y el peso dela arista de menor peso en el árbol abarcadorde coste máximo en C. Note que a menor valorde esta función más parecidos son entre sí sonlos nodos de C y más distintos con los nodosque no están en C. Sea C = {C1, . . . , Ck
} unapartición de G en k componentes conexas. De-finimos �(C) = max�(C
i
) como una medidadde la partición C. Queremos encontrar la par-tición C⇤ formada por k componentes conexasque minimiza el valor de �(·). En esta char-la mostraremos las propiedades que tiene estapartición óptima y expondremos un algoritmopara computarla.
Nombre: Ruy Fabila MonroyInstitución: CINVESTAVCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Una cota superiorpara constante del número de cruce rectilíneo.Co-autores: Oswin Aichholzer, Frank Duque,Oscar García, Carlos Hidalgo-ToscanoResumen: El número de cruce rectilíneo deuna gráfica G es el mínimo número de crucescr(G) que aparecen al dibujar la gráfica en elplano, dibujando sus aristas con segmentos derectas. Se sabe que para la gráfica completa ellímite cuando n tiene a infinito de cr(K
n
)/�n
4
�
es una constante. Esta constante se conoce co-mo la constante del número de cruce rectilíneo.En esta charla hablaremos de las herramientascomputacionales usadas para obtener la mejorcota superior a la fecha.
Nombre: María de Luz Gasca SotoInstitución: UNAM-Facultad de CienciasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Difusión de la infor-mación y ruteo en vox-sólidosResumen: Un vox-sólido V es la unión finitade voxeles tal que 1. la intersección de voxeleses sólo por caras, aristas o vértices; y 2. la fron-tera de V es una superficie no singular. A ca-da vox-sólido V le asociamos una gráfica cuyosvértices corresponden a las caras en la fronterade V y las aristas indican la adyacencia entrelas caras de V . Ésta es llamada gráfica facialdel vox-sólido V , la cual resulta ser una gráfica4-regular, 4-conexa y, para diversas familias in-finitas de vox-sólidos, es Hamiltoniana y admiteuna descomposición Hamiltoniana.
En esta charla veremos a la gráfica facial deun vox-sólido como una red de interconexión,además presentaremos un algoritmo de difusión
de la información (broadcasting) y un algoritmode ruteo (routing) para la gráfica facial asociadaa ciertas familias de vox-sólidos.
Jueves
Nombre: Juan José Montellanos BallesterosInstitución: UNAM-Instituto de MatemáticasCorreo: [email protected]
Nivel: PlenariaTítulo de la ponencia: Estructuras en tor-neos multipartitos.Co-autores: Paulina Figueroa, Mika OlsenResumen: Dado un entero c � 1, un c-torneomultipartito es una orientación de una gráficacompleta c-partita. Dada un digráfica D, la irre-gularidad global de D se define como
ig
(D) = max
x,y2V (D){max{d+(x), d�(x)}�mın{d+(y), d�(y)}}.
Si ig
(D) = 0, entonces D es regular.En esta plática veremos algunas relaciones
entre la irregularidad global (y otro parámetrosparecidos) de un c-torneo multipartito y la exis-tencia de ciertas estructuras en dicho torneotales como ciclos, subtorneos fuertemente co-nexos o particiones en torneos fuertemente co-nexos.
Nombre: César Hernández VélezInstitución: Universidad Autónoma de SanLuis PotosíCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Polinomio de Ehrhartdel politopo de un matroide
Co-autores: Jorge Luis Ramírez AlfonsínResumen: Dado un politopo P , seaL(P , k) := # (kP \ Zn
) el número depuntos de coordenadas enteras en la k-ésimaexpansión de P . Es sabido que L(P , k) esun polinomio de grado d, la dimensión delpolitopo, con coeficientes racionales, el cual esllamado el polynomial de Ehrhart de P .
En esta charla hablaremos del polinomio deEhrhart del politopo de bases de un matroide.En especial de los matroides de látices de cami-nos.
Nombre: Germán Benítez BobadillaInstitución: UNAM-Instituto de MatemáticasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Patrones pancromá-ticos dinámicosCo-autores: Hortensia Galeana Sánchez, Cé-sar Hernández CruzResumen: Sea H una digráfica, posiblemen-te con lazos, y D una multidigráfica. Una H-coloración ⇣ de D es una función que asig-na a cada flecha de D un vértice de H.Una sucesión de vértices (x0, x1, . . . , xn
) enD es un H-camino dinámico de D si pa-ra cada i 2 {0, . . . , n � 2} existe f
i
2A
D
[xi
, xi+1] y f
i+1 2 AD
[xi+1, xi+2] tales que
(⇣(fi
), ⇣(fi+1)) 2 A(H). Un subconjunto K ✓
V (D) es un H-núcleo por caminos dinámicos deD si cumple que entre cualesquiera dos vérticesde K no existe un H-camino dinámico entreellos y para cualquier vértice fuera de K exis-te un H-camino dinámico hacia algún vérticede K. Un patrón pancromático por caminos di-námicos es una digráfica H tal que para todamultidigráfica D y toda H-coloración de D se
tiene que D tiene H-núcleo por caminos diná-micos.
En esta charla veremos que la existencia deun H-camino entre dos vértices no garantizala existencia de un H-camino dinámico entreesos vértices, y viceversa. Daremos ejemplos demultidigráficas con H-núcleo dinámico pero sinH-núcleo por caminos, y viceversa. Finalmente,caracterizaremos a todos patrones pancromáti-cos por caminos dinámicos.
Nombre: Briseida Guadalupe Trejo EscamillaInstitución: UNAM-Instituto de MatemáticasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Panales quiralesCo-autores: Isabel A. Hubard EscaleraResumen: Describimos panales (“politopos”) ysus grupos de simetrías en el espacio euclidianoy esférico.
Casos más interesantes surgen cuando cons-truimos panales del tipo {p, q, r} e identifica-mos vértices en t pasos a lo largo de sus polí-gonos de Petrie derechos, pues resulta que nohay simetrías por reflexión.
Nombre: Eric Paulí Pérez ContrerasInstitución: UNAM-Instituto de MatemáticasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Gráficas autodualesen el espacioCo-autores: Luis Montejano PeimbertResumen: Un concepto que resulta interesan-te en varios contextos de las matemáticas es ladualidad. En los sólidos platónicos, por ejemplo,el cubo es dual del octaedro, el dodedcaedro tie-ne por dual al icosaedro y el tetraedro es dual
a sí mismo, es decir, es autodual. Existe unagran variedad de poliedros autoduales y resultadestacable que sus simetrías se relacionan estre-chamente con sus dualidades, es decir, el grupode automorfismos de la gráfica guarda una bo-nita relación con el conjunto de isomorfismosde dualidad entre la gráfica y su dual. La geo-metría de estos poliedros resulta ser una puertamisteriosa hacia la construcción de cuerpos deancho constante, que son objetos geométricosque comparten una propiedad con la esfera: tie-nen el mismo ancho en cualquier dirección.
Nombre: Mika OlsenInstitución: Universidad AutónomaMetropolitana-CuajimalpaCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Coloraciones acíclicasen digráficasCo-autores: Gabriela Araujo-Pardo, JuanJosé Montellano-Ballesteros y Christian RubioMontielResumen: Una coloración de los vértices deuna gráfica es propia y completa si cada clasecromática es independiente y para cualquierpara de colores i, j hay una arista cuyosvértices terminales tienen colores i y j. Elnúmero cromático y el número acromático es elmínimo y el máximo número, respectivamente,de colores de una coloración propia y completa.
Hay diversas generalizaciones del número cro-mático para digráficas y dos generalizaciones delnúmero acromático para digráficas, aunque hayresultados claásicos del número acromático queno se extienden a estas dos generalizaciones.
En esta charla presentamos otra generaliza-ción del número acromático en digráficas, en
términos de coloraciones acíclicas. Una colora-ción es acíclica y completa si cada clase cromá-tica es acíclica y para cualquier pareja ordenadade colores (i, j) hay una flecha cuyo vértice ini-cial tiene color i y el vértice terminal tiene colorj. El número dicromático (definido por VíctorNeumann-Lara) y el número diacromático (defi-nido por Araujo-Pardo, Montellano-Ballesteros,Olsen y Rubio) es el mínimo y el máximo núme-ro, respectivamente, de colores de una colora-ción acíclica y completa. Extendemos resultadosclásicos del número acromático para el númerodiacromático, entre ellos el Teorema de la Inter-polación, el cual las otras dos generalizacionesno satisfacen.
Nombre: Edgardo Roldán PensadoInstitución: UNAM-Centro de Ciencias Mate-máticasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Un teorema tipo Hellypara simetría centralCo-autores: Alexey GarberResumen: Estudiamos un problema de KonradSwanepoel relacionado con el Teorema de Ca-rathéodory. Si X es un conjunto de puntos ta-les que cualquier subconjunto con k elementosestá en posición centralmente simétrica y con-vexa, ¿es cierto que X debe estar en posicióncentralmente simétrica y convexa?
Nombre: Silvia Fernández-MerchantInstitución: California State University, North-ridgeCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Crossings on k-circle
drawings of complete graphsCo-autores: Bernardo M. Abrego, CharlesCamacho, Marija Jelic, Rachel Kirsch, LindaKleist, Elizabeth Bailey Matson, Athena Sparks,Jennifer WhiteResumen: We consider k-circle drawings ofgraphs in the plane (k � 1). In a k-circle dra-wing of a graph G, the vertices of G are pla-ced on k disjoint circles C1, · · · , Ck
and theedges of G do not cross the circles. If G is ak-partite graph (k � 2) with k-partition of thevertices V1, · · · , Vk
, a k-partite-circle drawingof G is a k-circle drawing of G with the addi-tional condition that V
i
is placed on Ci
. Thek-(partite-)circle crossing number of G is theminimum number of crossings in a k-(partite-)circle drawing of G. In this context, 1-circlecrossing numbers are equivalent to 2-page-bookcrossing numbers; while 2-circle and 2-partite-circle crossing numbers are equivalent to cy-lindrical and bipartite-cylindrical crossing num-bers, respectively. The focus of this talk is on2-circle and 3-circle crossing numbers of com-plete, complete bipartite, and complete triparti-te graphs. We include several exact results andthe best known bounds for these crossing num-bers as well as their relationship to the famousHarary-Hill Conjecture.
Nombre: Elías MochánInstitución: UNAM-Instituto de MatemáticasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Todo dije el antipris-ma cuadrangularCo-autores: Isabel HubardResumen: Usaremos al antiprisma cuadrangu-lar como ejemplo para estudiar conceptos tales
como la gráfica de banderas y la gráfica de tipode simetría de un poliedro. Veremos qué infor-mación nos dan estas gráficas sobre el poliedro.Veremos cómo recuperar un poliedro a partir desu gráfica de banderas y también cómo recupe-rarlo a partir de su gradúa de tipo de simetríausando su grupo de simetrías.
Nombre: Loiret Alejandría Dosal TrujilloInstitución: UNAM - Instituto de Matemáti-casCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Contando conjuntosindependientes en gráficas vértice-transitivasCo-autores: Hortensia Galeana SánchezResumen: Decimos que un subconjunto devértices de una gráfica G es un conjunto inde-pendiente, si entre cualesquiera dos vértices delconjunto no existe una arista entre ellos. Al nú-mero total de conjuntos independientes de unagráfica G se le conoce, en el contexto de la Teo-ría de Gráficas, como el número de Fibonacci deG. En general, determinar este parámetro es degran complejidad. Decimos que una gráfica Ges vértice-transitiva, si la acción del grupo deautomorfismos de G actúa transitivamente so-bre su conjunto de vértices. En esta charla ha-blaremos de cómo este problema de conteo sepuede simplificar en algunas familias de gráficasvértice-transitivas.
Nombre: Joel Antonio Trejo-SánchezInstitución: CIMATCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Algoritmos auto-estabilizantes para el problema del conjunto in-
dependiente fuerte en gráficas tipo cactusCo-autores: José Alberto Fernández-ZepedaResumen: Un sistema auto-estabilizante esaquel sistema en el que, independientemente desu configuración inicial, se garantiza que con-verge a una configuración estable en un nú-mero finito de pasos. Diseñar algoritmos auto-estabilizantes es mucho más complejo que di-señar algoritmos no auto-estabilizantes. En elcaso de los algoritmos auto-estabilizantes, elnúmero de posibles estados iniciales del siste-ma es muy grande, mientras que en los algo-ritmos no auto-estabilizantes se puede suponeruna configuración inicial idónea en la cual lasvariables están inicializadas. En los algoritmosauto-estabilizantes un calendarizador define elorden de ejecución de dicho algoritmo. El calen-darizador síncrono es el más simple de los calen-darizadores y el calendarizador adversario es elmás complejo. Un algoritmo auto-estabilizanteque funciona bajo la suposición del calendariza-dor síncrono, no necesariamente funciona con elcalendarizador adversario.
Dada una gráfica G = (V,E), un subconjun-to S ✓ V es un conjunto independiente fuerte,si dados un par de vértices de S, la distancia en-tre dichos vértices es de al menos tres aristas.Un conjunto independiente fuerte S es maximal,si no existe un conjunto independiente fuerte S 0
tal que S ⇢ S 0. Una gráfica tipo cactus, es unagráfica plana en la que cada arista pertenece alo más a un ciclo.
En esta charla se presentan dos algoritmosauto-estabilizantes que encuentran un conjun-to independiente fuerte maximal en una gráficatipo cactus. El primer algoritmo funciona ba-jo la suposición del calendarizador síncrono yel segundo algoritmo también funciona con el
calendarizador adversario.
Nombre: Gyula KarolyiInstitución: Renyi Institute and Eotvos Univer-sity, BudapestCorreo: karolyi <[email protected]
Nivel: InvestigaciónTítulo de la ponencia: On the Ramsey mul-tiplicity of odd cyclesResumen: The Ramsey number R(G) of agraph G is the smallest positive integer n suchthat in any 2-coloring of the edges of the com-plete graph on n vertices there is a monochro-maic copy of the graph G. For a cycle of lengthk > 3, k odd, the Ramsey number is known tobe 2k � 1.
Any coloring of the complete graph on R(G)
vertices usually contains many monochromaticcopies of G. Here we prove that in the casewhen G is a cycle of length k (k odd), thisnumber is superexponentially large in k.
Viernes
Nombre: Pablo Pérez LanteroInstitución: Universidad de Santiago de ChileCorreo: [email protected]
Nivel: PlenariaTítulo de la ponencia: Grafo de intersecciónde círculos en polígonos convexosResumen: Dado un polígono convexo de n la-dos podemos dibujar n círculos (llamados círcu-los de los lados) donde cada círculo tiene comodiámetro un lado del polígono. El grafo de inter-sección de los círculos de los lados del polígonoes el grafo no dirigido cuyos vértices son los n
círculos, y dos círculos son adyacentes si y sólosi tienen un punto en común.
En esta charla presentaremos varias propieda-des combinatoriales de este grafo. Primeramen-te demostraremos que para todo polígono con-vexo el grafo de intersección de los círculos esplano y hamiltoniano. Posteriormente probare-mos que el treewidth es a lo más tres, mostran-do un algoritmo de tiempo O(n) que construyeuna descomposición de ancho a lo más tres; da-do el polígono como entrada. Esto implica quepodemos construir el grafo de intersección delos círculos en tiempo O(n). También estudia-remos el número de círculos independientes deeste grafo que es la cantidad máxima de círcu-los ajenos dos a dos del polígono. La condiciónde que este grafo es plano implica que podemosseleccionar por lo menos n/4 círculos ajenos dosa dos, y para n � 3 demostraremos que existenpolígonos convexos donde no podemos seleccio-nar más de este número. Finalmente, probare-mos que los grafos outerplanares y hamiltonia-nos, excepto el ciclo de longitud cuatro, estáncontenidos en el conjunto de los grafos de in-tersección de círculos en polígonos convexos, yestos últimos están contenidos en el conjuntode los grafos planos y hamiltonianos.
Nombre: María del Rocío Sánchez LópezInstitución: UNAM-Facultad de CienciasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Una caracterizaciónde las digráficas infinitas núcleo perfectasResumen: Sean D una digráfica, posiblementeinfinita, y N un subconjunto de V (D). Diremosque N es un núcleo de D si N es un conjun-to independiente y un conjunto absorbente. Se
dice que una digráfica infinita es finita núcleoimperfecta crítica si ella no tiene núcleo perotodas sus subdigráficas inducidas finitas si tie-nen núcleo. En esta charla veremos como se ca-racterizan las digráficas infinitas que son núcleoperfectas por medio de digráficas infinitas queson finitas núcleo imperfectas críticas y las com-ponentes fuermente conexas de su parte asimé-trica.
Nombre: Julián Alberto Fresán FigueroaInstitución: Universidad AutónomaMetropolitana-IztapalapaCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: El número cromáticode empaquetamiento de algunas jaulasCo-autores: Diego González Moreno, MikaOlsenResumen: El número cromático de empaque-tamiento �
p
(G) de una gráfica G es el enteromás pequeño k para el cual existe una colora-ción de vértices � : V (G) ! {1, 2, . . . , k} talque cualesquiera dos vértices de color i estána distancia al menos i + 1. Una (k; g)-jaulaes una gráfica k-regular con cuello g. En estacharla presentaré unos resultados acerca delnúmero cromático de empaquetamiento paralas jaulas de cuello seis y ocho.
Nombre: Narda Cordero MichelInstitución: UNAM-Instituto de MatemáticasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Sobre la existencia deciclos alternantes en la suma generalizada colo-reada de gráficas 2-coloreadas en aristasCo-autores: Hortensia Galeana Sánchez
Resumen: El estudio de paseos alternantes engráficas coloreadas en aristas es muy interesan-te, no sólo por ser bonito para quien lo estu-dia sino también por tener aplicaciones en otrasáreas. Además, el problema de determinar si unagráfica 2-coloreada en aristas tiene un ciclo ha-miltoniano alternante es NP-completo, por loque también es un reto encontrar soluciones“parciales” a dicho problema, es decir, dar con-diciones de suficiencia para garantizar la exis-tencia de estos ciclos.
En [1], los autores estudiaron este proble-ma para las gráficas bipartitas 2-coloreadas enaristas y para las multigráficas completas 2-coloreadas en aristas, a partir de subgráficasgeneradoras compuestas por una colección deciclos alternantes ajenos.
En esta charla hablaremos sobre la operaciónde suma generalizada coloreada de gráficas 2-coloreadas en aristas que introdujimos en [2] ydaremos algunas condiciones para garantizar laexistencia de ciclos hamiltonianos alternantes ociclos alternantes de una gama de longitudesen la suma generalizada coloreada de gráficasque contienen un ciclo hamiltoniano alternante,lo cual nos encaminará hacia el estudio de lassumas que resulten ser alternantemente pancí-clicas.
[1] Jørgen Bang-Jensen and Gregory Gutin.Digraphs. Theory, algorithms and applica-tions. Springer Monographs in Mathema-tics. Springer-Verlag London, Ltd., Lon-don, second edition, 2009.
[2] Narda Cordero-Michel and H. Galeana-Sánchez, Some results on the existenceof Hamiltonian alternating cycles in the
colored generalized sum of 2-edge-coloredgraphs. Submitted.
Nombre: Fernando Esteban Contreras Men-dozaInstitución: UNAM - Facultad de CienciasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Caracterizandocográficas polares mediante subgráficas prohi-bidas.Co-autores: F. Esteban Contreras-Mendoza,César Hernández-CruzResumen: Se dice que una gráfica es (s, k)-polar si existe una partición {A,B} de suconjunto de vértices de modo que A induzcauna gráfica s-partita completa y B induzcala unión ajena de a lo más k clanes. La clasede las gráficas polares no ha sido estudiadaa profundidad y no se conoce ninguna buenacaracterización para ella. Más aún, decidir siuna gráfica es una gráfica polar es un problemaNP-completo.
Por otra parte se han definido las cográficas,que son gráficas sin trayectorias de cuatro vér-tices como subgráficas inducidas. Las cográfi-cas pueden ser reconocidas en tiempo lineal yposeen muchas útiles caracterizaciones, así co-mo una descomposición estructural que permi-te la resolución algorítmica eficiente de diversosproblemas que en casos más generales resultande gran complejidad. Esta familia de gráficases una generalización de las gráficas bipartitascompletas y es a su vez una subfamilia de lasllamadas gráficas perfectas.
En este trabajo consideramos a las cográficas(s, 1)-polares, para las cuales damos una carac-terización en términos de una familia finita de
subgráficas prohibidas.
Nombre: Diego Antonio González MorenoInstitución: Universidad AutónomaMetropolitana-CuajimalpaCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: Una cota superior yla pareja de cuellos de una (k; g)-jaulaCo-autores: J. J. Montellano, C. BalbuenaResumen: Una (k; g)-jaula es una gráficak-regular, con cuello g y el menor númeroposible de vértices. En esta charla presenta-mos una cota superior para el orden de una(k; g + 1)-jaula en términos del orden de una(k; g)-jaula, donde k � 2 y g � 5 es unentero impar. También mostraremos que sik � 6, entonces toda (k; 11)-jaula contieneun ciclo de longitud 12, lo cual prueba uncaso particular de una conjetura propuesta porHarary y Kovács en 1983.
Nombre: Ricardo StrauszInstitución: UNAM-Instituto de MatemáticasCorreo: [email protected]
Nivel: InvestigaciónTítulo de la ponencia: De la gráfica de co-circuitos a la MacPhersonianaResumen: Exhibiremos una nueva metodologíapara estudiar el tipo de homotopía de la MacP-hersoniana usando la clasificación de la gráficade cocircuitos de los matroides orientados queencontraron Montellano-Ballesteros, Kolja y S.
Sesión de pósters
Nombre: Luis Enrique Adame MartínezInstitución: Universidad Autónoma de Zacate-casCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Hamiltonicidad en al-gunas gráficas de fichasCo-autores: Luis Manuel Rivera Martínez; Jo-sé Manuel Gómez SotoResumen: Dada una gráfica G y un enterok 2 {1, 2, . . . , n � 1}, se define la gráfica dek-fichas de G, denotada por F
k
(G) o G(k), co-mo la gráfica donde sus vértices son todos losk-conjuntos de V (G), y dos vértices A y B deG(k) son adyacentes si existen a 2 A y b 2 Btales que A�B = {a, b} 2 E(G).Las gráficas de fichas se han redefinido variasveces. Aparecen al menos desde 1988, en unatesis de Johns. Posteriormente en 1991, YousefAlavi junto con otros coautores las definen co-mo double vertex graphs (que es lo mismo quelas gráficas de 2-fichas). Luego en 2002, pero demanera independiente, Terry Rudolph, las defi-nió como la 2-potencia simétrica de una gráfi-ca y más delante, en 2007, Koenraad Audenaerjunto con otros autores extendieron el conceptopara k-potencia simétrica de una gráfica dondek 2 {1, 2, . . . , n� 1} y n es el número de vér-tices de la gráfica.Posteriormente, en 2012, Ruy Fabila junto conotros coautores reintrodujeron el concepto degráfica de k-fichas como un modelo en el quek fichas indistinguibles y situadas sobre los vér-tices de una gráfica G, que se mueven de unvértice a otro a través de las aristas de G.En esta charla se presentará un breve panorama
sobre las gráficas de fichas, así como algunosresultados recientes sobre la hamiltonicidad.
Nombre: Flor de María Aguilar CamposInstitución: UNAM-Instituto de MatemáticasCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Triangulaciones míni-masResumen: Se pretende demostrar algunos teo-remas importantes a cerca de triangulaciones desuperficies con frontera y sin frontera mediantegráficas mixtas.
Nombre: Alma Arévalo LoyolaInstitución: UNAM-Facultad de CienciasCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Matrices de Ericksony algunas variantesCo-autores: Amanda MontejanoResumen: Dada una matriz A, llamaremos un2-cuadrado a las cuatro esquinas de una sub-matriz cuadrada de A. Una matriz de Erick-son es una matriz binaria que no contiene 2-cuadrados constantes. En 1996, Martin J. Erick-son propuso el problema de encontrar el mínimoentero, n0, tal que si n � n0, entonces no existeuna matriz de Erickson de n⇥n. Dicho proble-ma se puede replantear de la siguiente manera:sea [n]2 el tablero de n ⇥ n casillas, determineel mínimo entero, n0, tal que toda bicoloración,f : [n]2 ! {A,R} produce un 2-cuadrado mo-nocromático. En 2008, M. Axenovich y J. Mans-ke [1] proporcionaron una cota superior paran0, utilizando el número de Van der Waerden,w(2, 8), correspondiente a la existencia de pro-gresiones aritméticas de longitud 8 en toda 2-
coloración del intervalo inicial de números ente-ros. Dicha cota, de orden 2
240 , era la mejor quese conocía hasta 2010, cuando R. Bacher y S.Eliahou [2] demostraron que n0 = 15, utilizan-do herramientas computacionales. El problemade las matrices de Erickson se considera dentrode la Teoría de Ramsey, la cual se encarga de es-tudiar la existencia de estructuras monocromá-ticas en universos coloreados. En analogía conla Teoría de Ramsey, se encuentran la Teoríaanti-Ramsey y la Teoría de Ramsey balancea-da que se ocupan de estudiar, respectivamente,la existencia de estructuras hererocromáticas ode estructuras balanceadas, en universos colo-reados. El objetivo de esta charla es presentarlos resultados antes mencionados, así como susvariantes en la Teoría anti-Ramsey y en la Teo-ría de Ramsey balanceada, mostrando diferen-tes comportamientos en cada caso.
[1] Maria Axenovich and Jacob Manske. Onmonochromatic subsets of a rectanguladrgrid. Integers, 8:A21, 14, 2008.
[2] Ronald Bacher and Shalom Eliahou. Ex-tremal binary matrices without constant 2-squares. J. Comb.,1(1):77–100, 2010.
Nombre: Ricardo Becerril SerranoInstitución: Universidad Autónoma del Estadode MéxicoCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Rompecabezas y norompecabezas en una gráficaCo-autores: Enrique Casas BautistaResumen: Sea G una gráfica conexa con nú-mero cromático �(G) y sea P una partición deV (G).
En esta charla nos referimos por coloraciónde vértices como la mínima asignación de co-lores de vértices de G usando los números1, . . . ,�(G), de tal manera que vértices adya-centes tienen distinto color. Por otro lado, par-tición significa una partición P = {P1, P2, . . .}de V (G) de tal manera que G[P
i
] es una grá-fica conexa. Los elementos de la partición sonllamados piezas.P es una soluci’on sobre G si hay exactamen-
te una coloración sobre V (G) con la propiedadde que las sumas de las etiquetas de los vérticesde cada pieza sean todas iguales. Un rompeca-bezas sobre G es una partición que es soluciónsobre G.P es una no-solución sobre G si hay exacta-
mente una coloración sobre V (G) con la pro-piedad de que las sumas de las etiquetas de losvértices de cada pieza sean todas diferentes. Unno-rompecabezas sobre G es una partición quees no solución sobre G.
Se presentaran ejemplos de gráficas que con-tienen rompecabezas, ejemplos de gráficas quecontienen no-rompecabezas y ejemplos de grá-ficas en donde podemos encontrar un rompeca-bezas y un no-rompecabezas.
Nombre: Héctor Castañeda LópezInstitución: Universidad Autónoma del Estadode MéxicoCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Propiedades de la di-gráfica excéntricaCo-autores: María del Rocío Rojas MonroyResumen: Sea G = (V (G), A(G)) una gráfi-ca. La distancia de un vértice u a otro vérticev, denotada por d(u, v), es la longitud de la
uv-trayectoria más corta en G. La excentrici-dad de un vértice u es la distancia máxima deu a cualquier otro vértice en G y es denotadapor e(u). Un vértice v es un vértice excéntricode u si d(u, v) = e(u). La digráfica excéntricaDE(G) de una gráfica G es una digráfica conel mismo conjunto de vértices y habrá una fle-cha de un vértice u a otro vértice v si v es unvértice excéntrico de u. En el presente trabajose expondrán las principales propiedades que sehan investigado de dicha digráfica.
Nombre: Alma Gabriela Desentis MartínezInstitución: UNAM-Facultad de CienciasCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Análisis de red tróficade la Reserva Ecológica del Pedregal San ÁngelResumen: Realizaremos la red trófica de la Re-serva Ecológica del Pedregal San Ángel y hare-mos un análisis de la misma para determinar quéanimal o animales son esenciales para el ecosis-tema. Con esta información podremos hacer elsupuesto de ver cómo se vería afectada la redsi alguna de esas especies faltara.
Nombre: Bernardo Fregoso GarduñoInstitución: UNAM-Facultad de CienciasCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Digráficas con ciclosimpares núcleo-perfectasResumen: Explicaremos, de una manera másclara, porqué las digráficas, que en todos susciclos impares tienen dos flechas tales quepertencen a un 2-ciclo, son núcleo-perfectas(recordando que los ciclos impares no sonnúcleo-perfectas).
Nombre: Alejandra Iveth Garcá PérezInstitución: Instituto Politécnico NacionalCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Fundamentos demuestreo aleatorio. Cómputo de permutacionesy combinaciones.Co-autores: Adrián Alcántar TorresResumen: En la vida cotidiana estamos cons-tantemente sometidos a la toma de decisionesque nos conducen a establecer preferencias conbase en antiguas experiencias. De esta mane-ra, bastaría visitar pocas veces un restaurante,seleccionar una aerolínea, los servicios de unacompañía de telecomunicaciones o bien una ca-fetería, para emitir un juicio y decidir si ha sidode nuestro agrado o no.
Cuando se presente la tarea de evaluar par-ticularmente, por ejemplo, restaurantes de co-mida italiana en determinada ciudad, se deberáhacer una selección y posteriormente la evalua-ción. Al hecho de realizar estas selecciones sele conoce como muestreo. Dado que la partedonde se lleva a cabo la selección es clave, de-be diseñarse algún procedimiento que sea justo,equitativo y computacionalmente abordable.
En mi trabajo de tesis se presentan los fun-damentos del muestreo aleatorio, así como lafuerte relación de este con la combinatoria. Sehace un análisis profundo del muestro aleato-rio simple y su fuerte relación con el cómputode permutaciones y combinaciones, los cuales asu vez son un tema que merecen mucha impor-tancia y cuya complejidad matemática es muyelegante.
Nombre: Rangel Hernández OrtizInstitución: Universidad Autónoma
Metropolitana-CuajimalpaCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: El polinomio dicro-máticoCo-autores: Diego González-MorenoResumen: Una k-coloración de una digráficaD es una partición del conjunto de vérticesV (D) en k conjuntos acíclicos. Al mínimoentero k para el cual existe una k-coloraciónde D se le conoce como el número dicromáticode la digráfica D. El número dicromático deuna digráfica D es denotado por �
d
(D).Dada una digráfica D y un conjunto de �
colores, se define la función P (D,�) como elnúmero de formas distintas de colorear D utili-zando los � colores. P (D,�) es conocido comoel polinomio dicromático de D. El polinomio di-cromático es un concepto relativamente recien-te del cual se conocen muy pocos resultados,por lo que el primer objetivo de este póster espresentar dichos resultados. El segundo, y prin-cipal objetivo, es presentar una fórmula recur-siva para calcular el polinomio dicromático deuna digráfica D, así como una conjetura sobrelas propiedades que satisface tal polinomio.
Nombre: Erick David Luna NúñezInstitución: Universidad Autónoma de Aguas-calientesCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Aplicaciones de lacombinatoria en geometria algebraicaResumen: En este trabajo se quiere mostrar unárea de la geometría algebraica, llamada geome-tría tórica, la cual usa en gran medida las herra-mientas de la combinatoria, y se quiere expresar
la utilidad de ésta en teoremas importantes parala geometráa algebraica, reduciéndolos, en estecaso, a resultados combinatorios sencillos.
Nombre: Guadalupe Macías Hernández yRicardo Andrés Maass GonzálezInstitución: Universidad AutónomaMetropolitana-CuajimalpaCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Descubriendo arcoírisen algunas gráficasCo-autores: Diego González Moreno, MikaOlsenResumen: Buscamos la conexidad arcoíris endistintas gráficas. Una gráfica G es conexa portrayectorias arcoíris si entre cualquier par devértices u y v existe una uv-trayectoria tal quesus aristas tienen colores diferentes, es decir,que la trayectoria no repita colores. En estepóster presentaremos distintos resultados de laconexidad arcoíris para algunas familias de grá-ficas, en particular, las gráficas generalizadasde Petersen y los 2-árboles.
Nombre: Natalia Martínez de la ViñaInstitución: UNAM-Facultad de CienciasCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Los números de Fi-bonacci por trayectorias monocromáticas de lasgráficas arista-coloreadasResumen: Dada una m-arista-coloración deuna gráfica G, decimos que un conjunto S ✓V (G) es independiente por trayectorias mono-crométicas, si entre cualesquiera dos vérticesx, y 2 S no existe una xy-trayectoria en G cu-
yas aristas sean del mismo color. En 2007, IwonaWłoch y Andrzej Włoch definieron el número deFibonacci por trayectorias monocromáticas engráficas arista-coloreadas, como el número to-tal de conjuntos independientes por trayectoriasmonocromáticas de la gráfica.
En este póster, hablaremos sobre los núme-ros de Fibonacci por trayectorias monocromá-ticas de ciertas familias de gráficas y veremoscomo estos números generalizan a los númerosde Fibonacci de las gráficas definidos por Hel-mut Prodinger y Robert F. Tichy en 1982.
Nombre: Francisco Páez PérezInstitución: UNAM-Facultad de CienciasCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Sobre el índice de Ho-soya y de Merrifield-Simmons en gráficas conconexidad a lo más kResumen: Para una gráfica G el índice deHosoya, denotado por z(G), y el índice deMerrifield-Simmos, denotado por i(G) (tambiénllamados índices topológicos en el contexto dequímica combinatoria), representan el númerototal de apareamientos y de conjuntos indepen-dientes en G, respectivamente. El índice de Ho-soya está relacionado de manera directa con laestructura de algunos compuestos orgánicos ysus propiedades termodinámicas, tales como elpunto de ebullición, la entropía y el calor deevaporación. El índice de Merrifiel-Simmons es-tá relacionado de manera directa con el puntode ebullición de los compuestos orgánicos, comolos hidrocarburos, y, en particular, de los alca-nos. Sean V
n,k
el conjunto de las gráficas cone-xas de orden n con conexidad puntual a lo másk n� 1, y A
n,k
el conjunto de todas las grá-
ficas conexas de orden n con conexidad lineal alo más k n�1. En este póster hablaremos deestas familias de gr’aficas, con particular interésen aquellas gráficas cuyos índices de Hosoya yde Merrifield-Simmons dan las cotas máximas omínimas para dichos conjuntos.
Nombre: Sheila Keren Palacios AlvaradoInstitución: UNAM-Facultad de CienciasCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Algunos productos degráficas y su relación con la probabilidad no con-mutativa.DCo-autores: Francisco Javier Torres AyalaResumen: Los operadores de adyacencia aso-ciados a algunos productos de gráficas se pue-den descomponer como un producto tensorialentre los operadores de adyacencia corrrespon-dientes a las gráficas “factor”. La naturalezade estas descomposiciones guarda una relaciónmuy estrecha con varias de las nociones de in-dependencia empleadas en la probabilidad noconmutativa. Abordaremos esta relación.
Nombre: Viviana MárquezInstitución: Konrad Lorenz Fundación Univer-sitariaCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Composiciones de ncon partes menores o iguales a kCo-autores: John A. ArredondoResumen: Sea n un entero positivo. Unacomposición de n es una dupla organizada deenteros positivos cuya suma es n. Por ejemplo,todas las composiciones posibles de 3 son(1, 1, 1), (2, 1), (1, 2), (3). Sea C(k)
n
el número
de composiciones de n que sólo involucrennúmeros menores o iguales a k. En este trabajopresentaremos una fórmula no-recursiva parahallar C(k)
n
, para n 2k + 1, la cual es máseficiente que la fórmula recursiva previamenteconocida.
Nombre: Montserrat Sancho CertuchaInstitución: UNAM - Facultad de CienciasCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Caracterización de Di-gráficas Bi-TransitivasResumen: Introduciremos una nueva fami-lia de digráficas, las cuales son digráficas bi-coloreadas por flechas de tal forma que, si exis-te una trayectoria monocromática de longitud 2,entonces existe una flecha del inicio de la tra-yectoria al final de la trayectoria del otro color, ylas llamaremos digráficas bi-transitivas. Logra-mos dar una caracterización de las digráficasbi-transitivas con al menos una clase de colorfuertemente conexa.
Nombre: Alejandra Silva RamírezInstitución: Universidad AutónomaMetropolitana-CuajimalpaCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Resultados delnúmero diacromàticoCo-autores: Dra. Mika OlsenResumen: El número acromático es unavariante del número cromático, y se ha buscadogeneralizar para las digráficas, pero los resulta-dos clásicos del número acromático en gráficasno son extendibles a ninguno de ellos. Recien-temente, la Dra. Olsen en conjunto con colegas
de la UNAM definieron otra generalización,llamada número diacromático, basada en elnúmero dicromático y extendieron los resulta-dos clásicos del número acromático en gráficasa resultados para el número diacromático. Porlo que en este poster se pretende presentar losresultados que hasta hoy se conocen y los querecientemente se están intentando.
Nombre: Claudia Silva RuizInstitución: UNAM - Facultad de CienciasCorreo: [email protected]
Título de la ponencia: El 6-girth-thicknessde la gráfica completaCo-autores: Héctor Castañeda-López, PabloC. Palomino, Andrea B. Ramos-Tort, ChristianRubio-MontielResumen: El g-girth-thickness ✓(g,G) de unagráfica G es el menor número de gráficas planasde cuello al menos g cuya unión es G. Determi-namos el 6-girth-thickness ✓(6, K
n
) de la gráfi-ca completa K
n
en la mayor parte de los casos.También, calculamos por computadora el valorfaltante de ✓(4, K
n
).
Nombre: Denae Ventura ArredondoInstitución: UNAM - Facultad de CienciasCorreo: [email protected]
Nivel: PósterTítulo de la ponencia: Coloraciones del hi-percuboCo-autores: Amanda Montejano CantoralResumen: El hipercubo de dimensión n, Q
n
,es la gráfica cuyos vértices son las n-tuplas bi-narias, y dos vértices son adyacentes si sus co-rrespondientes n-tuplas difieren en exactamenteuna posición.
En este póster veremos el parámetro
f(Qn
, Qk
) de tipo anti-Ramsey, definido porMaria Axenovich et al., que es el máximo núme-ro k de colores tal que existe una k-coloraciónde las aristas de Q
n
libre de Qk
’s heterocromá-ticos donde k < n, así como cotas inferior ysuperior del parámetro.
del 4 al 9 de marzo de 2018Universidad de La Habana, Cuba
XXXIII COLOQUIO VÍCTOR NEUMANN-LARADE TEORÍA DE LAS GRÁFICAS, COMBINATORIA Y SUS APLICACIONES
ProgramaHora
8:45 - 9:15
Lunes
Inauguración
Martes Miércoles Jueves Viernes
9:30 - 10:20 Alfredo Somoza Bernardo Ábrego Pablo Pérez LanteroGabriela AraujoPardo
Juancho MontellanoBallesteros
10:35 - 11:00 Miguel Raggi Dolores Lara Rocío SánchezChristian Rubio César Hernández
11:00 - 11:20 José Montero María Martínez Julian FresánFabio Rodríguez Germán Benitez
11:20 - 11:40 Ismael Robles Isaac Arelio Narda CorderoMazay Jiménez Briseida Trejo
12:10 - 12:30 Antonio Torres Luis Caraballo Fernando ContrerasMarco Castillo Eric Pérez
16:00 - 16:25 Miguel Pizaña Carlos Seara Silvia Fernández
16:25 - 16:45 Citlali Zamora Gerando Brity Jaime Mochán
16:45 - 17:05 Claudia De la Cruz Alejandro Flores Janna Dosal
17:25 - 17:50 Miklós Ruszinko Joel Trejo
17:50 - 18:15 José Miguel Díaz Gyula Karolyi
12:30 - 12:55 Paulina Figueroa Ruy Fabila Diego GonzálezSesiónde
Pósters
Sesiónde
problemas
Mika Olsen
12:55 - 13:20 Joaquin Tey Lucy Gazca Dino StrauszEdgardo Roldan
10:20 - 10:35 Descanso
11:40 - 12:10 Café
17:05 - 17:25 Café Café
Comida
Tarde libre
