Ordenamiento débil

Clasificación matemática de un conjunto

Un orden débil en el conjunto donde y tienen el mismo rango, se clasifica por debajo de ellos, y se clasifica por encima de ellos. I) representación como un orden débil estricto donde se muestra como una flecha desde a ; II) representación como un preorden total , que se muestra mediante flechas; III) representación como una partición ordenada, con los conjuntos de la partición como elipses punteadas y el orden total en estos conjuntos mostrados con flechas. ${\displaystyle \{a,b,c,d\}}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle d}$
${\displaystyle \,<\,}$ ${\displaystyle x<y}$ ${\displaystyle x}$ ${\displaystyle y}$
${\displaystyle \,\leq \,}$

Los 13 posibles ordenamientos débiles estrictos en un conjunto de tres elementos . Los únicos órdenes totales se muestran en negro. Dos ordenamientos están conectados por una arista si difieren en una sola dicotomía. ${\displaystyle \{a,b,c\}.}$

En matemáticas , especialmente en teoría del orden , un orden débil es una formalización matemática de la noción intuitiva de una clasificación de un conjunto , algunos de cuyos miembros pueden estar vinculados entre sí. Los órdenes débiles son una generalización de conjuntos totalmente ordenados (clasificaciones sin vínculos) y son a su vez generalizados por conjuntos y preórdenes (estrictamente) parcialmente ordenados . ^[1]

Existen varias formas comunes de formalizar ordenamientos débiles, que son diferentes entre sí pero criptomórficos (interconvertibles sin pérdida de información): pueden axiomatizarse como ordenamientos débiles estrictos (conjuntos estrictamente parcialmente ordenados en los que la incomparabilidad es una relación transitiva ), como preórdenes totales (relaciones binarias transitivas en las que al menos una de las dos relaciones posibles existe entre cada par de elementos), o como particiones ordenadas ( particiones de los elementos en subconjuntos disjuntos, junto con un orden total en los subconjuntos). En muchos casos también es posible otra representación llamada arreglo preferencial basado en una función de utilidad .

Los ordenamientos débiles se cuentan por los números de Bell ordenados . Se utilizan en informática como parte de algoritmos de refinamiento de particiones y en la biblioteca estándar de C++ . ^[2]

Ejemplos

En las carreras de caballos , el uso de acabados fotográficos ha eliminado algunos, pero no todos, los empates o (como se les llama en este contexto) empates , por lo que el resultado de una carrera de caballos puede modelarse mediante un orden débil. ^[3] En un ejemplo de la carrera de obstáculos de la Maryland Hunt Cup en 2007, The Bruce fue el claro ganador, pero dos caballos, Bug River y Lear Charm, empataron en el segundo lugar, con los caballos restantes más atrás; tres caballos no terminaron. ^[4] En el orden débil que describe este resultado, The Bruce sería el primero, Bug River y Lear Charm se clasificarían después de The Bruce pero antes de todos los demás caballos que terminaron, y los tres caballos que no terminaron se ubicarían últimos en el orden pero empatados entre sí.

Los puntos del plano euclidiano pueden ordenarse por su distancia al origen , lo que da otro ejemplo de un ordenamiento débil con infinitos elementos, infinitos subconjuntos de elementos ligados (los conjuntos de puntos que pertenecen a un círculo común centrado en el origen) e infinitos puntos dentro de estos subconjuntos. Aunque este ordenamiento tiene un elemento más pequeño (el propio origen), no tiene ningún segundo elemento más pequeño ni ningún elemento más grande.

Las encuestas de opinión en las elecciones políticas proporcionan un ejemplo de un tipo de ordenamiento que se asemeja a los ordenamientos débiles, pero que se modela mejor matemáticamente de otras maneras. En los resultados de una encuesta, un candidato puede estar claramente por delante de otro, o los dos candidatos pueden estar empatados estadísticamente, lo que significa no que sus resultados de la encuesta sean iguales sino que están dentro del margen de error uno del otro. Sin embargo, si el candidato está empatado estadísticamente con y está empatado estadísticamente con todavía podría ser posible que sea claramente mejor que por lo que estar empatado no es en este caso una relación transitiva . Debido a esta posibilidad, las clasificaciones de este tipo se modelan mejor como semiórdenes que como ordenamientos débiles. ^[5] ${\displaystyle x}$ ${\displaystyle y,}$ ${\displaystyle y}$ ${\displaystyle z,}$ ${\displaystyle x}$ ${\displaystyle z,}$

Axiomatizaciones

Supongamos en todo momento que es una relación binaria homogénea en un conjunto (es decir, es un subconjunto de ) y, como de costumbre, escribimos y decimos que se cumple o es verdadero si y solo si ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S\times S}$ ${\displaystyle x<y}$ ${\displaystyle x<y}$ ${\displaystyle (x,y)\in \,<.\,}$

Ordenamientos débiles estrictos

Preliminares sobre la incomparabilidad y la transitividad de la incomparabilidad

Se dice que dos elementos y de son incomparables con respecto a si ni son verdaderos. ^[1] Un orden parcial estricto es un ordenamiento débil estricto si y solo si la incomparabilidad con respecto a es una relación de equivalencia . La incomparabilidad con respecto a es siempre una relación simétrica homogénea en Es reflexiva si y solo si es irreflexiva (lo que significa que siempre es falsa), lo que se supondrá de modo que la transitividad sea la única propiedad que esta "relación de incomparabilidad" necesita para ser una relación de equivalencia . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle x<y}$ ${\displaystyle y<x}$ ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle S.}$ ${\displaystyle \,<\,}$ ${\displaystyle x<x}$

Defina también una relación homogénea inducida en declarando que donde es importante destacar que esta definición no es necesariamente la misma que: si y solo si Dos elementos son incomparables con respecto a si y solo si son equivalentes con respecto a (o menos verbosamente, -equivalentes ), lo que por definición significa que ambos son verdaderos. La relación "son incomparables con respecto a " es, por lo tanto, idéntica a (es decir, igual a) la relación "son -equivalentes" (por lo que, en particular, la primera es transitiva si y solo si la segunda lo es). Cuando es irreflexiva, entonces la propiedad conocida como "transitividad de incomparabilidad" (definida a continuación) es exactamente la condición necesaria y suficiente para garantizar que la relación "son -equivalentes" forme de hecho una relación de equivalencia en Cuando este es el caso, permite que dos elementos cualesquiera que satisfagan se identifiquen como un solo objeto (específicamente, se identifican juntos en su clase de equivalencia común ). ${\displaystyle \,\lesssim \,}$ ${\displaystyle S}$ $${\displaystyle x\lesssim y{\text{ is true }}\quad {\text{ if and only if }}\quad y<x{\text{ is false}}}$$ ${\displaystyle x\lesssim y}$ ${\displaystyle x<y{\text{ or }}x=y.}$ ${\displaystyle x,y\in S}$ ${\displaystyle \,<\,}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle \,\lesssim }$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ ${\displaystyle \,<}$ ${\displaystyle \,\lesssim }$ ${\displaystyle \,<\,}$ ${\displaystyle \,\lesssim }$ ${\displaystyle S.}$ ${\displaystyle x,y\in S}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$

Definición

Un ordenamiento débil estricto en un conjunto es un orden parcial estricto en para el cual la relación de incomparabilidad inducida en por es una relación transitiva . ^[1] Explícitamente, un orden débil estricto en es una relación homogénea en que tiene las cuatro propiedades siguientes: ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$

1. Irreflexividad : Para nadaes cierto que ${\displaystyle x\in S,}$ ${\displaystyle x<x.}$
   • Esta condición se cumple si y sólo si la relación inducida en es reflexiva , donde se define declarando que es verdadero si y sólo si es falso . ${\displaystyle \,\lesssim \,}$ ${\displaystyle S}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x\lesssim y}$ ${\displaystyle y<x}$
2. Transitividad : Para todosientonces ${\displaystyle x,y,z\in S,}$ ${\displaystyle x<y{\text{ and }}y<z}$ ${\displaystyle x<z.}$
3. Asimetría : Para todosies verdadero entonceses falso. ${\displaystyle x,y\in S,}$ ${\displaystyle x<y}$ ${\displaystyle y<x}$
4. Transitividad de incomparabilidad : Para todosies incomparable con(lo que significa que ninies verdadero) y sies incomparable conentonceses incomparable con ${\displaystyle x,y,z\in S,}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x<y}$ ${\displaystyle y<x}$ ${\displaystyle y}$ ${\displaystyle z,}$ ${\displaystyle x}$ ${\displaystyle z.}$
   • Dos elementos son incomparables con respecto a si y solo si son equivalentes con respecto a la relación inducida (lo que por definición significa que ambos son verdaderos), donde como antes, se declara verdadero si y solo si es falso. Por lo tanto, esta condición se cumple si y solo si la relación simétrica en definida por " son equivalentes con respecto a " es una relación transitiva, lo que significa que siempre que sean -equivalentes y también sean -equivalentes, entonces necesariamente son -equivalentes. Esto también se puede reformular como: siempre que y también entonces necesariamente ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,<\,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ ${\displaystyle x\lesssim y}$ ${\displaystyle y<x}$ ${\displaystyle S}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x{\text{ and }}y}$ ${\displaystyle \,\lesssim }$ ${\displaystyle y{\text{ and }}z}$ ${\displaystyle \,\lesssim }$ ${\displaystyle x{\text{ and }}z}$ ${\displaystyle \,\lesssim }$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$ ${\displaystyle y\lesssim z{\text{ and }}z\lesssim y}$ ${\displaystyle x\lesssim z{\text{ and }}z\lesssim x.}$

Las propiedades (1), (2) y (3) son las propiedades definitorias de un orden parcial estricto, aunque hay cierta redundancia en esta lista ya que la asimetría (3) implica irreflexividad (1), y también porque la irreflexividad (1) y la transitividad (2) juntas implican asimetría (3). ^[6] La relación de incomparabilidad es siempre simétrica y será reflexiva si y solo si es una relación irreflexiva (lo que se supone por la definición anterior). En consecuencia, un orden parcial estricto es un orden débil estricto si y solo si su relación de incomparabilidad inducida es una relación de equivalencia . En este caso, sus clases de equivalencia se particionan y, además, el conjunto de estas clases de equivalencia puede ordenarse totalmente de forma estricta mediante una relación binaria , también denotada por que se define para todos por: ${\displaystyle \,<\,}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \,<,}$ ${\displaystyle A,B\in {\mathcal {P}}}$

${\displaystyle A<B{\text{ if and only if }}a<b}$para algunos (o equivalentemente, para todos) los representantes ${\displaystyle a\in A{\text{ and }}b\in B.}$

Por el contrario, cualquier orden total estricto en una partición de da lugar a un ordenamiento débil estricto en definido por si y solo si existen conjuntos en esta partición tales que ${\displaystyle {\mathcal {P}}}$ ${\displaystyle S}$ ${\displaystyle \,<\,}$ ${\displaystyle S}$ ${\displaystyle a<b}$ ${\displaystyle A,B\in {\mathcal {P}}}$ ${\displaystyle a\in A,b\in B,{\text{ and }}A<B.}$

No todo orden parcial obedece a la ley transitiva de incomparabilidad. Por ejemplo, considere el orden parcial en el conjunto definido por la relación Los pares son incomparables pero y están relacionados, por lo que la incomparabilidad no forma una relación de equivalencia y este ejemplo no es un ordenamiento débil estricto. ${\displaystyle \{a,b,c\}}$ ${\displaystyle b<c.}$ ${\displaystyle a,b{\text{ and }}a,c}$ ${\displaystyle b}$ ${\displaystyle c}$

Para la transitividad de la incomparabilidad es necesaria cada una de las siguientes condiciones , y para los órdenes parciales estrictos también es suficiente :

• Si entonces para todos, uno o ambos. ${\displaystyle x<y}$ ${\displaystyle z,}$ ${\displaystyle x<z{\text{ or }}z<y}$
• Si es incomparable con entonces para todo , o bien ( ) o ( ) o ( es incomparable con y es incomparable con ). ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x<z{\text{ and }}y<z}$ ${\displaystyle z<x{\text{ and }}z<y}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle y}$

Total de pedidos anticipados

Los órdenes débiles estrictos están muy relacionados con los preórdenes totales o los órdenes débiles (no estrictos) , y los mismos conceptos matemáticos que se pueden modelar con ordenamientos débiles estrictos se pueden modelar igualmente bien con preórdenes totales. Un preorden total o un orden débil es un preorden en el que dos elementos cualesquiera son comparables. ^[7] Un preorden total satisface las siguientes propiedades: ${\displaystyle \,\lesssim \,}$

• Transitividad : Para todo si entonces ${\displaystyle x,y,{\text{ and }}z,}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim z}$ ${\displaystyle x\lesssim z.}$
• Fuerte conectividad : para todos ${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x\lesssim y{\text{ or }}y\lesssim x.}$
  • Lo que implica reflexividad : para todos ${\displaystyle x,}$ ${\displaystyle x\lesssim x.}$

Un orden total es un preorden total que es antisimétrico, es decir, que también es un orden parcial . Los preórdenes totales a veces también se denominan relaciones de preferencia .

El complemento de un orden débil estricto es un preorden total, y viceversa, pero parece más natural relacionar los órdenes débiles estrictos y los preórdenes totales de una manera que preserve en lugar de invertir el orden de los elementos. Por lo tanto, tomamos el inverso del complemento: para un orden débil estricto definimos un preorden total estableciendo siempre que no sea el caso que En la otra dirección, para definir un orden débil estricto < a partir de un preorden total establecido siempre que no sea el caso que ^[8] ${\displaystyle \,<,}$ ${\displaystyle \,\lesssim \,}$ ${\displaystyle x\lesssim y}$ ${\displaystyle y<x.}$ ${\displaystyle \,\lesssim ,}$ ${\displaystyle x<y}$ ${\displaystyle y\lesssim x.}$

En cualquier preorden existe una relación de equivalencia correspondiente donde dos elementos y se definen como equivalentes si En el caso de un preorden total el orden parcial correspondiente en el conjunto de clases de equivalencia es un orden total. Dos elementos son equivalentes en un preorden total si y solo si son incomparables en el ordenamiento débil estricto correspondiente. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\lesssim y{\text{ and }}y\lesssim x.}$

Particiones ordenadas

Una partición de un conjunto es una familia de subconjuntos no vacíos y disjuntos de los cuales tienen como unión. Una partición, junto con un orden total de los conjuntos de la partición, da una estructura llamada por Richard P. Stanley una partición ordenada ^[9] y por Theodore Motzkin una lista de conjuntos . ^[10] Una partición ordenada de un conjunto finito puede escribirse como una secuencia finita de los conjuntos en la partición: por ejemplo, las tres particiones ordenadas del conjunto son ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \{a,b\}}$ $${\displaystyle \{a\},\{b\},}$$ $${\displaystyle \{b\},\{a\},\;{\text{ and }}}$$ $${\displaystyle \{a,b\}.}$$

En un ordenamiento débil estricto, las clases de equivalencia de incomparabilidad dan una partición de conjuntos, en la que los conjuntos heredan un ordenamiento total de sus elementos, dando lugar a una partición ordenada. En la otra dirección, cualquier partición ordenada da lugar a un ordenamiento débil estricto en el que dos elementos son incomparables cuando pertenecen al mismo conjunto en la partición, y en caso contrario heredan el orden de los conjuntos que los contienen.

Representación mediante funciones

Para conjuntos de cardinalidad suficientemente pequeña , es posible una cuarta axiomatización, basada en funciones de valor real. Si es un conjunto cualquiera, entonces una función de valor real en induce un orden débil estricto en estableciendo El preorden total asociado se da estableciendo y la equivalencia asociada estableciendo ${\displaystyle X}$ ${\displaystyle f:X\to \mathbb {R} }$ ${\displaystyle X}$ ${\displaystyle X}$ $${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$ ${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a)\leq f(b)}$ ${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a)=f(b).}$

Las relaciones no cambian cuando se reemplaza por ( función compuesta ), donde es una función de valor real estrictamente creciente definida al menos en el rango de Así, por ejemplo, una función de utilidad define una relación de preferencia . En este contexto, los ordenamientos débiles también se conocen como arreglos preferenciales . ^[11] ${\displaystyle f}$ ${\displaystyle g\circ f}$ ${\displaystyle g}$ ${\displaystyle f.}$

Si es finito o contable, cada orden débil en puede representarse mediante una función de esta manera. ^[12] Sin embargo, existen órdenes débiles estrictos que no tienen una función real correspondiente. Por ejemplo, no existe tal función para el orden lexicográfico en Por lo tanto, mientras que en la mayoría de los modelos de relación de preferencia la relación define una función de utilidad hasta las transformaciones que preservan el orden, no existe tal función para las preferencias lexicográficas . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \mathbb {R} ^{n}.}$

De manera más general, si es un conjunto, es un conjunto con un ordenamiento débil estricto y es una función, entonces induce un ordenamiento débil estricto en estableciendo Como antes, el preorden total asociado se da estableciendo y la equivalencia asociada estableciendo No se supone aquí que es una función inyectiva , por lo que una clase de dos elementos equivalentes en puede inducir una clase más grande de elementos equivalentes en Además, no se supone que sea una función sobreyectiva , por lo que una clase de elementos equivalentes en puede inducir una clase más pequeña o vacía en Sin embargo, la función induce una función inyectiva que mapea la partición en a la de Por lo tanto, en el caso de particiones finitas, el número de clases en es menor o igual que el número de clases en ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \,<,\,}$ ${\displaystyle f:X\to Y}$ ${\displaystyle f}$ ${\displaystyle X}$ $${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$ ${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a){}\lesssim {}f(b),}$ ${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a){}\sim {}f(b).}$ ${\displaystyle f}$ ${\displaystyle Y}$ ${\displaystyle X.}$ ${\displaystyle f}$ ${\displaystyle Y}$ ${\displaystyle X.}$ ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y.}$ ${\displaystyle X}$ ${\displaystyle Y.}$

Tipos de pedidos relacionados

Los semiórdenes generalizan ordenamientos débiles estrictos, pero no suponen transitividad de incomparabilidad. ^[13] Un orden débil estricto que es tricotómico se denomina orden total estricto . ^[14] El preorden total que es el inverso de su complemento es en este caso un orden total .

Para un orden débil estricto otra relación reflexiva asociada es su clausura reflexiva , un orden parcial (no estricto) Las dos relaciones reflexivas asociadas difieren con respecto a diferentes y para los cuales ni ni : en el preorden total correspondiente a un orden débil estricto obtenemos y mientras que en el orden parcial dado por la clausura reflexiva obtenemos ni ni Para los órdenes totales estrictos estas dos relaciones reflexivas asociadas son las mismas: el orden total (no estricto) correspondiente. ^[14] La clausura reflexiva de un orden débil estricto es un tipo de orden parcial serie-paralelo . ${\displaystyle \,<\,}$ ${\displaystyle \,\leq .}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a<b}$ ${\displaystyle b<a}$ ${\displaystyle a\lesssim b}$ ${\displaystyle b\lesssim a,}$ ${\displaystyle a\leq b}$ ${\displaystyle b\leq a.}$

Todos los órdenes débiles en un conjunto finito

Enumeración combinatoria

El número de órdenes débiles distintos (representados como órdenes débiles estrictos o como preórdenes totales) en un conjunto de elementos se da por la siguiente secuencia (secuencia A000670 en la OEIS ): ${\displaystyle n}$

Téngase en cuenta que S ( n , k ) se refiere a números de Stirling del segundo tipo .

Estos números también se denominan números de Fubini o números de Bell ordenados .

Por ejemplo, para un conjunto de tres elementos etiquetados, hay un orden débil en el que los tres elementos están empatados. Hay tres maneras de dividir los elementos en un conjunto singleton y un grupo de dos elementos empatados, y cada una de estas divisiones da dos órdenes débiles (uno en el que el singleton es más pequeño que el grupo de dos, y otro en el que este orden se invierte), lo que da seis órdenes débiles de este tipo. Y hay una única manera de dividir el conjunto en tres singletons, que pueden ordenarse en total de seis maneras diferentes. Por lo tanto, en total, hay 13 órdenes débiles diferentes en tres elementos.

Estructura de adyacencia

El permutoedro de cuatro elementos es un poliedro tridimensional convexo . Tiene 24 vértices, 36 aristas y 14 caras bidimensionales, que en conjunto con el poliedro tridimensional completo corresponden a los 75 ordenamientos débiles de cuatro elementos.

A diferencia de los órdenes parciales, la familia de ordenamientos débiles en un conjunto finito dado no está conectada en general por movimientos que agreguen o eliminen una única relación de orden a o de un ordenamiento dado. Por ejemplo, para tres elementos, el ordenamiento en el que están empatados los tres elementos difiere en al menos dos pares de cualquier otro ordenamiento débil en el mismo conjunto, ya sea en el ordenamiento débil estricto o en las axiomatizaciones de preorden total. Sin embargo, es posible un tipo diferente de movimiento, en el que los ordenamientos débiles en un conjunto están más altamente conectados. Defina una dicotomía como un ordenamiento débil con dos clases de equivalencia, y defina una dicotomía como compatible con un ordenamiento débil dado si cada dos elementos que están relacionados en el ordenamiento están relacionados de la misma manera o empatados en la dicotomía. Alternativamente, una dicotomía puede definirse como un corte de Dedekind para un ordenamiento débil. Entonces un ordenamiento débil puede caracterizarse por su conjunto de dicotomías compatibles. Para un conjunto finito de elementos etiquetados, cada par de ordenamientos débiles puede estar conectado entre sí mediante una secuencia de movimientos que agregan o eliminan una dicotomía a la vez hacia o desde este conjunto de dicotomías. Además, el grafo no dirigido que tiene los ordenamientos débiles como sus vértices y estos movimientos como sus aristas, forma un cubo parcial . ^[15]

Geométricamente, los ordenamientos totales de un conjunto finito dado pueden representarse como los vértices de un permutoedro , y las dicotomías en este mismo conjunto como las facetas del permutoedro. En esta representación geométrica, los ordenamientos débiles en el conjunto corresponden a las caras de todas las dimensiones diferentes del permutoedro (incluido el permutoedro mismo, pero no el conjunto vacío, como una cara). La codimensión de una cara da el número de clases de equivalencia en el ordenamiento débil correspondiente. ^[16] En esta representación geométrica, el cubo parcial de movimientos en los ordenamientos débiles es el gráfico que describe la relación de cobertura de la red de caras del permutoedro.

Por ejemplo, el permutoedro de tres elementos es simplemente un hexágono regular. La red de caras del hexágono (de nuevo, incluyendo el hexágono mismo como cara, pero sin incluir el conjunto vacío) tiene trece elementos: un hexágono, seis aristas y seis vértices, correspondientes a un ordenamiento débil completamente empatado, seis ordenamientos débiles con un empate y seis ordenamientos totales. El gráfico de movimientos en estos 13 ordenamientos débiles se muestra en la figura. ${\displaystyle n=3,}$

Aplicaciones

Como se mencionó anteriormente, los órdenes débiles tienen aplicaciones en la teoría de la utilidad. ^[12] En la programación lineal y otros tipos de problemas de optimización combinatoria , la priorización de soluciones o de bases a menudo está dada por un orden débil, determinado por una función objetivo de valor real ; el fenómeno de los empates en estos ordenamientos se llama "degeneración", y se han utilizado varios tipos de reglas de desempate para refinar este ordenamiento débil en un ordenamiento total con el fin de prevenir problemas causados ​​por la degeneración. ^[17]

Los órdenes débiles también se han utilizado en informática , en algoritmos basados ​​en el refinamiento de particiones para la búsqueda lexicográfica en amplitud y el ordenamiento topológico lexicográfico . En estos algoritmos, un ordenamiento débil en los vértices de un grafo (representado como una familia de conjuntos que dividen los vértices, junto con una lista doblemente enlazada que proporciona un ordenamiento total en los conjuntos) se refina gradualmente a lo largo del algoritmo, produciendo finalmente un ordenamiento total que es el resultado del algoritmo. ^[18]

En la biblioteca estándar del lenguaje de programación C++ , los tipos de datos de conjunto y multiconjunto ordenan su entrada mediante una función de comparación que se especifica en el momento de la instanciación de la plantilla y que se supone que implementa un ordenamiento débil estricto. ^[2]

Véase también

• Comparabilidad  – Propiedad de elementos relacionados por desigualdades
• Preorden  – Relación binaria reflexiva y transitiva
• Componente débil  : Partición de vértices de un gráfico dirigido: los subconjuntos equivalentes en el orden débil más fino consistente con una relación dada

Referencias

1. Roberts, Fred; Tesman, Barry (2011), Combinatoria aplicada (2.ª ed.), CRC Press, Sección 4.2.4 Órdenes débiles, págs. 254-256, ISBN 9781420099836.
2. Josuttis, Nicolai M. (2012), La biblioteca estándar de C++: un tutorial y una referencia, Addison-Wesley, pág. 469, ISBN 9780132977739.
3. de Koninck, JM (2009), Esos números fascinantes, Sociedad Matemática Estadounidense, p. 4, ISBN 9780821886311.
4. Baker, Kent (29 de abril de 2007), "Bruce se aferra a la victoria en la Hunt Cup: Bug River y Lear Charm terminan empatados por el segundo puesto", The Baltimore Sun , archivado desde el original el 29 de marzo de 2015.
5. Regenwetter, Michel (2006), Elección social conductual: modelos probabilísticos, inferencia estadística y aplicaciones, Cambridge University Press, págs. 113 y siguientes, ISBN 9780521536660.
6. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007), Cierres transitivos de relaciones binarias I (PDF) , Praga: Facultad de Matemáticas - Física de la Universidad Charles, p. 1, S2CID  47676001, archivado desde el original (PDF) el 2018-04-06, Lema 1.1 (iv). Nótese que esta fuente se refiere a las relaciones asimétricas como "estrictamente antisimétricas".
7. A esta relación también se le llama fuertemente conectada .
8. Ehrgott, Matthias (2005), Optimización multicriterio, Springer, Proposición 1.9, pág. 10, ISBN 9783540276593.
9. Stanley, Richard P. (1997), Combinatoria enumerativa, vol. 2 , Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, pág. 297.
10. Motzkin, Theodore S. (1971), "Números de clasificación para cilindros y otros números de clasificación", Combinatorics (Proc. Sympos. Pure Math., vol. XIX, Univ. California, Los Ángeles, Calif., 1968) , Providence, RI: Amer. Math. Soc., págs. 167-176, MR  0332508.
11. Gross, OA (1962), "Acuerdos preferenciales", The American Mathematical Monthly , 69 (1): 4–8, doi :10.2307/2312725, JSTOR  2312725, MR  0130837.
12. Roberts, Fred S. (1979), Teoría de la medición, con aplicaciones a la toma de decisiones, la utilidad y las ciencias sociales , Enciclopedia de matemáticas y sus aplicaciones, vol. 7, Addison-Wesley, Teorema 3.1, ISBN 978-0-201-13506-0.
13. Luce, R. Duncan (1956), "Semiórdenes y una teoría de discriminación de utilidad" (PDF) , Econometrica , 24 (2): 178–191, doi :10.2307/1905751, JSTOR  1905751, MR  0078632.
14. Velleman, Daniel J. (2006), Cómo demostrarlo: un enfoque estructurado, Cambridge University Press, pág. 204, ISBN 9780521675994.
15. Eppstein, David ; Falmagne, Jean-Claude ; Ovchinnikov, Sergei (2008), Teoría de los medios: Matemáticas aplicadas interdisciplinarias , Springer, Sección 9.4, Órdenes débiles y complejos cúbicos, págs. 188-196.
16. Ziegler, Günter M. (1995), Lecciones sobre politopos , Textos de posgrado en matemáticas, vol. 152, Springer, pág. 18.
17. Chvátal, Vašek (1983), Programación lineal, Macmillan, págs. 29–38, ISBN 9780716715870.
18. Habib, Michel; Paul, Christophe; Viennot, Laurent (1999), "Técnicas de refinamiento de particiones: un interesante conjunto de herramientas algorítmicas", International Journal of Foundations of Computer Science , 10 (2): 147–170, doi :10.1142/S0129054199000125, MR  1759929.