Noticias en español
Árboles generadores en digrafos densos.
Resumen: En el año 2001 se encontró una condición del grado mínimo para grafos con n vértices que aseguraba la contención de todo árbol generador de grado máximo acotado por cn/log(n). En este seminario se muestra que el mismo resultado, cambiando grado mínimo por semigrado mínimo, se tiene para árboles orientados y digrafos. Este fue demostrado en el presente año por Kathapurkar y Montgomery, quienes utilizaron un método distinto al clásico lema de Regularidad.
Read MoreEl problema de reconstrucción de las gráficas de fichas.
Abstract: Sea $G$ una gráfica simple de orden $n\ge 2$ y $k$ un entero tal que $n>k\ge 1$. La \emph{gráfica de $k$-fichas $F_k(G)$ de $G$} es la gráfica cuyos vértices son todos los $k$-conjuntos de vértices de $G$, y donde dos $k$-conjuntos son adyacentes si su diferencia simétrica es un par de vértices adyacentes en $G$. Las gráficas de fichas han sido definidas cuatro veces, de manera independiente, desde 1988, y tienen relación con otras gráficas bien conocidas, tales como las gráficas de Johnson y las gráficas de Johnson duplicadas. En las últimas dos décadas se han descubierto...
Read MoreCubriendo digrafos completos 2-coloreados con digrafos monocromáticos d-dominantes.
Abstract: En esta presentación, hablaremos sobre los resultados obtenidos en un reciente artículo de DeBiasio y Gyárfás (ver https://arxiv.org/pdf/2102.12794.pdf) donde se busca (y se logra) responder a la pregunta: ¿Es posible cubrir todos los vértices de un digrafo completo (incluyendo loops) 2-arista-coloreado por un número acotado de digrafos monocromáticos d-dominantes que solo dependa de d?.
Read MoreUmbral del semigrado para ciclos Hamiltonianos antidirigidos.
Resumen: DeBiasio y Molla prueban que para dígrafos suficientemente grandes en n vértices con semigrado al menos n/2 + 1 se tiene un ciclo Hamiltoniano antidirigido. Más aún, es suficiente con semigrado n/2, a menos que el dígrafo sea uno de dos contraejemplos. En este seminario se hablará de la demostración del resultado, mostrando con más detalle el caso no-extremal que usa método de absorción.
Read MoreBuscando ciclos balanceados.
Resumen: El teorema de los patrones inevitables dice que, para n suficientemente grande, toda 2-coloración de E(K_n) con “suficientes” aristas en cada clase cromática contiene al menos uno de dos patrones: una K_2t donde una clase cromática induce una K_t o bien una K_2t donde una clase cromática induce dos K_t disjuntas. Una gráfica G es balanceable si existe un entero no negativo k tal que toda 2-coloración de E(K_n) con más de k aristas en cada clase cromática contiene una copia de G de forma balanceada (la mitad de sus aristas son azules y el resto rojas). El entero k más...
Read MorePotencias de caminos en torneos.
Resumen: En esta charla se presentaran tres resultados recientes acerca de k-potencias de caminos en torneos, con un esquema de su demostración, así como la idea de “k-absorbers”, que es clave en esta, en particular: -Todo torneo contiene k-potencias de caminos lineales. -Todo torneo epsilon-intransitivo contiene k-potencias de ciclos lineales. -Todo torneo puede descomponerse como la unión de 2^c k-potencias de caminos
Read More