En la teoría de matroides , una disciplina matemática, la circunferencia de un matroide es el tamaño de su circuito más pequeño o conjunto dependiente. La circunferencia de un matroide es la circunferencia de su matroide dual . La circunferencia de un matroide generaliza la noción del ciclo más corto en un grafo, la conectividad de los bordes de un grafo, los conjuntos de Hall en grafos bipartitos , los conjuntos pares en familias de conjuntos y la posición general de los conjuntos de puntos. Es difícil de calcular, pero manejable con parámetros fijos para matroides lineales cuando se parametrizan tanto por el rango del matroide como por el tamaño del campo de una representación lineal.
La terminología "circunferencia" generaliza el uso de circunferencia en la teoría de grafos , es decir, la longitud del ciclo más corto en un grafo: la circunferencia de un matroide gráfico es la misma que la circunferencia de su grafo subyacente. [1]
La circunferencia de otras clases de matroides también corresponde a importantes problemas combinatorios. Por ejemplo, la circunferencia de un matroide cográfico (o la circunferencia de un matroide gráfico) es igual a la conectividad de las aristas del grafo subyacente, el número de aristas en un corte mínimo del grafo. [1] La circunferencia de un matroide transversal da la cardinalidad de un conjunto Hall mínimo en un grafo bipartito: este es un conjunto de vértices en un lado de la bipartición que no forma el conjunto de puntos finales de una coincidencia en el grafo. [2]
Cualquier conjunto de puntos en el espacio euclidiano da lugar a un matroide lineal real al interpretar las coordenadas cartesianas de los puntos como vectores de una representación matroide . La circunferencia del matroide resultante es igual a uno más la dimensión del espacio cuando el conjunto subyacente de puntos está en la posición general , y es menor en caso contrario. Las circunferencias de los matroides lineales reales también surgen en la detección comprimida , donde el mismo concepto se conoce como la chispa de una matriz. [3]
La circunferencia de un matroide binario da la cardinalidad de un conjunto par mínimo, una subcolección de una familia de conjuntos que incluye un número par de copias de cada elemento del conjunto. [2]
Determinar la circunferencia de un matroide binario es NP-difícil . [4]
Además, determinar la circunferencia de un matroide lineal dada por una matriz que representa el matroide es W[1]-difícil cuando se parametriza por la circunferencia o por el rango del matroide, pero manejable con parámetros fijos cuando se parametriza por una combinación del rango y el tamaño del campo subyacente . [2]
Para un matroide arbitrario, dado por un oráculo de independencia , es imposible encontrar la circunferencia usando un número subexponencial de consultas de matroide. [5] De manera similar, para un matroide lineal real de rango r , con n elementos, descrito por un oráculo que da la orientación de cualquier r -tupla de elementos, requiere consultas de oráculo para determinar la circunferencia. [6]
También se han considerado cálculos que utilizan un oráculo de circunferencia (un oráculo que informa el subconjunto dependiente más pequeño de un conjunto dado de elementos). [7]
