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.

Conjectura de Seymour

Um grafo é menor próprio de si mesmo.

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,\ldots$ 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$.

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

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,\ldots,n\}} = \mathrm{id}_{\mathbb{N}}\vert_{\{0,\ldots,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.

Teorema (Kruskall) Árvores finitas formam uma boa quasi-ordem sobre a relação de menor $\leq$.

Teorema : Toda árvore (com raiz) enumerável tem subcontração própria.

• 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¹⁾ $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,\ldots}$ $\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.