Vamos matroid

En matemáticas , el matroide de Vámos o cubo de Vámos es un matroide sobre un conjunto de ocho elementos que no se puede representar como una matriz sobre ningún cuerpo . Recibe su 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 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 conjuntos posibles de cuatro elementos también son independientes. Las cinco excepciones son circuitos de cuatro elementos en el matroide. Cuatro de estos cinco circuitos están formados por caras del cuboide (omitiendo dos caras opuestas). El quinto circuito conecta dos aristas opuestas del cuboide, cada una de las cuales es compartida 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 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 autodual (el isomorfismo requiere una permutación no trivial de los elementos del matroide). ^[2]
El matroide Vámos no puede representarse sobre ningún cuerpo. Es decir, no es posible encontrar un espacio vectorial y un sistema de ocho vectores dentro de ese espacio, de modo que el matroide de independencia lineal de estos vectores sea isomorfo al matroide Vámos. ^[3] De hecho, es uno de los matroides no representables más pequeños, ^[4] y sirvió como contraejemplo a una conjetura de Ingleton de que los matroides de ocho elementos o menos eran todos representables. ^[5]
El matroide Vámos es un menor prohibido para los matroides representables sobre un cuerpo , siempre que tenga cinco o más elementos. ^[6] Sin embargo, no es posible comprobar en tiempo polinomial si es un menor de un matroide dado , dado el acceso a través de un oráculo de independencia . ^[7] ${\estilo de visualización F}$ ${\estilo de visualización F}$ ${\estilo de visualización M}$ ${\estilo de visualización M}$
El matroide Vámos no es algebraico, es decir, no existe una extensión de cuerpo y un conjunto de ocho elementos de , tales que el grado de trascendencia de los conjuntos de estos ocho elementos sea igual a la función de rango del matroide. ^[8] ${\estilo de visualización L/K}$ ${\estilo de visualización L}$
El matroide Vámos no es un matroide de intercambio de secretos. ^[9] Los matroides de intercambio de secretos describen esquemas de intercambio de secretos "ideales" en los que cualquier coalición de usuarios que pueda obtener cualquier información sobre una clave secreta puede aprender la clave completa (estas coaliciones son los conjuntos dependientes del matroide), y en los que la información compartida no contiene más información que 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 adjuntos, lo que significa que la red dual de la red geométrica del matroide Vámos no puede ser incorporada en otra red geométrica del mismo rango. ^[12]
El matroide Vámos puede estar orientado . ^[13] En los matroides orientados, una forma del teorema de Hahn-Banach se deduce de una cierta propiedad de intersección de los planos del matroide; el matroide Vámos proporciona un ejemplo de un matroide en el que la propiedad de intersección no es verdadera, pero el teorema de Hahn-Banach se cumple de todos modos. ^[14]
El polinomio de Tutte del matroide Vámos es ^[15]
$x^{4}+4x^{3}+10x^{2}+15x+5xy+15y+10y^{2}+4y^{3}+y^{4}.$

Referencias

^ Vámos, P. (1968), Sobre la representación de las estructuras independentistas.
^ ab Oxley, James G. (2006), "Ejemplo 2.1.22", Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, pág. 76, ISBN 9780199202508.
^ Oxley (2006), págs. 170-172.
^ Oxley (2006), Proposición 6.4.10, pág. 196. 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, SEÑOR 0263665.
^ Ingleton, AW (1959), "Una nota sobre funciones de independencia y rango", Journal of the London Mathematical Society , Segunda serie, 34 : 49–56, doi :10.1112/jlms/s1-34.1.49, MR 0101848.
^ Oxley (2006), pág. 511.
^ Seymour, PD ; Walton, PN (1981), "Detección de menores matroides", Journal of the London Mathematical Society , Segunda serie, 23 (2): 193–203, doi :10.1112/jlms/s2-23.2.193, MR 0609098Jensen , Per M.; Korte, Bernhard (1982), "Complejidad de los algoritmos de propiedades de matroides", SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR 0646772.
^ Ingleton, AW; Main, RA (1975), "Existen matroides no algebraicos", Boletín de la Sociedad Matemática de Londres , 7 : 144–146, doi :10.1112/blms/7.2.144, MR 0369110.
^ Seymour, PD (1992), "Sobre matroides que comparten secretos", 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 de intercambio de 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), "Adjuntos de una geometría", Canadian Mathematical Bulletin , 17 (3): 363–365, corrección, ibid. 17 (1974), núm. 4, 623, doi : 10.4153/CMB-1974-066-5 , MR 0373976.
^ Bland, Robert G. ; Las Vergnas, Michel (1978), "Orientabilidad de matroides", 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 orientados", 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.