Hamiltonian Cycles in Kneser Graphs

O grafo Kneser K(n, k) é o grafo cujos vértices são todos os subconjuntos com k elementos de um conjunto que tem n elementos e dois vértices são unidos por uma aresta se o par correspondente de conjuntos de tamanho k é disjunto. O grafo ímpar Ok é o caso especial do grafo Kneser quando n=2k + 1. Uma conjectura de Lovász afirma que Ok tem um caminho hamiltoniano para k ≥ 1. Anteriormente, a conjectura de Lovász tinha sido provada para todo k ≤ 13. Nós melhoramos estes valores mostrando que Ok tem um caminho hamiltoniano para 14 ≤ k ≤ 17. Adicionalmente, estabelecemos quão próximos os grafos ímpares estão de serem hamiltonianos: Ok tem um passeio gerador fechado ou uma trilha geradora fechada no qual cada vértice aparece duas vezes no máximo.