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 circunferencia de un matroide es la circunferencia de su matroide dual . La circunferencia de Matroid generaliza la noción del ciclo más corto en un gráfico, la conectividad de borde de un gráfico, conjuntos de Hall en gráficos bipartitos, incluso conjuntos en familias de conjuntos y posición general de conjuntos de puntos. Es difícil de calcular, pero se puede tratar con parámetros fijos para matroides lineales cuando se parametrizan tanto por el rango de matroides como por el tamaño del campo de una representación lineal.
Ejemplos de
La terminología de "circunferencia" generaliza el uso de circunferencia en la 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 co-gráfica (o la circunferencia de una matroide gráfica) es igual a la conectividad de los bordes del gráfico subyacente, el número de bordes en un corte mínimo del gráfico. [1] La circunferencia de una matroide transversal da la cardinalidad de un conjunto de Hall mínimo 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 más pequeño en caso contrario. Las circunferencias de las 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 mínimo par, una subcolección de una familia de conjuntos que incluye un número par de copias de cada elemento del conjunto. [2]
Complejidad computacional
Determinar la circunferencia de una matroide binaria es NP-difícil . [4]
Además, la determinación de la circunferencia de una matroide lineal dada por una matriz que representa la matroide es W [1] -duro cuando se parametriza por la circunferencia o por el rango de la matroide, pero es manejable con parámetro fijo cuando se parametriza mediante una combinación de el tamaño del campo subyacente . [2]
Para una matroide arbitraria, dada 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 una matroide lineal real de rango r , con n elementos, descrita por un oráculo que da la orientación de cualquier r -tupla de elementos, requiereconsultas de Oracle 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 dado de elementos). [7]
Referencias
- ^ a b Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "Sobre la (co) circunferencia de una matroide conectada", Matemáticas aplicadas discretas , 155 (18): 2456–2470, doi : 10.1016 / j.dam.2007.06.015 , MR 2365057.
- ^ a b c Panolan, Fahad; Ramanujan, MS; Saurabh, Saket (2015), "Sobre la complejidad parametrizada de los problemas de circunferencia y conectividad en matroides lineales" (PDF) , en Dehne, Frank; Sack, Jörg-Rüdiger; Stege, Ulrike (eds.), Algoritmos y estructuras de datos: 14th International Symposium, WADS 2015, Victoria, BC, Canadá, 5-7 de agosto de 2015, Actas , Lecture Notes in Computer Science, 9214 , Springer, págs. 566–577 , doi : 10.1007 / 978-3-319-21840-3_47.
- ^ Donoho, David L .; Elad, Michael (2003), "Representación óptimamente escasa en diccionarios generales (no ortogonales) mediante la minimización de ℓ 1 ", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 100 (5): 2197-2202, doi : 10.1073 / pnas.0437847100 , PMC 153464 , PMID 16576749.
- ^ Cho, Chen y Ding (2007) observan que esto es un corolario de un resultado de Alexander Vardy en la teoría de la codificación: Vardy, Alexander (1997), "La intratabilidad de calcular la distancia mínima de un código", IEEE Transactions on Information Theory , 43 (6): 1757-1766, doi : 10.1109 / 18.641542 , MR 1481035.
- ^ Jensen, Per M .; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedad matroide", SIAM Journal on Computing , 11 (1): 184-190, doi : 10.1137 / 0211014 , MR 0646772.
- ^ Erickson, J .; Seidel, R. (1995), "Mejores límites inferiores para detectar degeneraciones afines y esféricas", Geometría discreta y computacional , 13 (1): 41–57, doi : 10.1007 / BF02574027 , MR 1300508.
- ^ Hausmann, D .; Korte, B. (1981), "Definiciones algorítmicas versus axiomáticas de matroides", Programación matemática en Oberwolfach (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979) , Estudios de programación matemática, 14 , págs. 98-111, doi : 10.1007 / BFb0120924 , MR 0600125.