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 [2022/08/30 18:18] lucas |
seminario:seminarios [2023/06/18 18:15] 127.0.0.1 external edit |
||
---|---|---|---|
Line 1: | Line 1: | ||
======== Seminários ======== | ======== Seminários ======== | ||
- | ===== Próximos ===== | + | ===== Próximos ===== |
+ | \\ | ||
+ | |||
+ | ==== 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.// | ||
+ | |||
+ | \\ | ||
+ | |||
+ | |||
+ | ===== 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 ==== | ||
+ | === Lucas Silva Sinzato Real === | ||
+ | === 13h em 27/04/2023 === | ||
+ | |||
+ | Para a generalização de diversos resultados de natureza finita, é conveniente interpretar "pontos limites" em um grafo infinito como objetos similares a vértices. Formalmente, uma **extremidade** em um grafo $G$ é um elemento do quociente obtido quando dizemos que raios em $G$ são equivales se estão infinitamente conectados. Dessa maneira, podemos inserir uma topologia apropriada sobre vértices e extremidades de forma que um raio acumule em sua classe de equivalência, intuindo que essa é a "direção" na qual ele aponta. Restringindo-nos apenas a esses objetos limites, fica definido um espaço topológico $\Omega(G)$, dito ser o **espaço de extremidades** de $G$. Em 1992, Diestel pergunta que propriedades topológicas caracterizam os espaços obtidos dessa maneira. Então, em uma tentativa de filtrar espaços topológicos que podem ser espaços de extremidades, apresentaremos neste seminário a prova de que $\Omega(G)$ é um espaço ultraparacompacto para todo grafo $G$, conforme concluíram Kurkofka, Melcher e Pitz em 2021. Como principal ferramenta que sustenta essa demonstração, discutiremos uma variação do algoritmo de busca em profundidade para encontrar árvores normais. | ||
+ | |||
+ | |||
+ | ==== Conjectura da 2-cobertura por ciclos: o retorno ==== | ||
+ | === Luisa Gomes Seixas === | ||
+ | === 13h em 20/04/2023 === | ||
+ | |||
+ | A conjectura da 2-cobertura por ciclos, abordada previamente em outro seminário, foi proposta na década de 70, e permance em aberto desde então. | ||
+ | |||
+ | Aqui, iremos relembrar um pouco do que foi visto do seminário anterior em relação a essa conjectura. Além disso, nos concentraremos em três pontos principais: | ||
+ | |||
+ | * Mostrar que se a conjectura vale para grafos finitos, então vale para grafos localmente finitos; | ||
+ | * Abordar uma generalização da conjectura; | ||
+ | * Tentar mostrar que, se a conjectura vale para grafos localmente finitos, então vale para qualquer grafo. | ||
+ | |||
+ | Abordaremos os problemas que encontramos e os próximos passos no estudo dessa conjectura e de sua generalização. | ||
+ | |||
+ | ==== Grafos entre nós ==== | ||
+ | === Lucas Silva Sinzato Real === | ||
+ | === 13h em 24/11/2022 === | ||
+ | |||
+ | A noção de planaridade é bem conhecida na Teoria dos Grafos: dizemos que um grafo é planar quando pode ser desenhado em $\mathbb{R}^2$ sem que haja o cruzamento de suas arestas. Neste seminário, discutiremos uma definição similar com respeito a mergulhos de grafos em espaços tridimensionais. Nessa direção, encontraremos grafos que não podem ser desenhados em $\mathbb{R}^3$ sem que seus ciclos se linkem, e outros que não admitem representações sem que um de seus ciclos de enode. Para essa abordagem, porém, recorreremos a algumas ferramentas da Teoria de Nós. | ||
+ | |||
+ | ==== Conjectura da $2$-cobertura por ciclos ==== | ||
+ | === Luisa Gomes Seixas === | ||
+ | === 13h em 17/11/2022 === | ||
+ | |||
+ | A conjectura da $2$-cobertura por ciclos, proposta nos anos 70, de forma independente, por Szekeres e Seymour, afirma o seguinte: | ||
+ | |||
+ | Todo grafo sem pontes possui uma coleção de ciclos tal que toda aresta aparece em exatamente dois desses ciclos. | ||
+ | |||
+ | Nessa apresentação, iremos explorar o que já se sabe sobre esse conjectura. | ||
+ | Estudaremos o curioso caso dos snarks, candidatos a contraexemplo da conjectura, entendendo quem são essas estruturas. | ||
+ | Por último, vamos mostrar que, se existe um contraexemplo não-enumerável para tal conjectura, então podemos encontrar um contraexemplo enumerável. | ||
+ | |||
+ | |||
+ | ==== Empacotar + Cobrir = Decompor ==== | ||
+ | === Lucas Silva Sinzato Real === | ||
+ | === 13h em 20/10/2022 === | ||
+ | |||
+ | Conhecidas como Teoremas de Nash-Willians, há caracterizações para que, dado $k\in \mathbb{N}$, um grafo finito $G = (V,E)$ admita uma família de $k$ árvores geradoras disjuntas nas arestas ou admita uma família de $k$ árvores geradoras que as cobrem. No estudo de grafos infinitos, porém, essas duas propriedades estão de certa forma relacionadas. Neste seminário, mostraremos que, quando $k$ e $G$ são infinitos, possuir $k$ árvores geradoras disjuntas nas arestas e possuir $k$ árvores geradoras que as cobrem é uma condição equivalente a possuir $k$ árvores geradoras que simultanemente são disjuntas nas arestas e as cobrem. Curiosamente, ainda não se sabe se esse resultado - que é do tipo Cantor-Bernstein-Schroeder - pode ser obtido quando $k$ é finito. | ||
+ | |||
+ | |||
+ | |||
+ | ==== Submodelos elementares, axioma de Martin e árvores geradoras sem ramo infinito ==== | ||
+ | === Luisa Gomes Seixas === | ||
+ | === Sala 3-009 às 13h em 29/09/2022 === | ||
+ | |||
+ | Submodelos elementares possuem aplicações nas mais diversas áreas da matemática e fazem com que várias demonstrações se tornem muito mais fáceis. O mesmo vale para o axioma de Martin. Uma das áreas em que podemos aplicar essas ferramentas é a teoria dos grafos. | ||
+ | |||
+ | Aqui, iremos utilizar submodelos elementares para demonstrar que, se vale $MA_{k}$, então todo grafo $\omega$-conectado de cardinalidade menor ou igual a $\kappa$ tem uma árvore geradora sem ramos infinitos. | ||
+ | |||
==== Vértices no infinito ==== | ==== Vértices no infinito ==== | ||
=== Lucas Silva Sinzato Real === | === Lucas Silva Sinzato Real === | ||
- | === 01/09/2022 Sala 3-011 === | + | === Sala 3-011 às 13h em 01/09/2022 === |
Determinados objetos importantes da Teoria dos Grafos são finitos por natureza, como os ciclos e os caminhos. Por conta disso, alguns resultados clássicos dessa área dizem respeito a grafos com apenas finitos vértices, de modo que análogos infinitos (quando possíveis de serem obtidos) muitas vezes requerem adaptações em seus enunciados. Nesta apresentação, veremos que a noção de extremidade em um grafo infinito é adequada para responder as seguintes perguntas: O que é um ciclo infinito? Quais as pontas que caminhos infinitos conectam? | Determinados objetos importantes da Teoria dos Grafos são finitos por natureza, como os ciclos e os caminhos. Por conta disso, alguns resultados clássicos dessa área dizem respeito a grafos com apenas finitos vértices, de modo que análogos infinitos (quando possíveis de serem obtidos) muitas vezes requerem adaptações em seus enunciados. Nesta apresentação, veremos que a noção de extremidade em um grafo infinito é adequada para responder as seguintes perguntas: O que é um ciclo infinito? Quais as pontas que caminhos infinitos conectam? | ||
- | Para tanto, utilizaremos o Teorema de Lovász-Cherkassky como exemplo de resultado sobre grafos finitos em que "vértices no infinito" auxiliam no desenvolvimento de uma generalização. | ||
- | ===== Anteriores ===== | + | Inclusive, utilizaremos o Teorema de Lovász-Cherkassky como exemplo de resultado sobre grafos finitos em que "vértices no infinito" auxiliam no desenvolvimento de uma generalização. |
+ | |||
+ | <WRAP tip> | ||
+ | * {{:seminario:lovaszcherkassky.pdf |Slides}} | ||
+ | </WRAP> | ||
==== O Teorema de Kuratowski ==== | ==== O Teorema de Kuratowski ==== |