Events Calendar

Flat View
By Year
Monthly View
By Month
Weekly View
By Week
Search
Search
Download as iCal file
Fábio Botler ministra palestra "Counting graph orientations with no directed triangles"
Thursday, 02 July 2020,  2:00 -  3:00

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).

Back

Go to top