Buscando 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 chico que cumple esta definición se llama número de balanceo de G y se denota como bal(n,G). Hay ciclos que son balanceables y otros que no lo son. El teorema de patrones inevitables nos ayudará a determinar qué ciclos son balanceables y cuáles no. También hablaremos sobre el número de balanceo de los ciclos balanceables y qué podemos hacer con los ciclos no balanceables.

Posted on Jun 17, 2021 in Seminario de Grafos, Seminars