===== Conjectura do menor de Seymour =====


<WRAP round box 100%>
=== Definição ===
  * Uma **subcontração** de $G$ sobre $H$ é uma função $\gamma:X \to V(H)$ com:
      * Temos que $X \subset V(G)$.
      * $\gamma$ é sobrejeção.
      * $\gamma^{-1}(h) \subset V(G)$ é $G$-conexo.
      * Se existe uma $(h_1,h_2)$-aresta em $E(H)$, deve existir uma $(\gamma^{-1}h_1,\gamma^{-1}h_2)$-aresta.
      * Se $G,H$ são árvores com raízes $x$ e $y$ respectivamente, pedimos que $\gamma$ preserve a raiz, ou seja, $\gamma(x) = y$.
  * Uma subcontração é **própria** se não é isomorfismo entre $G$ e $H$.
  * Dizemos que $H \leq G$ quando existe $X \subset V(G)$ e subcontração $\gamma:X \to V(H)$.
      * $H<G$ quando $\gamma$ é própria.
</WRAP>

<WRAP round box 100%>
=== Conjectura de Seymour ===
//Um grafo é menor próprio de si mesmo.//
</WRAP>

Trivialmente falso para o caso infinito, existe também contra-exemplo não enumerável para esta conjectura. O caso infinito enumerável está em aberto. Estaremos interessado em árvores. Serão de particular interesse as seguintes definições:

<WRAP round box 100%>
=== Definição ===
  * O **raio natural** $N$ é simplesmente $N \doteq (\mathbb{N}, \{ \{n,n+1\} \, : \, n \in \mathbb{N} \})$. 
  * A **árvore binária** $2^{<\omega}$, sequências finitas de 0s e 1s, com arestas entre uma sequência $s$ e $s^\frown 0$ e $s^\frown 1$.
      * A raiz aqui é a sequência vazia.
      * Considere o seguinte algoritmo sobre uma árvore, cuja saída é um subconjunto de vértices.
          * Adicione a raiz no conjunto de vértices.
          * **Busca:** Para cada folha da árvore atual, busque dois de seus descendentes incomparáveis na ordem da árvore pelos quais passe um raio de $T$.
          * Adicione estes vértices ao conjunto.
          * Repita
      * Se naturais passos deste algoritmo podem ser seguidos em $T$, então $T$ tem $2^{<\omega}$ como menor.
      * Se $T$ não tem $2^{<\omega}$ como menor, então o passo de **busca** deve falhar eventualmente.
          * Deve haver $x$ vértice de $T$ pelo qual passa apenas um raio $R_x$. 
  * Uma **boa quasi-ordem** é uma quasi-ordem tal que, para toda sequência $x_0,x_1,...$ existem $i<j$ com $x_i \leq x_j$.
      * Toda sequência $x_n$, como acima, contém subsequência $x_{n_k}$ crescente.

Seja $(Q,\leq)$ uma boa quasi-ordem, um **$Q$-mapa sobre um grafo $G$** é simplesmente um mapa $\lambda : V(G) \to Q$.

</WRAP>

<WRAP round box 100%>
** Lema: ** Para cada $Q$-mapa $\lambda$ sobre $N$, existe subcontração $\gamma$ própria tal que para todo vértice $n \in \mathbb{N}$ existe $m \in \gamma^{-1}(n)$ com $\lambda(m) \geq \lambda (n)$.
</WRAP>

<WRAP round box 100%>
** Demonstração: ** Considere $L_k \doteq \{n \geq k \, : \, \lambda (n) \geq \lambda(k)\}$.
  * Suponha que eventualmente $L_k$ é infinito.
      * Seja então $n$ tal que $L_k$ é infinito para $k \geq n$.
      * Defina $\gamma \vert_{\{0,...,n\}} = \mathrm{id}_{\mathbb{N}}\vert_{\{0,...,n\}}$.
      * Defina $\gamma(n+1) \doteq n$ (para forçar que $\gamma$ é própria).
      * Seja $\gamma$ bem definida em $[0,k]$.
          * Mantenha o valor de $\gamma$ em $\gamma(k)$ enquanto $\overline{k} \notin L_k$.
          * Como $L_k$ é infinito, em tempo finito chegaremos a um valor $ \overline{k} \in L_k $, e então fazemos $\gamma(\overline{k}) \doteq \gamma(k)+1$ (mantendo a adjacência).
      * Por construção, encontramos uma subcontração nesse caso.
  * Se não temos que eventualmente $L_k$ é infinito, então ele é frequentemente finito.
      * Logo, temos sequência ascendente infinita $n_i \in \mathbb{N}$ com $L_{n_i}$ finitos.
      * Podemos supor que os conjuntos $L_i$ são disjuntos.
          * Pegue o maior elemento $k$ de $L_i$.
          * Defina $n_{i+1}$ como sendo um número $>k$ com $L_{n_{i+1}}$ finito.
      * Como $Q$ é boa quasi-ordem, devem haver $i<j$ com $\lambda(n_i) \leq \lambda(n_j)$.
          * Mas então $n_j \in L_i$, mas $n_j \in L_j$.
          * Nesse caso, $n_j \in L_I \cap L_j \neq \emptyset$, um absurdo.
      * Absurdo.
</WRAP>

<WRAP round box 100%>
** Teorema (Kruskall) ** Árvores finitas formam uma boa quasi-ordem sobre a relação de menor $\leq$.
</WRAP>

<WRAP round box 100%>
** Teorema :** Toda árvore (com raiz) enumerável tem subcontração própria.
</WRAP>
<WRAP round box 100%>
  * Suponha que $T$ não tem um raio.
      * Suponha que $T$ não tem nenhum vértice de grau infinito.
          * Nesse caso, $T$ tem todos os níveis finitos.
          * Pelo lema de König, teria raio.
          * Absurdo.
      * Concluímos que $T$ deve ter um vértice de grau infinito $x$.
          * Suponha que todo $x$ de ordem infinita tem descendente de ordem infinita.
              * Note que poderíamos definir um raio com estas hipóteses.
              * Absurdo.
      * Existe vértice((maximal na ordem na árvore com esta propriedade.)) $x$ de grau infinito que não tem descendentes de grau infinito.  
      * Removendo este vértice, ficamos com um grafo $T[V(T)\backslash\{x\}]$ com enumeráveis componentes conexas.
          * No máximo uma componente não está contida no conjunto de descendentes de $x$, que denotaremos por $\lfloor x \rfloor$.
              * Quando $x$ é a raiz de $T$, teremos exatamente o caso em que nenhuma componente está contida nos descendentes de $x$.
          * Note que as outras componentes são árvores finitas.
          * Enumere $s_i$ os sucessores de $x$.
          * Note que $t_i \doteq T[\lfloor s_i \rfloor]$ é uma sequência de árvores.
          * Pelo teorema de Kruskall, deve haver subsequência $(t_{n_k})_{k=1,2,...}$ $\leq$-crescente.
              * Temos então subcontrações $\gamma_i:V(t_{i+1}) \to V(t_i)$.
              * Considere $X$ como sendo os vértices de $T$ exceto pelos vértices de $t_{n_1}$.
              * Definimos $\gamma:X \to V(T)$ como sendo $\gamma_i$, onde se aplica, e a identidade onde nenhuma das $\gamma_i$ se aplicam.
              * Note que $X \subsetneq V(T)$, pois $s_1 \notin X$.
                  * Nesse caso, $\gamma$ não pode ser isomorfismo.
  * Suponha que $T$ pode ter um raio $N$, mas não tem $2^{<\omega}$ como menor.
      * Deve haver $x$ vértice de $T$ pelo qual passa apenas um raio $R_x$.
      * Note que $R_x[\lfloor x \rfloor]$ é um "raio de árvores finitas", ou seja, cada vértice $v$ desse raio é raiz de uma árvore finita $\lambda(v)$.
      * Nosso mapa $\lambda$ vai para o conjunto das árvores finitas, uma boa quasi-ordem pelo teorema de Kruskall.
      * Aplicando o lema 1, e usando as subcontrações dadas pela propriedade de que existe $m \in \gamma^{-1}(n)$ com $\lambda(n) \leq \lambda(m)$, isso quer dizer que a árvore com raiz $n$ é menor da árvore de raiz $m$.
      * Estas informações nos permitem definir uma subcontração própria, estendendo para a identidade onde não se aplicam.
  * Suponha que $T$ tem $2^{<\omega}$ como menor.
      * Colore $(s,s^\frown 0)$ de branco e $(s,s^\frown 0)$ de preto.
      * Contraia as arestas brancas.
      * O que temos é $\omega^{<\omega}$, uma árvore onde todos os vértices tem infinitos enumeráveis sucessores.
      * A árvore $\omega^{<\omega}$ contém todas as árvores enumeráveis como subgrafo, incluindo $T$.
      * Nesse caso, $T \leq \omega^{<\omega} \leq 2^{<\omega} < T$, e acabamos.
</WRAP>
----------
Referências : The self-minor conjecture for infinite trees, Julian Pott.