\(\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.

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.

Vamos caracterizar os cardinais acima do continuum em que a conjectura de Halin é verdadeira em termos do operador pseudo potencia de Shelah.

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.

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.

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.

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.

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.

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.

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.

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

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.

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!

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.

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!

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.

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.

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!

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.

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.

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.

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.

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.

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.

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?

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.

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.

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.

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.

1. Aharoni, R. and Milner, E. C. and Prikry, K. Unfriendly partitions of a graph, Journal of Combinatorial Theory, Series B (1) 50 (1990)
2. Shelah, Saharon and Milner, E. C. Graphs with no unfriendly partitions, A Tribute to Paul Erdos, Cambridge University Press (1990)