Mayorización, politopos y clases de matrices combinatorias

Abstract

En este trabajo, investigamos el retículo de caras, la propiedad de aditividad, el f-vector y algunas conexiones con clases de matrices combinatorias de unos politopos asociados con tres conceptos de mayorización. El concepto clásico de mayorización fue introducido y caracterizado por Hardy, Littlewood y Pólya en [HLP34]; además, en el año 1959 el matemático ruso Mirsky describió geométricamente el concepto de mayorización débil en [Mir59] y, más recientemente, Roventa [Rov16] introdujo el concepto de mayorización fuerte para generalizarla desigualdad de Hardy, Littlewood y Pólya. De otra parte, en el año 2001, Dahl estudió el ideal principal de mayorización en [Dah01], donde exploró conexiones con optimización y presentó una descripción del 1-esqueleto de este politopo. Posteriormente, en [Dah10], él estableció una generalización del teorema de Gale-Ryser usando la aditividad entera del permutaedro de mayorización, trabajo que inauguró una nueva clase de matrices combinatorias llamada A(B,S), la cual él y Brualdi estudiaron en [BD12]. A partir de lo anterior, en este trabajo, nosotros definimos permutaedros e ideales principales asociados con los conceptos de mayorización débil y fuerte, los cuales investigamos motivados por las fuentes anteriormente mencionadas, e inspirados por la revisión presentada en [BKL85], [BS96] y [Bar02] de algunas demostraciones del resultado ya clásico que caracteriza el retículo de caras del permutaedro mediante las particiones ordenadas de [n]. Aprovechando la propiedad de ser simple que tienen varios delos politopos que investigamos, damos descripciones combinatorias de sus retículos de caras. Posteriormente, encontramos expresiones para las componentes del f-vector de cada uno delos politopos estudiados. Asimismo, establecemos caracterizaciones matricial y geométrica del concepto de mayorización fuerte, las cuales complementan los trabajos de Roventa [Rov16]sobre este concepto. Finalmente, ofrecemos demostraciones de la propiedad de aditividad para permutaedros e ideales de mayorización que obtenemos mediante la aplicación de politopos de Newton. Este es un enfoque para investigar la propiedad de aditividad alternativo a los encontrados en la literatura consultada.

In this work, we investigate the face lattice, the additivity property, the f-vector, and some connections with combinatorial matrix classes of some polytopes associated with three concepts of majorization. The classic concept of majorization was introduced and characterized by Hardy, Littlewood and Pólya in [HLP34]; besides, in 1959 the Russian mathematician Mirskydescribed geometrically the concept of weak majorization in [Mir59] and, more recently, Roventa[Rov16] introduced the concept of strong majorization to generalize the inequality of Hardy, Littlewood and Pólya. On the other hand, in 2001, Dahl studied the principal majorization ideal in [Dah01], where he explored connections with optimization and presented a description of the 1-skeleton of this polytope. Subsequently, in [Dah10], he established a generalization ofthe Gale-Ryser theorem using the integer additivity of the majorization permutahedron, workthat opened a new combinatorial matrix class calledA(B,S), which he and Brualdi studied in [BD12]. Based on the above, in this work, we define permutahedra and principal ideals associated with the concepts of weak and strong majorization, which we study motivated by the aforementioned references, and inspired by the review presented in [BKL85], [BS96] and [Bar02]of some proofs of the already classic result that characterizes the face lattice of permutahedron by means ordered partitions of [n]. Taking advantage of the property of being simple that seve-ral of the polytopes that we investigate have, we give combinatorial descriptions of their facelattices. Subsequently, we find expressions for thef-vector components of each of the polytopes studied. Likewise, we establish matrix and geometric characterizations of the concept of strong majorization, which complement the Roventa’s work on this concept. Finally, we offer proofs ofthe additivity property for majorization permutahedra and the majorization principal ideals that we obtain by applying Newton’s polytopes. This is an approach to investigate the additivity property alternative to those found in the references consulted.