Seminario de Grafos

08 de Junio del 2023, de 10:30 – 11:45 hrs. Sala de Seminarios  John Von Neumann CMM, Séptimo Piso Torre Norte. Beauchef 851.

Speaker: Matías Azocar, DIM, Universidad de Chile.

Title: Condiciones 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.

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 $2$-arista coloreo de $G$, o bien hay ciclos de cadalargo en $\{3,4,5,…,2t+2\}$ de un mismo color o bien hay ciclos de cada largo par en $\{4, 6, 8, …, 2t + 2\}$ del mismo color». Este resultadoresuelve algunas conjeturas planteadas por Schelp, Benevides, {\L}uczak,Scott, Skokan y White.