Reconstrucción de coloraciones a partir de sus conjuntos homogéneos
No Thumbnail Available
Date
2023-02-14
Authors
Advisors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
Sea φ una coloración en dos colores de los pares de elementos de un conjunto X numerable. Esto es, una partición de X[2] en dos conjuntos. En 1, fue definido el problema de reconstrucción de coloraciones a partir de sus conjuntos homogéneos. Este trabajo contiene una continuación de la investigación en dicho artículo y hemos logrado responder algunas de las preguntas formuladas allí.
En primer lugar, definimos el concepto de coloraciones fuertemente reconstruibles y mostramos que es una instancia más especializada del concepto de coloraciones reconstruibles. En segundo lugar, pero de mayor importancia es el trabajo que se presenta en el Capítulo 3 de esta tesis. Allí, estudiamos la función r, definida en 1 de la siguiente manera,
r(φ) = {|A| : A ̸ = ∅, A induce una reconstrucción de φ},
la cual toma valores en los números naturales, o puede ser infinita. Demostramos que si X es infinito, los únicos valores posibles para r(φ) son 1, 4 o א0. La demostración de esta afirmación es el principal resultado que se obtuvo en esta investigación, ver Teorema (3.15). Primero fueron establecidos varios resultados auxiliares dentro de los cuales se destaca el Teorema (3.13) que dice que dada una coloración φ : X[2] → 2 sobre un conjunto infinito X, si A (que induce una reconstrucción de φ) contiene tres aristas que forman un triángulo (a, b, b, c, a, c ∈ A) entonces |A| = א0.
Bajo las condiciones requeridas para el teorema principal, las coloraciones que satisfacen r(φ) = 1 o r(φ) = 4 corresponden exactamente con coloraciones que poseen ciertas subestructuras conocidas como pares críticos y ciclos críticos, respectivamente.
Por otra parte, en el Capítulo 4, examinamos la estructura interna de colecciones de coloraciones que comparten la lista de conjuntos homogéneos. Estos son unos primeros pasos para establecer un nuevo enfoque con el cual estudiar el problema de reconstrucción de coloraciones.
Description
Keywords
Coloración, Coloración reconstruible, Par crítico, Ciclo crítico, Reconstrucción mínima de una coloración, Coloración fuertemente reconstruible, Conjunto que induce una reconstrucción