======== Seminários ========
===== Próximos =====
\\
\\
===== Anteriores =====
==== Conjectura de Kriesell para grafos infinitos ====
=== Rodrigo Santos Monteiro ===
=== Sala 5-002 às 14h em 27/03/2026 ===
Seja \(G\) um grafo e \(S \subseteq V(G)\) um subconjunto de vértices. Uma árvore de Steiner para \(S\) em \(G\) é uma árvore de \(G\) cujo conjunto de vértices contém \(S\). Kriesell conjecturou que, para todo subconjunto de vértices \(S\) que é \(2k\)-aresta-conexo em um grafo finito e conexo \(G\), existem \(k\) árvores de Steiner para \(S\) duas a duas disjuntas em arestas. É bem conhecido que essa conjectura é falsa para grafos infinitos.
Neste seminário apresentamos uma versão da conjectura de Kriesell com árvores topológicas para grafos enumeráveis e uma versão com \(F\)-limites de árvores para grafos rayless.
Mostramos que, se a conjectura de Kriesell for válida para grafos finitos, então ela também é válida para todo grafo conexo, rayless e finitamente separável por arestas. Em particular, todo grafo \(2k\)-aresta-conexo, rayless e finitamente separável por arestas contém \(k\) árvores geradoras duas a duas disjuntas em arestas.
==== Jogos para raios (sem hífen!) ====
=== Matheus Duzi ===
=== Sala 5-002 às 14h em 20/03/2026 ===
Como mencionado em seminários anteriores, os ditos espaços de raios (de árvores enraizadas) têm uma íntima relação com os espaços de extremidades (de grafos). No artigo que estabelece tal relação, Kurkofka e Pitz (2021-2024) levantam uma pergunta, que deixam como problema em aberto: é possível caracterizar, combinatoricamente, quando duas árvores (especiais) têm seus espaços de raios homeomorfos?
Neste seminário, exploraremos um pouco mais a fundo estes espaços (trazendo sua definição, propriedades e exemplos básicos) e jogaremos alguns jogos infinitos com o objetivo de responder o problema levantado por Kurkofka e Pitz.
==== Fluxos em redes infinitas ====
=== Guilherme Eduardo Pinto ===
=== Sala 5-002 às 14h em 13/03/2026 ===
A literatura de fluxos em grafos (direcionados) finitos é tão diversa em viéses de
estudo quanto em aplicações, aparecendo nas engenharias, na computação, entre
outras áreas do conhecimento. Ela também tem uma aplicação interessantíssima
na própria teoria de grafos, que, por meio do teorema de Fluxo Maximal/Corte
minimal, pode-se provar as versões não dirigidas e dirigidas do clássico Teorema de
Menger (verificar o capítulo 6 do livro de Diestel (2025) para mais informações).
Apesar da sua versão finita ser uma área tão rica, a contraparte infinita permanece
pouco explorada, com os principais resultados sendo o artigo de Miraftab e
Moghadamzadeh (2017), no qual trabalham com a teoria de fluxos algébricos, e
o artigo de Aharoni et al. (2011), que verifica uma versão do teorema de Fluxo
Maximal/Corte minimal para grafos enumeráveis em redes direcionadas.
Iremos ver possíveis definições de redes e fluxos em redes infinitas e as dificuldades
de traduzir esse problema do finito para o infinito. Provaremos o teorema de Fluxo
Maximal/Corte minimal para redes direcionadas de capacidade integral. Por fim,
exploraremos o que significa um fluxo fluindo de uma extremidade a outra, ou seja,
vindo de um infinito e desaguando em outro lado infinito.
==== Grafos e Suas Amigas Especias: Árvores====
=== Igor Santos ===
=== Sala 3-010 às 14h em 27/02/2026 ===
Como visualizar as extremidades de um grafo infinito? Embora os espaços de extremidades nos deem muitas informações sobre a estrutura global de um grafo infinito, ver a 'cara' da sua topologia pode não ser uma tarefa fácil. Se o grafo fosse uma árvore — ou, de outra forma, se o seu espaço de extremidades pudesse ser visto como o de uma árvore bem comportada — talvez não tivéssemos tantos problemas. No entanto, o problema é que, no geral, isso não ocorre com tanta frequência. Neste Combinando, mostraremos que, embora nem todo grafo infinito possua uma árvore que preserve as suas extremidades, todos eles podem ser representados por algo muito próximo disso.
* {{ :seminario: tgrafosecaminhos.pdf |Notas do seminário}}
==== Emaranhados ====
=== Violeta Mar ===
=== Sala 3-011 às 14h em 13/02/2026 ===
A teoria de emaranhados (tangles, em inglês) nasce na teoria de conectividade de grafos finitos. Aqui apresentamos uma versão ‘conjuntista’ dela, vinda da versão simplificada
apresentada por Diestel em seu livro cujo objetivo era aplicações em inteligência artificial.
* {{ :seminario: emaranhados.pdf |Notas do seminário}}
==== As álgebras por trás das extremidades (Parte 2) ====
=== Violeta Mar ===
=== Sala 3-009 às 14h em 06/02/2026 ===
O espaço de extremidades de um grafo infinito é um dos seus mais estudados invariantes. Assim, é de se esperar que ele teria sido descoberto e redescoberto várias vezes por diferentes pessoas em diferentes áreas de pesquisa. Numa tentativa de tentar fazer sentido desse mar de definições alternativas, eu e Gustavo Boska acabamos chegando em uma formulação da teoria um pouco alternativa. Ela é baseada em uma estrutura algébrica por trás da combinatória do grafo: uma álgebra de Boole que captura a forma como conjuntos finitos conectam ou desconectam o grafo. A teoria de álgebras de Boole é uma lindissima área da lógica, cujo maior resultado pode ser filosoficamente interpretado como uma dualidade entre sintaxe e semântica. Essa dualidade é conhecida como dualidade de Stone e ela diz, rapidamente, que a categoria de álgebras de Boole é equivalente à categoria de espaços de Stone - que são certos tipos especiais de espaços topológicos. Esta dualidade é o que vai nos permitir passar da álgebra do grafo para o seu espaço de extremidades. Apresentarei de forma breve esses objetos e resultados, sem muitos detalhes técnicos. (a não ser que o público demande...)
* {{ :seminario: algebras_de_cortes_e_separacoes.pdf |Notas do seminário}}
==== As álgebras por trás das extremidades (Parte 1) ====
=== Violeta Mar ===
=== Sala 3-009 às 14h em 30/01/2026 ===
O espaço de extremidades de um grafo infinito é um dos seus mais estudados invariantes. Assim, é de se esperar que ele teria sido descoberto e redescoberto várias vezes por diferentes pessoas em diferentes áreas de pesquisa. Numa tentativa de tentar fazer sentido desse mar de definições alternativas, eu e Gustavo Boska acabamos chegando em uma formulação da teoria um pouco alternativa. Ela é baseada em uma estrutura algébrica por trás da combinatória do grafo: uma álgebra de Boole que captura a forma como conjuntos finitos conectam ou desconectam o grafo. A teoria de álgebras de Boole é uma lindissima área da lógica, cujo maior resultado pode ser filosoficamente interpretado como uma dualidade entre sintaxe e semântica. Essa dualidade é conhecida como dualidade de Stone e ela diz, rapidamente, que a categoria de álgebras de Boole é equivalente à categoria de espaços de Stone - que são certos tipos especiais de espaços topológicos. Esta dualidade é o que vai nos permitir passar da álgebra do grafo para o seu espaço de extremidades. Apresentarei de forma breve esses objetos e resultados, sem muitos detalhes técnicos. (a não ser que o público demande...)
* {{ :seminario: algebras_de_cortes_e_separacoes.pdf |Notas do seminário}}
==== Inflações de $T-$grafos esparsos ====
=== Gabriel Zanetti ===
=== Sala 5-002 às 10h em 21/03/2024 ===
Será provado que se $T$ é uma árvore semi-especial que não é especial, então a inflação de um grafo $T-$esparso não é a subdivisão da inflação de um grafo $S-$esparso sendo $S$ uma árvore especial. Além disso, mostramos que a inflação de um grafo $T-$esparso possui apenas uma extremidade e o grau dessa extremidade é exatamente $\aleph_1$. Isso responde a uma pergunta de Geshke, Kurkofka, Melcher e Pitz de 2023. Este é um trabalho com Aurichi e Magalhães Júnior.
==== Colorindo por compacidade ====
=== Lucas Silva Sinzato Real ===
=== Sala 3-011 às 13h em 17/06/2024 ===
Um resultado parcial notável a respeito da Conjectura da Partição Não-Amigável diz que essas colorações existem em grafos que possuem apenas finitos vértices de grau infinito. Neste seminário, a demonstração desse fato será revisitada em uma tentativa de evidenciar os argumentos centrais utilizados, visando posteriormente empregá-los em outros contextos. Nessa direção, destacam-se o uso de princípios de compacidade e estimativas envolvendo cortes máximos em grafos finitos. Em particular, uma curta prova para o Lema da Seleção de Rado será esboçada com base em noções de topologia.
==== Famílias Universais (uma continuação evitando grafos finitos em rayless) ====
=== Guilherme Eduardo Pinto ===
=== Sala 3-011 às 13h em 10/06/2024 ===
Em uma apresentação passada, vimos sobre famílias universais e a construção de uma família universal pequena para os grafos rayless enumeraveis. Nessa apresentação iremos explorar uma adaptação da contrução anterior para provar que, para qualquer família finita de grafos finitos, há uma família universal pequena para a classe de rayless enumeraveis com os grafos da família finita proibidos.
==== Uma variação da conjectura do grau de extremidades de Halin ====
=== Paulo Sérgio Farias Magalhães Júnior ===
=== Sala 3-010 às 13h em 03/06/2024 ===
Neste seminário vamos motivar e apresentar uma variação da conjectura do grau de extremidades de Halin. Além disso, vamos provar que para o caso $\aleph_1$ essa variação da conjectura vale.
==== Um resultado sobre árvores geradoras ====
=== Mauricio Gibertoni Sia ===
=== Sala 3-010 às 13h em 27/05/2024 ===
A classe de Schmidt é uma classe de grafos e possui algumas peculiaridades muito interessantes, por exemplo, o fato dela ser a classe dos grafos sem raio, ou seja, os grafos sem caminhos infinitos. Neste apresentação iremos exibi-lá e juntamente a isso mostrar algumas de suas propriedades e características. E no final mostrarmos que sempre podemos encontrar dentro de um grafo desta classe uma árvore geradora possuindo algumas coisinhas a mais.
==== Grafos com poucos vértices de grau infinito ====
=== Lucas Silva Sinzato Real ===
=== Sala 3-010 às 13h em 13/05/2024 ===
Uma maneira de medir a complexidade de um dado grafo é por meio da análise de como se comportam os seus raios. Em seminários anteriores, por exemplo, discutimos como procedimentos hierárquicos podem ser utilizados para caracterizar grafos rayless, onde esses objetos não são encontrados. Motivados por essa abordagem, estudaremos certas estruturas recursivas em grafos cujos raios passam por apenas finitos vértices de grau infinito. Com as técnicas propostas, esboçaremos uma aplicação envolvendo a Conjectura da Partição Não-Amigável.
==== Famílias Universais (e uma pequena para rayless) ====
=== Guilherme Eduardo Pinto ===
=== Sala 3-011 às 13h em 06/05/2024 ===
A construção de Rado de um grafo universal para grafos enumeráveis inspirou a busca por grafos universais para diferentes classes, em particular, as de grafos enumeráveis com subgrafos proibidos. Há provas clássicas que algumas classes não admitem um universal. Nesses casos, estudamos famílias universais, buscando as menores possíveis. Iremos apresentar ideias e resultados acerca desse tema, por fim será apresentada uma nova construção de uma família universal pequena para a classe dos grafos rayless enumeráveis.
==== Produtividade de \(\Delta-\)sets ====
=== Vinícius de Oliveira Rodrigues ===
=== Sala 3-010 às 13h em 29/04/2024 ===
\(\Delta-\)sets são conjuntos de números reais relacionados ao problema do espaço normal de Moore. Neste seminário, motivaremos as definições destes conjuntos e mencionaremos alguns fatos conhecidos sobre eles. Feito isso, discutiremos dois resultados meus em coautoria com Rodrigo Rey Carvalho. O primeiro resultado, que utiliza forcing, é o de que é consistente a existência de um \(Q-\)set cujo quadrado não é um \(\Delta-\)set. O segundo resultado é o de que se existe um \(\Delta-\)set, existe um \(\Delta-\)set tal que todas as potências finitas são \(\Delta-\)sets.
==== Separadores: Topologia X Combinatória ====
=== Lucas Silva Sinzato Real ===
=== Sala 3-010 às 13h em 22/04/2024 ===
A topologia dos espaços de extremidades em grafos infinitos muitas vezes reflete propriedades combinatórias destes objetos. Nesta direção, este seminário visa explicar como hipóteses de separação topológica podem ser interpretadas por meio da existência de subgrafos apropriados. Em particular, resultados do tipo Menger serão revisitados com o auxílio de ferramentas desenvolvidas pela literatura recente em teoria dos grafos infinitos. Dentre elas, destacam-se a noção de envelopes e a aproximação de espaços de extremidades por árvores normais, seguindo certos trabalhos obtidos por Melcher, Kurkofka e Pitz.
==== Pseudo Potência e a Conjectura dos Graus de Halin ====
=== Gabriel Zanetti ===
=== Sala 3-010 às 13h em 08/04/2024 ===
Vamos caracterizar os cardinais acima do continuum em que a conjectura de Halin é verdadeira em termos do operador pseudo potencia de Shelah.
==== Sobre a Conjectura de Salia ====
=== Paulo Sérgio Farias Magalhães Júnior ===
=== Sala 3-010 às 13h em 18/03/2024 ===
Seja $G$ um grafo, denotaremos por $N_G(X)$ o conjunto dos vértices de $G$ os quais possuem pelo menos dois vizinhos em $X$. Dizemos que um grafo bipartido $G$ com lados $A$ e $B$ satisfaz a propriedade double Hall se $\vert A \vert\geq 2$, e $\vert N^2_G(X)\vert\geq \vert X\vert $ para todo $X\subset A$ de tamanho pelo menos 2. Tais grafos são chamados de **grafos dHp**. Em 2021, Salia apresentou a seguinte conjectura em sua tese de doutorado:
//__Conjectura de Salia:__// Se $G$ é um grafo dHp bipartido com lados $A$ e $B$, então existe um ciclo que cobre $A$.
Nesta apresentação iremos apresentar alguns resultados que obtemos na direção de resolver a Conjectura de Salia para grafos infinitos e também os problemas que ainda não conseguimos superar.
==== Limites de ciclos e a conjectura da 2-cobertura ====
=== Paulo Sérgio Farias 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.//
==== 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 ====
=== Lucas Silva Sinzato Real ===
=== 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?
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.
* {{:seminario:lovaszcherkassky.pdf |Slides}}
==== O Teorema de Kuratowski ====
=== Luan Arjuna Fraga Ramires ===
=== 24/11/2021 ===
Grafos são estruturas extremamente úteis e versáteis, mas muito complicadas. Por esse motivo, desenhos são sempre bem vindos para facilitar sua visualização!
No entanto, se o seu desenho é uma confusão de pontos e arcos passando por cima uns dos outros, ele pode mais atrapalhar do que ajudar na compreensão do grafo em questão...
É claro que alguns grafos são tão complicados que seria impossível evitar essa confusão.
Surge assim o questionamento: o que é necessário para que um grafo possa ser desenhado sem que haja sobreposição de arestas?
A resposta pode te supreender!
* [[https://drive.google.com/file/d/1498By8UvTiVu_F7Oa46q7a6cyJOzWevW/view?usp=sharing|Vídeo]]
* {{:seminario:kuratowski.pdf |Slides}}
==== Dar uma festa de sucesso é NP-difícil ====
=== Sabrina Teodoro Alberto da Silva ===
=== 20/10/2021 ===
Neste seminário vamos provar que encontrar um conjunto independente máximo em um grafo é difícil. Muito difícil. NP-díficil. Participe dessa festa.
* [[https://drive.google.com/file/d/1NtjJEaNi_sECV-0ql9Mbw2VoP1YZA69m/view?usp=sharing|Vídeo]]
* {{:seminario:festa_de_sucesso.pdf |Slides}}
==== O Teorema do Sanduíche de Presunto ====
=== Luan Arjuna Fraga Ramires ===
=== 01/09/2021 ===
Neste seminário iremos dividir em partes de mesmo volume um sanduíche de presunto! Para esse fim, realizaremos uma caçada por pontos fixos através do surpreendente resultado da geometria combinatória conhecido por lema de Sperner! Não perca!
* [[https://drive.google.com/file/d/1KAerdaJJWZS1-w23fSaQvjYMRY80oICT/view?usp=sharing|Vídeo da primeira parte]]
* {{:seminario:o_teorema_do_ponto_fixo.pdf |Slides da primeira parte}}
* [[https://drive.google.com/file/d/1kw-0SdccVHHX7mkByAZMlmGcdg4ZS0yy/view?usp=sharing|Vídeo da segunda parte]]
* {{:seminario:o_teorema_do_sanduiche_de_presunto.pdf |Slides da segunda parte}}
==== O Lema de Sperner e o Problema do Aluguel Harmônico ====
=== Sabrina Teodoro Alberto da Silva e Luan Arjuna Fraga Ramires ===
=== 01/04/2021 ===
Neste seminário, vamos dividir os quartos e o aluguel de um apartamento, sem causar inveja entre os inquilinos, através de um dos resultados mais supreendentes da geometria combinatória: o lema de Sperner.
==== HEX e Y: dois jogos de conexão (que são "equivalentes") ====
=== Lucas Silva Sinzato Real ===
=== 18/03/2021 ===
Os jogos HEX e Y são compostos por um tabuleiro de casas hexagonais em que dois jogadores se alternam na disposição de peças de modo a construírem, cada um, um conjunto específico. Nos dois casos, é declarado vencedor aquele participante que atingir seu objetivo. Neste seminário, com o auxílio de resultados simples de planaridade de grafos, veremos que esse critério de vitória não está mal colocado e nem ambíguo: nos dois jogos, se o tabuleiro estiver totalmente preenchido por peças, é possível identificar que um (e apenas um) jogador construiu sua disposição de peças almejada. Na verdade, basta verificar essa propriedade para um dos jogos, pois, como será demonstrado, um deles não admite empates se, e somente se, o outro também não.
* {{:seminario:hex-y.pdf |Slides}}
==== O Problema do Final Feliz ====
=== Luan Arjuna Fraga Ramires ===
=== 04/02/2021 ===
Neste seminário será apresentada uma aplicação inusitada do Teorema de Ramsey na geometria: uma generalização do Problema do Final Feliz, o qual afirma que, dado um conjunto de cinco pontos em posição geral no plano, existe um subconjunto de quatro pontos formando um quadrilátero convexo! Divirta-se!
* [[https://drive.google.com/file/d/108fKeYovQZZLJm33gLZCw_ptYVwwxOdU/view?usp=sharing|Vídeo]]
==== É difícil capturar o ladrão ====
=== Lucas Silva Sinzato Real ===
=== 19/11/2020 ===
O Jogo de Cops and Robber sobre um grafo consiste em um jogo de perseguição no qual uma equipe de policiais tenta capturar um ladrão. Cada personagem pode se deslocar pelo grafo por meio de suas arestas e, a todo momento, os policiais e o ladrão sabem onde cada um se encontra. Não é difícil observar que, se a equipe de policiais for muito grande, o ladrão é certamente capturado em finitas rodadas. Contudo, quais propriedades um grafo deve ter de modo que apenas um policial consiga desenvolver uma estratégia vencedora para capturar o ladrão? Anteriormente, vimos que os grafos finitos com tal característica podem ser caracterizados em termos de uma noção de "desmanchabilidade", enquanto grafos infinitos interessantes com essa propriedade são difíceis de serem encontrados. Neste seminário, veremos que, mesmo em grafos infinito com muitas arestas, o ladrão pode ser esperto o suficiente para nunca ser capturado por um policial.
* [[https://drive.google.com/file/d/1zAo0HtOfG79_dvMY-glN8D_6MaGfH25-/view?usp=sharing|Vídeo]]
* {{:seminario:cordal.pdf |Slides}}
==== Números de Ramsey ====
=== Luan Arjuna Fraga Ramires ===
=== 29/10/2020 ===
Determinar o valor dos números de Ramsey é um dos problemas em aberto mais importantes da matemática contemporânea. Nesta apresentação serão desenvolvidos métodos construtivos e probabilísticos a fim de computar cotas para tais valores.
* [[https://drive.google.com/file/d/1NL6tCXn_Ww4zWep6XCiV42inVKKsun_c/view?usp=sharing|Vídeo]]
* {{:seminario:números_de_ramsey.pdf |Slides}}
==== O Algoritmo das Flores de Edmonds ====
=== Sabrina Teodoro Alberto da Silva ===
=== 17/09/2020 ===
Um emparelhamento (=matching) é um conjunto M de arestas duas a duas não adjacentes, e é máximo se $|M| \geq |M'|$ para qualquer emparelhamento $M'$. Neste seminário apresentaremos um algoritmo polinomial que encontra um emparelhamento máximo em um grafo arbitrário, um importante marco no desenvolvimento da Otimização Combinatória. Também visitaremos a Teoria dos Grafos envolvida e comentaremos uma das várias aplicações que os emparelhamentos proporcionam.
* {{:seminario:edmonds.pdf |Slides}}
* [[https://drive.google.com/file/d/1krasEVs0Tun2oQM49yjVWxK4SdVlROhw/view?usp=sharing|Parte I]]
* [[https://drive.google.com/file/d/1N-IqxKJht8mpPYfUMf8teg_b3vLql1_f/view?usp=sharing|Parte II]]
* [[https://drive.google.com/file/d/1pPstwF-26vqjYiFQwx8HNb9iUb1aj-km/view?usp=sharing|Parte III]]
==== Aplicação de teorias dos grafos ao problema do caixeiro viajante métrico ====
=== Sabrina Teodoro Alberto da Silva ===
=== 28/08/2020 ===
O Problema do Caixeiro Viajante (TSP) é um dos mais famosos da matemática computacional, devido a suas várias aplicações práticas e por ser NP-difícil. Sequer é conhecido um algoritmo de aproximação com razão constante para o TSP. Contudo, para um caso particular do problema, o do Caixeiro Viajante Métrico (TSPM), um tal algoritmo é conhecido.
Neste seminário, apresentaremos um algoritmo que encontra uma solução sub-ótima para o TSPM, e visitaremos a Teoria dos Grafos e a Otimização Combinatória subjacentes.
* [[https://drive.google.com/file/d/1_uvs7omcQ_CY3UfDSli863qX8EnQ1T-p/view?usp=sharing|Parte I]]
* [[https://drive.google.com/file/d/1OyliqjPzn39bU5h4jHzCth9TlXDsCS-W/view?usp=sharing|Parte II]]
* {{ :seminario:caixeiro.pdf |Slides}}
==== Colorindo a reta real ====
=== Thales Sarinho Galvão Santos de Souza ===
=== 31/07/2020 ===
Vamos introduzir colorações em grafos feitos com pontos da reta, onde a adjacência de pontos depende de um intervalo. Vamos apresentar algumas definições usuais de grafos e obter alguns resultados sobre seus subgrafos e números cromáticos.
* [[https://drive.google.com/file/d/1tDWQmLrcMr1tPpGuwYL3m0hYV0YC7oeY/view?usp=sharing|Vídeo]]
* {{colorindo.pdf|Slides}}
==== Matroides ====
=== Gustavo HL Boska ===
=== 15/05/2020 ===
Uma **brevíssima** introdução ao mundo dos matroides. Como nasceram e que formas e nichos ocupam na matemática? Vamos discutir em particular os axiomas de independência, matroides gráficos e aplicações em problemas de otimização.
{{ :seminario:miniature.png?400|}}
Suponha que você é um ponto num espaço $n$-dimensional e quer andar por todas as dimensões, mas só pode andar em finitas direções, cada uma oferecendo um certo custo (não linear), que direções escolher?
Suponha que você queira conectar todas as cidades do seu país, sabendo quanto custará cada estrada, como gastar o mínimo possível?
Estes problemas tem a mesma solução : O algoritmo guloso, mas o que eles têm em comum?
* [[https://www.youtube.com/watch?v=ZdOqQyGIxfI|Vídeo]]
* {{matroid.pdf|Slides}}
=== O Jogo de Cops And Robber ===
=== Lucas Silva Sinzato Real ===
=== 08/05/2020 16h ===
Interpol consiste em um jogo de perseguição, em que uma equipe de detetives da Interpol deve se movimentar por um tabuleiro em busca do criminoso Mister X. Cada um dos jogadores realiza seus movimentos de acordo com as possibilidades permitidas pelo tabuleiro, que se assemelha muito a um grafo. Durante o jogo, a equipe da Interpol possui uma quantidade limitada de movimentos, bem como Mister X, e não sabem exatamente onde se encontra o criminoso e quais movimentos ele pretende realizar. Neste seminário, discutiremos uma versão desse jogo com algumas simplificações: os jogadores possuem uma quantidade ilimitada de movimentos e os policiais, a todo momento, sabem precisamente em que local se encontra o ladrão. Mais especificamente, analisaremos quais condições sobre o tabuleiro do jogo são necessárias e suficientes para que apenas um policial capture o criminoso.
* {{copsandrobber.pdf|Slides}}
* [[https://www.youtube.com/watch?v=EzlWl7H0hmE| Vídeo]]
==== Teorema de Schur ====
=== Luan Arjuna Fraga Ramires ===
=== 17/04/2020 ===
Neste seminário será apresentado, de forma introdutória, o conjunto Zp com algumas de suas propriedades mais interessantes. Uma delas, a não validez de uma versão análoga do Último Teorema de Fermat, será demonstrada a partir de uma aplicação do Teorema de Ramsey: o Teorema de Schur.
* {{Teorema_de_Schur.pdf|Slides}}
==== Teoremas de Ramsey ====
=== Leandro F. Aurichi ===
=== 03/04/2020 16h combinando-seminario-icmc no Google Meet ===
O teorema de clássico de Ramsey deu origem a toda uma área que procura propriedades com o seguinte comportamento: posso pedir que uma estrutura seja grande o suficiente para garantir que certos padrões pré-definidos necessariamente aconteçam nela?
Neste seminário vamos apresentar a versão infinita do Teorema de Ramsey e usá-la para provar sua versão finita. A ideia é ser uma apresentação bem introdutória ao tema.
* {{slidesramsey.pdf|Slides}}
* {{https://drive.google.com/file/d/1JavtUN2zG9879AcOnm_7g4v0l1DQvKat/view?usp=sharing|Vídeo}} da apresentação
==== A Conjectura do Unfriendly Partition ====
=== Lucas Silva Sinzato Real ===
=== 10/03/2020 13h s. 3-010 ===
Seja $G = (V,E)$ um grafo. Dado $v \in V$ um vértice, o conjunto dos vértices a ele adjacentes, designado **vizinhança** de $v$, será denotado por $N(v)$. Por **grau** do vértice $v$, nos referimos a $|N(v)|$. Dado $n \in \mathbb{N}$ um natural, uma função $f : V \to \{0,1,2,3,\dots,n-1\}$ será dita uma $n-$ **coloração** do grafo. Naturalmente, $f$ induz uma partição sobre $V$: $\{f^{-1}(i) : 0 \leq i \leq n-1\}$ é uma família de conjuntos dois a dois disjuntos cuja união é $V$. Se uma função $g : K \to \{0,1,2,\dots,n-1\}$ é uma restrição de $f$, em que $K\subset V$, dizemos que $f$ **estende** $g$.
Agora, fixe uma $2-$coloração $\pi: V \to \{0,1\}$ de $G$. Dado $x \in V$, defina os conjuntos $A_{\pi}(x) = \{y \in N(x) : \pi(y)\neq \pi(x)\}$ e $B_{\pi}(x) = \{y \in N(x) : \pi(y)=\pi(x)\}$ com cardinalidades $a_{\pi}(x)$ e $b_{\pi}(x)$. Dizemos que $\pi$ é **unfriendly** para o vértice $x$ se $a_{\pi}(x) \geq b_{\pi}(x)$. Se $\pi$ for unfriendly para todos os vértices de seu domínio, dizemos que essa é uma **unfriendly partition**. Os matemáticos R. Cowan e W. Emerson, em um texto que não foi publicado, conjecturaram que todo grafo possui uma unfriendly partition. Neste seminário, verificaremos que a conjectura é válida para grafos finitos. Além disso, podemos estender colorações sobre um grafo $G$ de uma maneira conveniente o suficiente para que grafos localmente finitos (isto é, em que todos os vértices possuem grau finito, mesmo que a quantidade de vértices seja infinita) e com finitos vértices de grau infinito admitam unfriendly partitions. Esses resultados são de Aharoni, Milner e Prikry [1]. Posteriormente, Milner e Shelah [2] refutaram a conjectura ao exibirem um grafo não enumerável em que todos os vértices possuem grau infinito.
- Aharoni, R. and Milner, E. C. and Prikry, K. [[https://doi.org/10.1016/0095-8956(90)90092-E|Unfriendly partitions of a graph]], Journal of Combinatorial Theory, Series B (1) 50 (1990)
- Shelah, Saharon and Milner, E. C. [[https://doi.org/10.1017/CBO9780511983917.031|Graphs with no unfriendly partitions]], A Tribute to Paul Erdos, Cambridge University Press (1990)
* {{semináriocombinando.pdf|Slides}}
* {{suplementar10-03-2020.pdf|Arquivo suplementar}}