Noticias en español
Condiciones de grado mínimo para caminos y ciclos monocromáticos en grafos 2-arista-coloreados (segunda parte).
Abstract: Diremos que un grafo $G$ apunta a un grafo $H$ si es que en cada $2$-arista-coloreo de $G$ existe una copia monocromática de $H$. Schelp tenía la idea de que si el grafo completo $K_n$ apunta un grafo pequeño $H$, entonces cada subgrafo denso de $K_n$ también apunta a H.En este seminario, veremos un resultado demostrado por Balogh, Kostochka, Lavrov y Liu en 2021 ( https://arxiv.org/pdf/1906.02854.pdf ) que indica que “para todo $n$ suficientemente grande, si $n = 3t + r$ donde $r\in\{0,1,2\} y $G$ es un grafo en $n$ vértices con $\delta(G) \geq (3n-1)/4$,entonces para todo...
Read MoreCondiciones de grado mínimo para caminos y ciclos monocromáticos en grafos 2-arista-coloreados.
Abstract: Diremos que un grafo $G$ apunta a un grafo $H$ si es que en cada $2$-arista-coloreo de $G$ existe una copia monocromática de $H$. Schelp tenía la idea de que si el grafo completo $K_n$ apunta un grafo pequeño $H$, entonces cada subgrafo denso de $K_n$ también apunta a H.
Read MoreReconocimiento y caracterización de cuadrados exactos de grafos.
Abstract: Para un grafo G=(V,E) se define su cuadrado exacto, G^{[#2]}, como el grafocon el mismo conjunto de vértices V en donde una arista uv está en el cuadrado exacto si y solo si u y v están a distancia 2 en el grafo original G. Se dice que G es una raíz (cuadrada) exacta de G^{[#2]}. Se mostrará una caracterización de los grafos que tienen raíz exacta, donde dicha caracterización permite fácilmente crear un algoritmo de reconocimiento en tiempo polinomial. Se mostrará que reconocer grafos que tienen una raíz exacta que es bipartita es un problema NP-completo. Se presentará una...
Read MoreConversaciones entre la teoría de modelos y la teoría de grafos (tercera parte).
Abstract: En esta charla se pretende mostrar la utilidad de la teoría de modelos en combinatoria. En concreto, en la obtención de resultados para grafos infinitos. Se comenzará introduciendo el concepto de modelo para un lenguaje con una signatura dada, el concepto de submodelo y submodelo elemental, subrayando sus diferencias mediante un ejemplo. Posteriormente, se expondrá la construcción de submodelos elementales como herramienta para obtener resultados en grafos infinitos, en concreto para mostrar que si un grafo no tiene ningún corte mínimo impar, y pertenece a un modelo M para el cual...
Read MoreConversaciones entre la teoría de modelos y la teoría de grafos (segunda parte).
Abstract: En esta charla se pretende mostrar la utilidad de la teoría de modelos en combinatoria. En concreto, en la obtención de resultados para grafos infinitos. Se comenzará introduciendo el concepto de modelo para un lenguaje con una signatura dada, el concepto de submodelo y submodelo elemental, subrayando sus diferencias mediante un ejemplo. Posteriormente, se expondrá la construcción de submodelos elementales como herramienta para obtener resultados en grafos infinitos, en concreto para mostrar que si un grafo no tiene ningún corte mínimo impar, y pertenece a un modelo M para el cual...
Read MoreConversaciones entre la teoría de modelos y la teoría de grafos.
Abstract: En esta charla se pretende mostrar la utilidad de la teoría de modelos en combinatoria. En concreto, en la obtención de resultados para grafos infinitos. Se comenzará introduciendo el concepto de modelo para un lenguaje con una signatura dada, el concepto de submodelo y submodelo elemental, subrayando sus diferencias mediante un ejemplo. Posteriormente, se expondrá la construcción de submodelos elementales como herramienta para obtener resultados en grafos infinitos, en concreto para mostrar que si un grafo no tiene ningún corte mínimo impar, y pertenece a un modelo M para el cual...
Read More