En matemáticas , la matroide de Vámos o cubo de Vámos es una matroide sobre un conjunto de ocho elementos que no se puede representar como una matriz sobre ningún campo . Lleva el nombre del matemático inglés Peter Vámos , quien lo describió por primera vez en un manuscrito inédito en 1968. [1]
Definición
El matroide de Vámos tiene ocho elementos, que pueden considerarse como los ocho vértices de un cubo o cuboide . El matroide tiene rango 4: todos los conjuntos de tres o menos elementos son independientes, y 65 de los 70 posibles conjuntos de cuatro elementos también son independientes. Las cinco excepciones son los circuitos de cuatro elementos en el matroid. Cuatro de estos cinco circuitos están formados por caras del cuboide (omitiendo dos caras opuestas). El quinto circuito conecta dos bordes opuestos del cuboide, cada uno de los cuales es compartido por dos de las cuatro caras elegidas.
Otra forma de describir la misma estructura es que tiene dos elementos para cada vértice del gráfico de diamante y un circuito de cuatro elementos para cada borde del gráfico de diamante.
Propiedades
- El matroide de Vámos es un matroide de pavimentación , lo que significa que todos sus circuitos tienen un tamaño al menos igual a su rango . [2]
- El matroide Vámos es isomorfo a su matroide dual , pero no es idénticamente auto-dual (el isomorfismo requiere una permutación no trivial de los elementos matroides). [2]
- El matroide de Vámos no se puede representar sobre ningún campo. Es decir, no es posible encontrar un espacio vectorial , y un sistema de ocho vectores dentro de ese espacio, de manera que la matroide de independencia lineal de estos vectores sea isomorfa a la matroide de Vámos. [3] De hecho, es una de las matroides no representables más pequeñas, [4] y sirvió como contraejemplo a una conjetura de Ingleton de que las matroides de ocho o menos elementos eran todas representables. [5]
- El matroide Vámos es un menor prohibido para las matroides representable sobre un campo, cuando sea tiene cinco o más elementos. [6] Sin embargo, no es posible probar en tiempo polinomial si es menor de un matroide dado, dado acceso a a través de un oráculo de la independencia . [7]
- El matroide de Vámos no es algebraico. Es decir, no existe una extensión de campo , y un conjunto de ocho elementos de , de modo que el grado de trascendencia de los conjuntos de estos ocho elementos es igual a la función de rango de la matroide. [8]
- El matroide Vámos no es un matroide que comparte secretos. [9] Las matroides de intercambio de secretos describen esquemas de intercambio de secretos "ideales" en los que cualquier coalición de usuarios que pueda obtener información sobre una clave secreta puede aprender la clave completa (estas coaliciones son los conjuntos dependientes de la matroide), y en los que el La información compartida no contiene más información de la necesaria para representar la clave. [10] Estos matroides también tienen aplicaciones en la teoría de la codificación . [11]
- El matroide Vámos no tiene adjunto. Esto significa que la celosía dual de la celosía geométrica del matroide de Vámos no se puede incrustar en orden en otra celosía geométrica del mismo rango. [12]
- El matroide Vámos se puede orientar . [13] En las matroides orientadas, una forma del teorema de Hahn-Banach se sigue de una cierta propiedad de intersección de los planos de la matroide; la matroide de Vámos proporciona un ejemplo de una matroide en la que la propiedad de intersección no es verdadera, pero el teorema de Hahn-Banach se mantiene, no obstante. [14]
- El polinomio de Tutte del matroide de Vámos es [15]
Referencias
- ^ Vámos, P. (1968), Sobre la representación de las estructuras independentistas.
- ^ a b Oxley, James G. (2006), "Ejemplo 2.1.22", Teoría Matroide , Textos de Graduados en Matemáticas de Oxford , 3 , Oxford University Press, p. 76, ISBN 9780199202508.
- ^ Oxley (2006) , págs. 170-172.
- ^ Oxley (2006) , Prop. 6.4.10, p. 196. Una prueba de representabilidad para cada matroide con menos elementos o el mismo número pero menor rango fue dada por Fournier, Jean-Claude (1970), "Sur la représentation sur un corps des matroïdes à sept et huit éléments", Comptes rendus de l'Académie des sciences , Sér. AB, 270 : A810 – A813, MR 0263665.
- ^ Ingleton, AW (1959), "Una nota sobre funciones de independencia y rango", Revista de la Sociedad Matemática de Londres , Segunda Serie, 34 : 49–56, doi : 10.1112 / jlms / s1-34.1.49 , MR 0101848.
- ^ Oxley (2006) , p. 511.
- ^ Seymour, PD ; Walton, PN (1981), "Detecting matroid minors", Journal of the London Mathematical Society , Segunda serie, 23 (2): 193-203, doi : 10.1112 / jlms / s2-23.2.193 , MR 0609098. 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.
- ^ Ingleton, AW; Main, RA (1975), "Las matroides no algebraicas existen", Boletín de la Sociedad Matemática de Londres , 7 : 144-146, doi : 10.1112 / blms / 7.2.144 , MR 0369110.
- ^ Seymour, PD (1992), "On secret-sharing matroids", Journal of Combinatorial Theory , Serie B, 56 (1): 69–73, doi : 10.1016 / 0095-8956 (92) 90007-K , MR 1182458.
- ^ Brickell, Ernest F .; Davenport, Daniel M. (1991), "Sobre la clasificación de los esquemas ideales para compartir secretos", Journal of Cryptology , 4 (2): 123-134, doi : 10.1007 / BF00196772.
- ^ Simonis, Juriaan; Ashikhmin, Alexei (1998), "Códigos casi afines", Diseños, códigos y criptografía , 14 (2): 179–197, doi : 10.1023 / A: 1008244215660 , MR 1614357.
- ^ Cheung, Alan LC (1974), "Adjoints of a geometry", Canadian Mathematical Bulletin , 17 (3): 363–365, corrección, ibid. 17 (1974), núm. 4, 623, doi : 10.4153 / CMB-1974-066-5 , Sr. 0373976.
- ^ Bland, Robert G .; Las Vergnas, Michel (1978), "Orientability of matroids", Journal of Combinatorial Theory , Serie B, 24 (1): 94-123, doi : 10.1016 / 0095-8956 (78) 90080-1 , MR 0485461.
- ^ Bachem, Achim; Wanka, Alfred (1988), "Teoremas de separación para matroides orientadas", Matemáticas discretas , 70 (3): 303–310, doi : 10.1016 / 0012-365X (88) 90006-4 , MR 0955127.
- ^ Merino, Criel; Ramírez-Ibáñez, Marcelino; Sánchez, Guadalupe Rodríguez (2012), El polinomio de Tutte de algunas matroides , arXiv : 1203.0090 , Bibcode : 2012arXiv1203.0090M.