Data: 02/07/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Counting graph orientations with no directed triangles
Palestrante: Fábio Botler (UFRJ)


Abstract: Alon and Yuster proved that the number of orientations of any n-vertex graph in which every triangle is transitively oriented is at most 2^{\lfloor n^2/4 \rfloor} for n > 10^4 and conjectured that the precise lower bound on n should be 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^{\lfloor n^2/4\rfloor} such orientations.

This is a joint work with Pedro Araújo and Guilherme Oliveira Mota