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