Speaker: Taísa Martins, UFF.
Date: 05 oct 2022, 14h.
Place: Google Meet: swt-uoda-eyn.
Abstract: Füredi provou que todo grafo K_{r+1}-livre G pode se tornar r-partido pela remoção de no máximo k arestas onde k = ((r-1)/2r)(v(G))^2 - e(G). Investigamos versões mais fortes desse resultado. Para r<5, mostramos que todo grafo K_{r+1}-livre G pode se tornar r-partido pela remoção de no máximo 4k/5 arestas, e conjecturamos que o mesmo é verdadeiro para todo r. Tal conjectura implica uma solução para um problema de Sudakov com relação ao menor número de arestas que precisam ser removidas para tornar um grafo K_{r+1}-livre em um grafo bipartido. Por fim, mostramos que todo grafo K_6-livre G pode se tornar bipartido pela remoção de no máximo 4(v(G))^2/25 arestas, resolvendo um dos casos do problema de Sudakov. Nossa principal ferramenta é a técnica de flag álgebras de Razborov.
Esse é um trabalho em conjunto com Ping Hu, Bernard Lidický, Sergey Norin e Jan Volec.