Calendário de Eventos

Flat View
Ver por ano
Vista mensal
Ver por mês
Weekly View
Ver por semana
Daily View
Ver Hoje
Search
Pesquisar
Download como arquivo ICAL
Fábio Botler ministra palestra "Counting graph orientations with no directed triangles"
Quinta-feira, 02 Julho 2020, 14:00 - 15: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).

Voltar

Topo