O professor Fábio Botler (PESC) ministrará palestra, on line, dia 2 de julho, às 14 horas (GMT-3, horário de Brasília), com o título "Counting graph orientations with no directed triangles".

A palestra faz parte dos "Seminários online de Grafos, Algoritmos e Combinatória", organizados por Vinicius dos Santos da UFMG e Guilherme Mota da USP. Clique aqui para mais detalhes.

Resumo:

Alon e Yuster provaram que para n > 10^4, o número de orientações de um grafo com n vértices nas quais todo triângulo é orientado de forma transitiva é no máximo 2^r, onde r é o número de arestas do grafo bipartido balanceado com n vértices, e conjecturaram que o limitante preciso em n é n > 7. Nós confirmamos essa conjectura e, além disso, caracterizamos a família de grafos extremais mostrando que o grafo bipartido balanceado com n vértices é o único grafo com n vértices para o qual existem exatamente 2^r tais orientações.

Este é um trabalho em colaboração com Pedro Araújo (IMPA) e Guilherme Oliveira Mota (USP).

Abstract:

Alon and Yuster proved that for n > 10^4, the number of orientations of any n-vertex graph in which every triangle is transitively oriented is at most 2^r, where r is the number of edges of the n-vertex balanced bipartite graph, and conjectured that the precise lower bound on n is n > 7. We confirm their conjecture and, additionally, characterize the extremal families by showing that the balanced complete bipartite graph with n vertices is the only n-vertex graph for which there are exactly 2^r such orientations. 

This is a joint work with Pedro Araújo (IMPA) and Guilherme Oliveira Mota (USP).