Plan de asociación

La teoría de los esquemas de asociación surgió en estadística , en la teoría del diseño experimental para el análisis de varianza . ^{[ 1 ] [ 2 ] [ 3 ]} En matemáticas , los esquemas de asociación pertenecen tanto al álgebra como a la combinatoria . En combinatoria algebraica , los esquemas de asociación proporcionan un enfoque unificado para muchos temas, por ejemplo, diseños combinatorios y la teoría de códigos correctores de errores . ^{[ 4 ] [ 5 ]} En álgebra, la teoría de los esquemas de asociación generaliza la teoría de caracteres de representaciones lineales de grupos . ^{[ 6 ] [ 7 ] [ 8 ]}

Un esquema de asociación de n clases consiste en un conjunto X junto con una partición S de X × X en n  +  1 relaciones binarias , R ₀ , R ₁ , ..., R _n que satisfacen:

• ${\displaystyle R_{0}=\{(x,x):x\in X\}}$; se denomina relación de identidad .
• Definición${\displaystyle R^{*}:=\{(x,y):(y,x)\in R\}}$, si R está en S , entonces R* está en S.
• Si${\displaystyle (x,y)\in R_{k}}$, el número de${\displaystyle z\in X}$de tal manera que${\displaystyle (x,z)\in R_{i}}$y${\displaystyle (z,y)\in R_{j}}$es una constante${\displaystyle p_{ij}^{k}}$Dependiendo de${\displaystyle i}$,${\displaystyle j}$,${\displaystyle k}$pero no en la elección particular de${\displaystyle x}$y${\displaystyle y}$.

Un esquema de asociación es conmutativo si${\displaystyle p_{ij}^{k}=p_{ji}^{k}}$a pesar de${\displaystyle i}$,${\displaystyle j}$y${\displaystyle k}$La mayoría de los autores dan por sentada esta propiedad. Sin embargo, cabe señalar que, si bien la noción de esquema de asociación generaliza la noción de grupo, la noción de esquema de asociación conmutativo solo generaliza la noción de grupo conmutativo .

Un esquema de asociación simétrico es aquel en el que cada${\displaystyle R_{i}}$es una relación simétrica . Es decir:

• Si ( x , y ) ∈ R _i , entonces ( y , x ) ∈ R _i . (O equivalentemente, R * = R .)

Todo esquema de asociación simétrico es conmutativo.

Dos puntos x e y se denominan asociados i- ésimos si${\displaystyle (x,y)\in R_{i}}$La definición establece que si x e y son asociados i -ésimos, entonces también lo son y y x . Cada par de puntos son asociados i -ésimos para exactamente uno.${\displaystyle i}$Cada punto es su propio asociado cero, mientras que los puntos distintos nunca son asociados cero. Si x e y son asociados k, entonces el número de puntos${\displaystyle z}$que son ambos asociados de${\displaystyle x}$y j asociados de${\displaystyle y}$es una constante${\displaystyle p_{ij}^{k}}$.

El término esquema de asociación se debe a ( Bose y Shimamoto 1952 ) , pero el concepto ya estaba presente en ( Bose y Nair 1939 ) . ^{[ 9 ]} Estos autores estudiaban lo que los estadísticos han denominado diseños de bloques incompletos parcialmente balanceados (PBIDD). El tema se convirtió en objeto de interés algebraico con la publicación de ( Bose y Mesner 1959 ) y la introducción del álgebra de Bose-Mesner . La contribución más importante a la teoría fue la tesis de Ph. Delsarte ( Delsarte 1973 ) , quien reconoció y utilizó plenamente las conexiones con la teoría de la codificación y la teoría del diseño. ^{[ 10 ]}

DG Higman ha estudiado una generalización denominada configuraciones coherentes.

• ${\displaystyle p_{00}^{0}=1}$, es decir, si${\displaystyle (x,y)\in R_{0}}$entonces${\displaystyle x=y}$y el único${\displaystyle z}$de tal manera que${\displaystyle (x,z)\in R_{0}}$es${\displaystyle z=x}$.
• ${\displaystyle \sum _{i=0}^{k}p_{ii}^{0}=|X|}$; esto se debe a que el${\displaystyle R_{i}}$dividir${\displaystyle X}$.

Las matrices de adyacencia${\displaystyle A_{i}}$de los gráficos${\displaystyle \left(X,R_{i}\right)}$generar un álgebra conmutativa y asociativa${\displaystyle {\mathcal {A}}}$(sobre los números reales o complejos ) tanto para el producto matricial como para el producto de Hadamard (elemento a elemento) . El álgebra formada con el producto matricial se denomina álgebra de Bose-Mesner del esquema de asociación.

Dado que las matrices en${\displaystyle {\mathcal {A}}}$son simétricas y conmutan entre sí, pueden diagonalizarse simultáneamente. Por lo tanto,${\displaystyle {\mathcal {A}}}$es semisimple y tiene una base única de idempotentes primitivos.${\displaystyle J_{0},\ldots ,J_{n}}$.

Hay otra álgebra de${\displaystyle (n+1)\times (n+1)}$matrices que es isomorfa a${\displaystyle {\mathcal {A}}}$y suele ser más fácil trabajar con él.

• El esquema de Johnson , denotado por J ( v , k ), se define de la siguiente manera. Sea S un conjunto con v elementos. Los puntos del esquema J ( v , k ) son los${\displaystyle {v \choose k}}$subconjuntos de S con k elementos. Dos subconjuntos de k elementos A , B de S son asociados i cuando su intersección tiene tamaño k  − i . 
• El esquema de Hamming , denotado por H ( n , q ), se define de la siguiente manera. Los puntos de H ( n , q ) son las n - tuplas ordenadas q ⁿ sobre un conjunto de tamaño q . Dos n -tuplas x , y se denominan i -ésimas asociadas si no coinciden exactamente en i coordenadas. Por ejemplo, si x = (1,0,1,1), y = (1,1,1,1), z = (0,0,1,1), entonces x e y son 1.ª asociadas, x y z son 1.ª asociadas e y y z son 2.ª asociadas en H (4,2).
• Un grafo regular por distancia , G , forma un esquema de asociación definiendo dos vértices como asociados i si su distancia es i .
• Un grupo finito G produce un esquema de asociación en${\displaystyle X=G}$, con una clase R _g para cada elemento del grupo, como sigue: para cada${\displaystyle g\in G}$dejar${\displaystyle R_{g}=\{(x,y)\mid x=g*y\}}$dónde${\displaystyle *}$es la operación de grupo . La clase de la identidad del grupo es R ₀ . Este esquema de asociación es conmutativo si y solo si G es abeliano .
• Un esquema de asociación específico de 3 clases: ^{[ 11 ]}

Sea A (3) el siguiente esquema de asociación con tres clases asociadas en el conjunto X = {1,2,3,4,5,6}. La entrada ( i , j ) es s si los elementos i y j están en relación R _s .

El esquema de Hamming y el esquema de Johnson son de gran importancia en la teoría clásica de la codificación .

En la teoría de la codificación , la teoría de esquemas de asociación se centra principalmente en la distancia de un código . El método de programación lineal proporciona cotas superiores para el tamaño de un código con una distancia mínima dada , y cotas inferiores para el tamaño de un diseño con una fuerza dada. Los resultados más específicos se obtienen cuando el esquema de asociación subyacente satisface ciertas propiedades polinómicas ; esto nos introduce en el ámbito de los polinomios ortogonales . En particular, se derivan algunas cotas universales para códigos y diseños en esquemas de asociación de tipo polinómico.

En la teoría clásica de la codificación , al tratar con códigos en un esquema de Hamming , la transformada de MacWilliams involucra una familia de polinomios ortogonales conocidos como polinomios de Krawtchouk . Estos polinomios proporcionan los valores propios de las matrices de relación de distancia del esquema de Hamming .

• Diseño de bloques
• Álgebra de Bose-Mesner
• Diseño combinatorio

• Bailey, Rosemary A. (2004), Esquemas de asociación: experimentos diseñados, álgebra y combinatoria , Cambridge University Press, ISBN 978-0-521-82446-0, MR 2047311 (Los capítulos del borrador preliminar están disponibles en línea ).
• Bannai, Eiichi; Ito, Tatsuro (1984), Combinatoria algebraica I: Esquemas de asociación , Menlo Park, CA: Benjamin/Cummings, ISBN 0-8053-0490-8, MR 0882540 
• Bose, RC ; Mesner, DM (1959), "Sobre álgebras asociativas lineales correspondientes a esquemas de asociación de diseños parcialmente equilibrados" , Annals of Mathematical Statistics , 30 (1): 21–38 , doi : 10.1214/aoms/1177706356 , JSTOR 2237117 , MR 0102157  
• Bose, R.  C.; Nair, K.  R. (1939), "Diseños de bloques incompletos parcialmente equilibrados", Sankhyā , 4 (3): 337– 372, JSTOR 40383923 
• Bose, R.  C.; Shimamoto, T. (1952), "Clasificación y análisis de diseños de bloques incompletos parcialmente equilibrados con dos clases asociadas", Journal of the American Statistical Association , 47 (258): 151–184 , doi : 10.1080/01621459.1952.10501161
• Camion, P. (1998), "18. Códigos y esquemas de asociación: propiedades básicas de los esquemas de asociación relevantes para la codificación", en Pless, VS; Huffman, WC; Brualdi, RA (eds.), Handbook of Coding Theory , vol.  1, Elsevier, pp.  1441–, ISBN 978-0-444-50088-5
• Delsarte, P. (1973), "Un enfoque algebraico de los esquemas de asociación de la teoría de la codificación", Philips Research Reports (Suplemento n.º 10), OCLC 641852316 
• Delsarte, P.; Levenshtein, VI (1998). "Esquemas de asociación y teoría de la codificación". IEEE Transactions on Information Theory . 44 (6): 2477– 2504. doi : 10.1109/18.720545 .
• Dembowski, P. (1968), Geometrías finitas , Springer, ISBN 978-3-540-61786-0
• Godsil, CD (1993), Combinatoria algebraica , Nueva York: Chapman and Hall, ISBN 0-412-04131-6, MR 1220704 
• MacWilliams, FJ; Sloane, NJA (1977), The Theory of Error Correcting Codes , North-Holland Mathematical Library, vol.  16, Elsevier, ISBN 978-0-444-85010-2
• Street, Anne Penfold ; Street, Deborah J. (1987), Combinatoria del diseño experimental , Oxford UP [Clarendon], ISBN 0-19-853256-3

• van Lint, JH; Wilson, RM (1992), Un curso de combinatoria , Cambridge University Press, ISBN 0-521-00601-5
• Zieschang, Paul-Hermann (2005a), " Esquemas de asociación: experimentos diseñados, álgebra y combinatoria por Rosemary A. Bailey, reseña" (PDF) , Boletín de la Sociedad Matemática Americana , 43 (2): 249–253 , doi : 10.1090/S0273-0979-05-01077-3
• Zieschang, Paul-Hermann (2005b), Teoría de los esquemas de asociación , Springer, ISBN 3-540-26136-2
• Zieschang, Paul-Hermann (2006), "La condición de intercambio para esquemas de asociación", Israel Journal of Mathematics , 151 (3): 357–380 , doi : 10.1007/BF02777367 , MR 2214129 , S2CID 120009352