Grafos y conjuntos parcialmente ordenados que admiten un modelo CPT

Abstract

Los posets que admiten un modelo de contención utilizando intervalos de una línea, los cuales se denominan posets CI (containment order of intervals) y se sabe que son los posets con dimensión como máximo 2, son exactamente aquellos cuyos grafos de comparabilidad pertenecen a la clase conocida como grafos de permutación. Aquí estudiaremos también aquellos posets que admiten un modelo de contención mapeando vértices en caminos de un árbol, que se denominan posets CPT (containment order of paths in a tree) y claramente constituyen una super clase de los posets CI. Se han encontrado diferencias notables entre los posets CI y los CPT. Primero, la dimensión de los posets CI está acotada superiormente por 2, pero la dimensión de los posets CPT no está acotada, lo cual significa que para cada entero positivo d existe algún poset CPT con una dimensión mayor que d. En segundo lugar, cualquier poset CI admite un modelo CI que utiliza caminos no triviales. Sin embargo, existen posets CPT que requieren el uso de caminos triviales en cualquier modelo CPT. Y tercero, el hecho de ser poset CI es una invariante de comparabilidad pero el hecho de ser CPT no lo es. Esto significa que un mismo grafo puede ser el grafo de comparabilidad de un poset que es CPT y de otro poset que no es CPT. Determinar clases de posets en las que ser CPT es un invariante de comparabilidad y comprender la estructura detrás de esto es un problema desafiante. Resolveremos este problema dentro de una subclase de posets CPT. Al contrario de las diferencias anteriores, ambas clases son hereditarias, lo que significa que cualquier subposet de un poset CI (respectivamente CPT) también es CI (respectivamente CPT). En consecuencia, admiten una caracterización por una familia de subposets prohibidos minimales. Es bien sabido que las estructuras prohibidas para ser CI son los posets 3-irreducibles, es decir, los posets minimales con dimensión 3. En este trabajo, determinamos cuáles de los posets 3-irreducibles son CPT. Además, usándolos, describimos una familia infinita de posets que son subposets prohibidos minimales para ser CPT. La familia completa de subposets prohibidos minimales necesarios para caracterizar la clase de posets CPT es desconocida. Finalmente, centrándonos en los aspectos algorítmicos de los problemas de reconocimiento, un poset CI puede reconocerse en tiempo lineal. Determinar la complejidad temporal de reconocer posets CPT es un problema abierto. En este trabajo, investigamos (y resolvemos) el problema de caracterización y reconocimiento en la clase de posets cuyos grafos de comparabilidad son k-trees (grafos completos de k vértices o grafos que contienen un vértice cuya vecindad induce un grafo completo con k vértices y cuya eliminación da como resultado un k-tree).