Uma assimetria curiosa em boas caracterizações

Existem alguns teoremas, principalmente na teoria dos grafos e na otimização combinatória, que são frequentemente referidos como boas caracterizações. Eles tipicamente colocam uma propriedade em , mostrando que uma propriedade é válida ou existe algum obstáculo bem identificado que a impede de ser mantida. Muitas vezes, eles são apresentados como teoremas min-max. Consulte a pergunta anterior. Problemas de otimização com boa caracterização, mas sem algoritmo de tempo polinomial. $NP\cap co-NP$

Aqui estão dois exemplos clássicos de boas caracterizações:

Um gráfico bipartido tem uma correspondência do tamanho , ou há menos de vértices que cobrem todas as arestas. A existência de tal cobertura é um obstáculo trivial que exclui a correspondência. Se esse obstáculo não existe, a correspondência deve existir, essa é a parte não trivial, conhecida como Teorema de Konig. $k$ $k$
Ou existe um de fluxo de valor em um gráfico de fluxo, ou então há uma corte com capacidade inferior a . Mais uma vez, a existência de tal corte é um obstáculo trivial, pois o fluxo não pode passar. A parte não trivial é que a ausência do obstáculo já garante a existência do fluxo do valor , que é equivalente ao Teorema de Max Flow Min Cut. $s-t$ $F$ $s-t$ $F$ $F$

O que acho uma característica curiosa nesses (e em muitos outros) resultados é que eles mostram uma assimetria bem visível na dureza da prova entre as duas direções da equivalência. Geralmente, é fácil, ou mesmo trivial, provar que o obstáculo exclui a propriedade considerada. Por outro lado, é muito mais difícil provar que o obstáculo fácil / trivial é o único obstáculo, no sentido de que, uma vez que não existe, a propriedade deve permanecer.

Não estou ciente de uma boa explicação por que esse tipo de assimetria é tão comum. Não parece necessário a priori. Nota: não se deixe enganar pelo fato de que os exemplos acima são casos especiais de dualidade de programação linear. Existem outros exemplos que não têm nada a ver com programação linear.

Pergunta: Você conhece alguma boa caracterização que não se enquadre nessa categoria? (É certo que ele é vagamente definido, mas talvez a idéia tenha sido concretizada.) Em outras palavras, estou procurando um teorema que coloque uma propriedade em , capturando todos os obstáculos possíveis da propriedade, mas eles são nem todos os obstáculos fáceis / triviais. $NP\cap co-NP$

cc.complexity-theory graph-theory co.combinatorics Andras Farago
fonte

Eu gostaria de ver esses exemplos que não são casos especiais de dualidade? Porque, com seus exemplos, as direções fáceis são a dualidade fraca, o que é sempre trivial para provar, e as direções difíceis são a dualidade forte, o que é um fato mais profundo.

Sasho Nikolov

O que seria um exemplo de um obstáculo "não trivial"?

András Salamon

Aqui está um exemplo de um obstáculo não trivial para uma propriedade: um gráfico não pode ter um número cromático se não contiver um subgrafo construtível por , consulte a construção de Hajos [ en.wikipedia.org/wiki/Hajós_construction] . Embora o número cromático não esteja em (a menos que ), ele ainda mostra um exemplo de como poderia ser um obstáculo não trivial. Também postarei exemplos que não são casos especiais de dualidade de LP, mas eles não se encaixam em um comentário.

\geq k

$\geq k$

k

$k$

N P \cap c o - N P

$NP\cap co-NP$

N P = c o - N P

$NP=co-NP$

Andras Farago

Eu acho que isso pode muito bem ser uma conseqüência de provas sendo feitas por pessoas. Encontramos uma (fácil) desigualdade ou implicação e perguntamos se a outra direção (ou desigualdade) também é verdadeira. Para todos nós sabemos que pode haver muitas implicações que são difíceis para os dois lados, mas nós simplesmente não podemos encontrá-los :)

Daniello

(Isso é para responder ao comentário de Sasho Nikolov, mas é muito longo para o campo de comentários, então eu o posto como resposta.)

Os dois exemplos da pergunta original são casos especiais da dualidade do LP. Existem muitos exemplos semelhantes, mas pode-se argumentar que todos eles herdam a assimetria da dualidade do LP. É fácil provar a dualidade fraca do LP (ele fornece o "obstáculo trivial"), enquanto a dualidade forte é mais profunda, provando que o obstáculo trivial é o único obstáculo. Nesse sentido, os exemplos que são "filhos do LP" podem ser vistos como apenas encarnações diferentes do mesmo exemplo central.

Aqui estão, no entanto, alguns outros casos que (que eu saiba) não estão relacionados ao LP. Os exemplos abaixo são todos da teoria dos grafos, mas outros campos provavelmente também contêm padrões semelhantes.

$k, l, d$ $k$ $l$ $d$ $k\leq l \leq d$ . Como é (quase) trivial provar que esses parâmetros sempre satisfazem as desigualdades, a violação de pelo menos uma desigualdade é um obstáculo trivial para a existência de tal gráfico. A outra direção, de que esse gráfico sempre existe, não é trivial. (Veja o livro de Bollobas, "Teoria dos grafos extremais", teorema 1.5. Nota: a forma como é apresentada é um pouco mais complicada, usando mais desigualdades, porque também usa outro parâmetro, o número de vértices. Mas essa versão mais simples pode ser extraído dele, para mostrar a natureza essencial de que aqui novamente o obstáculo trivial é o único obstáculo.)
$\geq 3$ $K_5$ $K_{3,n-3}$
$d_1\geq\ldots\geq d_n$ $k\geq 2$ $k$ $d_1\geq\ldots\geq d_n$ $d_n\geq k$ , o que também é trivialmente necessário, pois a conectividade da borda é delimitada de cima pelo grau mínimo. Uma vez satisfeitas essas condições essencialmente triviais, o gráfico desejado sempre existe.
$G$ $H$ $G$ $H$ $G$ $|E(H)|$ $|E(G)|$ $g$ $H$ $g$ $|V(G)|-1$

Andras Farago
fonte

Uma assimetria curiosa em boas caracterizações

Respostas: