The complexity of recognizing graph properties and the evasiveness conjecture

Deciding graph properties—Boolean functions invariant under graph isomorphism—is a foundational challenge in computational complexity. A central question is determining the minimum number of edge queries required to verify such properties in the worst case. A property is evasive if resolving it demands inspecting every potential edge. While most graph properties are non-evasive, the Evasiveness Conjecture posits that all monotone graph properties (those preserved under edge addition) are evasive. Though unresolved in general, this conjecture is proven for graphs with prime power vertex counts, a landmark result deeply tied to algebraic and topological methods. This work synthesizes advances in the Evasiveness Conjecture, providing a detailed exposition of its proof for prime power-sized graphs. Our analysis reveals unexpected connections to finite group theory and simplicial topology, underscoring how combinatorial problems of this nature straddle diverse mathematical domains. By unifying these perspectives, we clarify the conjecture’s current boundaries and the role of symmetry in computational hardness.

• Autores: Mantilla Acosta, Rafael José
• Tipo de recurso: Trabajo de grado de pregrado
• Fecha de publicación: 2025
• Institución: Universidad de los Andes
• Repositorio: Séneca: repositorio Uniandes
• Idioma: eng
• OAI Identifier: oai:repositorio.uniandes.edu.co:1992/76183
• Acceso en línea: https://hdl.handle.net/1992/76183
• Palabra clave: Evasiveness Conjecture; Monotone graph properties; Deterministic query complexity; Topological methods in complexity; Matemáticas
• Rights: openAccess
• License: Attribution 4.0 International