voltarData: 05/10/2022
Título: Subgrafos multipartidos grandes em grafos H-livres.
Palestrante: Taísa Martins, UFF.
Data: 05 de Outubro de 2022, 14 h.
Sala: Google Meet.
Resumo: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.
Obs: Esse é um trabalho em conjunto com Ping Hu, Bernard Lidický, Sergey Norin e Jan Volec.