orden de dominancia

Concepto matemático discreto

Ejemplo de ordenamiento de dominancia de particiones de n. Aquí, n  = 6, los nodos son particiones de 6, los bordes indican que el nodo superior domina al nodo inferior. Si bien este ordenamiento parcial en particular se califica , esto no es cierto para el ordenamiento de dominancia en particiones de cualquier número  n  > 6.

En matemáticas discretas , el orden de dominancia (sinónimos: orden de dominancia , orden de mayorización , ordenamiento natural ) es un orden parcial en el conjunto de particiones de un entero positivo n que juega un papel importante en la combinatoria algebraica y la teoría de la representación , especialmente en el contexto de la simétrica. Funciones y teoría de la representación del grupo simétrico .

Definición

Si p = ( p ₁ , p ₂ ,...) y q = ( q ₁ , q ₂ ,...) son particiones de n , con las partes dispuestas en orden débilmente decreciente, entonces p precede a q en la dominancia ordene si para cualquier k ≥ 1, la suma de las k partes más grandes de p es menor o igual a la suma de las k partes más grandes de q :

${\displaystyle p\trianglelefteq q{\text{ if and only if }}p_{1}+\cdots +p_{k}\leq q_{1}+\cdots +q_{k}{\text{ for all }}k\geq 1.}$

En esta definición, las particiones se amplían añadiendo cero partes al final según sea necesario.

Propiedades del orden de dominancia

• Entre las particiones de n , (1,...,1) es la más pequeña y (n) es la más grande.
• El orden de dominancia implica un orden lexicográfico , es decir, si p domina a q y p  ≠  q , entonces para el i más pequeño tal que p _i ≠ q _i se tiene p _i > q _i .
• El conjunto de particiones de n está ordenado linealmente (y es equivalente al ordenamiento lexicográfico) si y solo si n ≤ 5. Se califica si y solo si n ≤ 6. Vea la imagen de la derecha para ver un ejemplo.
• Una partición p cubre una partición q si y solo si p _i = q _i + 1, p _k = q _k − 1, p _j = q _j para todo j ≠ i , k y (1) k = i + 1 o (2) q _i = q _k (Brylawski, Proposición 2.3). A partir del diagrama de Young de q , el diagrama de Young de p se obtiene eliminando primero el último cuadro de la fila k y luego agregándolo al final de la fila inmediatamente anterior k − 1, o al final de la fila i. < k si las filas i a k ​​del diagrama de Young de q tienen todas la misma longitud.
• Cada partición p tiene una partición conjugada (o dual) p ′, cuyo diagrama de Young es la transpuesta del diagrama de Young de p . Esta operación invierte el orden de dominancia:

${\displaystyle p\trianglelefteq q}$si y solo si ${\displaystyle q^{\prime }\trianglelefteq p^{\prime }.}$

• El orden de dominancia determina las inclusiones entre los cierres de Zariski de las clases de conjugación de matrices nilpotentes .

estructura reticular

Las particiones de n forman una red bajo el orden de dominancia, denotada como L _n , y la operación de conjugación es un antiautomorfismo de esta red. Para describir explícitamente las operaciones de red, para cada partición p considere la  tupla asociada ( n + 1) :

${\displaystyle {\hat {p}}=(0,p_{1},p_{1}+p_{2},\ldots ,p_{1}+p_{2}+\cdots +p_{n}).}$

La partición p se puede recuperar de su tupla ( n +1) asociada aplicando la diferencia del paso 1. Además, las tuplas ( n +1 ) asociadas a las particiones de n se caracterizan entre todas las secuencias enteras de longitud n  + 1 por las siguientes tres propiedades: ${\displaystyle p_{i}={\hat {p}}_{i}-{\hat {p}}_{i-1}.}$

• no decreciente, ${\displaystyle {\hat {p}}_{i}\leq {\hat {p}}_{i+1};}$
• Cóncavo, ${\displaystyle 2{\hat {p}}_{i}\geq {\hat {p}}_{i-1}+{\hat {p}}_{i+1};}$
• El término inicial es 0 y el término final es n , ${\displaystyle {\hat {p}}_{0}=0,{\hat {p}}_{n}=n.}$

Según la definición del orden de dominancia, la partición p precede a la partición q si y solo si la tupla asociada ( n  + 1) de p es término por término menor o igual a la tupla asociada ( n  + 1) de q. . Si p , q , r son particiones, entonces si y solo si El mínimo de componentes de dos secuencias enteras cóncavas no decrecientes también es cóncavo y no decreciente. Por lo tanto, para dos particiones cualesquiera de n , p y q , su encuentro es la partición de n cuya tupla ( n  + 1) asociada tiene componentes . La idea natural de usar una fórmula similar para la unión falla , porque el máximo de dos componentes por componentes Las secuencias cóncavas no necesitan ser cóncavas. Por ejemplo, para n  = 6, las particiones [3,1,1,1] y [2,2,2] tienen secuencias asociadas (0,3,4,5,6,6,6) y (0,2 ,4,6,6,6,6), cuyo máximo componente (0,3,4,6,6,6,6) no corresponde a ninguna partición. Para demostrar que dos particiones cualesquiera de n tienen una unión, se utiliza el antiautomorfismo de conjugación: la unión de p y q es la partición conjugada del encuentro de p ′ y q ′: ${\displaystyle r\trianglelefteq p,r\trianglelefteq q}$ ${\displaystyle {\hat {r}}\leq {\hat {p}},{\hat {r}}\leq {\hat {q}}.}$ ${\displaystyle \operatorname {min} ({\hat {p}}_{i},{\hat {q}}_{i}).}$

${\displaystyle p\lor q=(p^{\prime }\land q^{\prime })^{\prime }.}$

Para las dos particiones p y q en el ejemplo anterior, sus particiones conjugadas son [4,1,1] y [3,3] con encuentro [3,2,1], que es autoconjugado; por lo tanto, la unión de p y q es [3,2,1].

Thomas Brylawski ha determinado muchas invariantes de la red L _n , como la altura mínima y el número de cobertura máximo, y clasificó los intervalos de longitud pequeña. Si bien L _n no es distributivo para n  ≥ 7, comparte algunas propiedades con las redes distributivas: por ejemplo, su función de Möbius toma solo valores 0, 1, −1.

Generalizaciones

El orden de dominancia en los cuadros estándar de Young para la partición 6 = 4 + 2

Las particiones de n se pueden representar gráficamente mediante diagramas de Young en n cajas. Los cuadros de Young estándar son ciertas formas de llenar los diagramas de Young con números, y un orden parcial en ellos (a veces llamado orden de dominancia en los cuadros de Young ) se puede definir en términos del orden de dominancia en los diagramas de Young. Para que un cuadro de Young T domine a otro cuadro de Young S , la forma de T debe dominar la de S como partición y, además, lo mismo debe ser válido siempre que T y S se trunquen por primera vez en sus subcuadros que contienen entradas hasta un valor determinado. k , para cada elección de k .

De manera similar, existe un orden de dominancia en el conjunto de bitables de Young estándar, que desempeña un papel en la teoría de los monomios estándar .

Ver también

• celosía de joven
• Mayorización

Referencias

• Macdonald, Ian G. (1979). "sección I.1". Funciones simétricas y polinomios de Hall . Prensa de la Universidad de Oxford. págs. 5–7. ISBN 0-19-853530-9.
• Stanley, Richard P. (1999). Combinatoria enumerativa. vol. 2. Prensa de la Universidad de Cambridge. ISBN 0-521-56069-1.
• Brylawski, Thomas (1973). "La celosía de particiones enteras". Matemáticas discretas . 6 (3): 201-2. doi : 10.1016/0012-365X(73)90094-0 .