Combinando

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======== Seminários ========

===== Próximos ===== 
\\
==== 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.      

\\
    

===== Anteriores =====

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

<WRAP tip>
  * {{:seminario:lovaszcherkassky.pdf |Slides}}
</WRAP>


==== 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!

<WRAP tip>
  * [[https://drive.google.com/file/d/1498By8UvTiVu_F7Oa46q7a6cyJOzWevW/view?usp=sharing|Vídeo]]
  * {{:seminario:kuratowski.pdf |Slides}}
</WRAP>

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

<WRAP tip>
  * [[https://drive.google.com/file/d/1NtjJEaNi_sECV-0ql9Mbw2VoP1YZA69m/view?usp=sharing|Vídeo]]
  * {{:seminario:festa_de_sucesso.pdf |Slides}}
</WRAP>


==== 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!

<WRAP tip>
  * [[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}}
</WRAP>

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

<WRAP tip>
  * {{:seminario:hex-y.pdf |Slides}}
</WRAP>


==== 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!

<WRAP tip>
  * [[https://drive.google.com/file/d/108fKeYovQZZLJm33gLZCw_ptYVwwxOdU/view?usp=sharing|Vídeo]]
</WRAP>

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

<WRAP tip>
  * [[https://drive.google.com/file/d/1zAo0HtOfG79_dvMY-glN8D_6MaGfH25-/view?usp=sharing|Vídeo]]
  * {{:seminario:cordal.pdf |Slides}}
</WRAP>


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


<WRAP tip>
  * [[https://drive.google.com/file/d/1NL6tCXn_Ww4zWep6XCiV42inVKKsun_c/view?usp=sharing|Vídeo]]
  * {{:seminario:números_de_ramsey.pdf |Slides}}
</WRAP>

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

<WRAP tip>
  * {{: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]]
</WRAP>

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

<WRAP tip>
  * [[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}}
</WRAP>

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

<WRAP tip>
  * [[https://drive.google.com/file/d/1tDWQmLrcMr1tPpGuwYL3m0hYV0YC7oeY/view?usp=sharing|Vídeo]]
  * {{colorindo.pdf|Slides}}
</WRAP>

==== 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?

<WRAP tip>
  * [[https://www.youtube.com/watch?v=ZdOqQyGIxfI|Vídeo]]
  * {{matroid.pdf|Slides}}
</WRAP>

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

<WRAP tip>
  * {{copsandrobber.pdf|Slides}}
  * [[https://www.youtube.com/watch?v=EzlWl7H0hmE| Vídeo]]
</WRAP>


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

<WRAP tip>
  * {{Teorema_de_Schur.pdf|Slides}} 
</WRAP>

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

<WRAP tip>
  * {{slidesramsey.pdf|Slides}}
  * {{https://drive.google.com/file/d/1JavtUN2zG9879AcOnm_7g4v0l1DQvKat/view?usp=sharing|Vídeo}} da apresentação 
</WRAP>


==== 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)

<WRAP tip>
  * {{semináriocombinando.pdf|Slides}}
  * {{suplementar10-03-2020.pdf|Arquivo suplementar}}
</WRAP>
Combinando

User Tools

Site Tools

Page Tools
