http://meet.google.com/ujs-erif-gef
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.