Borja soto, Jerson ManuelNegrete Madera, Laura Vanesa2022-09-022023-09-022022-09-022022-09-02https://repositorio.unicordoba.edu.co/handle/ucordoba/6529En este trabajo estudiamos la complejidad de propiedades de grafos no evasivas, así como la evasividad de algunas propiedades de hipergrafos. Además, en el caso de las propiedades no evasivas damos estrategias que permiten obtener una cota para la complejidad de las mismas. En cuanto a propiedades de hipergrafos, mostramos una generalización del teorema de Yao sobre propiedades de grafos bipartitos, a propiedades de hipergrafos k−partitos k−uniformes.In this work we show the complexity of some known non-evasive graph properties, as well as the evasiveness of some hypergraph properties. Furthermore, in the case of non-evasive properties, we show the strategies that allow us to obtain an upper bound for their complexity. For hypergraph properties, we prove a generalization to k−partite hipergraph properties, of Yao’s theorem on bipartite graph properties.Resumen................................................. IIIAgradecimientos.......................................V1. Preliminares......................................... 31.1. Propiedades de grafos y la conjetura de evasividad . . . . . . . . . . . 31.2. Complejos simpliciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3. Enfoque topológico a la evasividad . . . . . . . . . . . . . . . . . . . . . 72. Propiedades no evasivas......................................... 92.1. Propiedad de Carter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2. Propiedad de Kleitman . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3. Grafos Escorpión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4. Propiedad no evasiva más pequeña . . . . . . . . . . . . . . . . . . . . . 142.5. Generalizaciones de la propiedad de Kleitman . . . . . . . . . . . . . . 182.5.1. Primera generalización de la propiedad de Kleitman . . . . . . 192.5.2. Segunda generalización de la propiedad de Kleitman . . . . . . 212.5.3. Tercera generalización de la propiedad de Kleitman . . . . . . . 243. Propiedades de hipergrafos.................................. 273.1. Hipergrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2. Extensión a hipergrafos de la propiedad de ser bipartito . . . . . . . . . 294. Conclusiones............................................. 34Bibliografía..................................................... 35application/pdfspaCopyright Universidad de Córdoba, 2022Trabajo de grado - Maestríainfo:eu-repo/semantics/embargoedAccessAtribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)ComplejidadEvasividadPropiedades de grafosPropiedades de hipergrafosComplexityEvasivenessGraph propertiesHypergraph properties.