This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
seminario:seminarios [2023/05/22 20:18] 127.0.0.1 external edit |
seminario:seminarios [2023/06/18 18:15] 127.0.0.1 external edit |
||
---|---|---|---|
Line 3: | Line 3: | ||
===== Próximos ===== | ===== Próximos ===== | ||
\\ | \\ | ||
- | ==== Grafos': uma história de nove grafos proibidos ==== | ||
- | === Lucas Silva Sinzato Real === | ||
- | === 13h em 25/05/2023 === | ||
- | Em um grafo \(G\) qualquer, podemos dizer que duas arestas são **vizinhas** quando incidem em um mesmo vértice. Com essa noção de adjacência, \(E(G)\) se torna o conjunto de vértices de um grafo \(G'\), dito ser o **grafo das arestas** de \(G\). Na literatura, grafos dessa natureza são protagonistas de diversos resultados que não se verificam para grafos quaisquer. Por exemplo, as possibilidades de seus números cromáticos variam em um conjunto controlado, enquanto que a aplicação \(G\mapsto G'''\) fornece um paralelo entre grafos eulerianos e hamiltonianos. Por esse motivo, neste seminário caracterizaremos os grafos que são grafos de arestas, descrevendo os (praticamente únicos) nove grafos que não são obtidos dessa forma. | + | ==== Limites de ciclos e a conjectura da 2-cobertura ==== |
+ | === Paulo Sérgio Farias de Magalhães Júnior === | ||
+ | === Sala 3-011 às 13h em 22/06/2023 === | ||
+ | |||
+ | No artigo "Sums of circuits" Seymour conjecturou que todo grafo sem pontes $G$ possui uma 2-cobertura por ciclos, isto é, uma coleção de ciclos de $G$ em que toda aresta do grafo está em exatamente dois ciclos dessa coleção, esta conjectura é chamada conjectura da 2-cobertura por ciclos. | ||
+ | |||
+ | Ao longo do tempo alguns avanços foram feitos no sentido de resolver e estender essa conjectura. Entre eles destacamos o resultado de Laviolette que diz que "Se a conjectura vale para grafos localmente finitos então ela vale para grafos infinitos quaisquer" e o resultado de Diestel, Stein e Bruhn na qual eles provam que "Se a conjectura vale para grafos finitos então vale para grafos localmente finitos". Com esses dois resultados se espera que possamos então mostrar que se a conjectura vale para grafos finitos então vale para qualquer grafo, porém isso não ocorre visto que os dois resultados anteriormente apresentados não trabalham com a mesma definição de ciclo. | ||
+ | |||
+ | Nesta apresentação iremos introduzir o conceito de limites de ciclos finitos, mostrar como esse objeto se comporta em grafos localmente finitos e mostrar que reformulando a conjectura para limites de ciclos finitos ao invés de ciclos podemos concluir o resultado: | ||
+ | |||
+ | **Teorema:** //Se a conjetura da 2-cobertura por limites de ciclos finitos vale para grafos finitos então ela também vale para grafos enumeráveis quaisquer.// | ||
\\ | \\ | ||
Line 13: | Line 20: | ||
===== Anteriores ===== | ===== Anteriores ===== | ||
+ | |||
+ | ==== Grafos': uma história de nove grafos proibidos ==== | ||
+ | === Lucas Silva Sinzato Real === | ||
+ | === 13h em 25/05/2023 === | ||
+ | |||
+ | Em um grafo \(G\) qualquer, podemos dizer que duas arestas são **vizinhas** quando incidem em um mesmo vértice. Com essa noção de adjacência, \(E(G)\) se torna o conjunto de vértices de um grafo \(G'\), dito ser o **grafo das arestas** de \(G\). Na literatura, grafos dessa natureza são protagonistas de diversos resultados que não se verificam para grafos quaisquer. Por exemplo, as possibilidades de seus números cromáticos variam em um conjunto controlado, enquanto que a aplicação \(G\mapsto G'''\) fornece um paralelo entre grafos eulerianos e hamiltonianos. Por esse motivo, neste seminário caracterizaremos os grafos que são grafos de arestas, descrevendo os (praticamente únicos) nove grafos que não são obtidos dessa forma. | ||
==== Ultraparacompacidade: mais uma aplicação da busca em profundidade ==== | ==== Ultraparacompacidade: mais uma aplicação da busca em profundidade ==== |