One question relating to partially ordered sets (posets) is that of partitioning or dividing the poset's elements into the fewest number of chains that span the poset. In 1950, Dilworth established that the width of the poset - the size of the largest set composed only of incomparable elements - is the minimum number of chains needed to partition that poset. Such a bound in on-line partitioning has been harder to establish, and work has evalutated classes of posets based on their width. This paper reviews the theorems that established val(2)=5 and illustrates them with examples. It also covers some of the work on establishing bounds for on-line partitioning with the Greedy Algorithm. The paper concludes by contributing a bound on incomparable elements in graded, (t+t)-free, finite width posets.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-17T11:12:12Z No. of bitstreams: 1 pedroesperidiaodossantosneto.pdf: 630134 bytes, checksum: 788b1bde0483d09ec36a640572f67ad0 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-18T11:49:19Z (GMT) No. of bitstreams: 1 pedroesperidiaodossantosneto.pdf: 630134 bytes, checksum: 788b1bde0483d09ec36a640572f67ad0 (MD5) / Made available in DSpace on 2017-03-18T11:49:20Z (GMT). No. of bitstreams: 1 pedroesperidiaodossantosneto.pdf: 630134 bytes, checksum: 788b1bde0483d09ec36a640572f67ad0 (MD5) Previous issue date: 2016-12-14 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Opresentetrabalhoversasobrecódigoscorretoresdeerroseseusduaissobreespaçosposet. Inicialmente,veremososconceitosdoqueéumcódigoeautilidadedeumcódigocorretorde erros em um sistema de comunicação e construiremos as principais propriedades de corpos finitos. Estesconceitoscombinadosserãoutilizadosparaaconstruiçãodecódigoscorretores de erros em espaços de Hamming, amplamente aplicados hoje. Em seguida, construiremos os códigos corretores de erros sobre espaços poset e algumas de suas consequências, como o surgimento de códigos P-MDS. Enunciaremos o Teorema da Dualidade para espaços poset e, por fim, analisaremosos códigos do tipo P-cadeia e algumas de suas propriedades provenientes do Teorema da Dualidade. / This piece of work treats of error correcting codes and their dual codes in poset spaces. Initially we will cover the concepts of what is a code and the need of an error correction code in a communication system and the main properties of finite fields. These concepts combined are used for building the error correction codes in Hamming spaces, which are currently largely applied. Poset spaces are proposed as a generalization of the Hamming spaces e we will build the codes over poset spaces and some of their consequences, as the occurrence of P-MDS codes. Then, we will state and prove the Duality Theorem for poset spaces. Lastly, we will analyze the P-chain codes some and of their properties derived from the Duality Theorem.

<p>Neka je A neprazan skup&nbsp; i ℒ&nbsp;= (L, &le;) proizvoljna mreža sa nulom i jedinicom. Svako preslikavanje &micro;: A &rarr; L zovemo rasplinuti podskup od A. U ovoj tezi proučavali smo rasplinute posete i relacije rasplinutog poretka. Uveli smo neke nove pojmove: rasplinuta uređena grupa, rasplinuti pozitivan konus, rasplinuti negativan konus, rasplinuta mrežno uređena grupa. Posmatrajući strukturu svih relacija slabog rasplinutog poretka koje su podskup klasične relacije poretka &le; , do&scaron;li smo do zaključka da ova struktura predstavlja kompletnu mrežu. Takođe, važan zadatak je bio da ispitamo egzistenciju rasplinute mrežno uređene podgrupe <i>l</i>&nbsp;&ndash;uređene grupe koja nije linearno uređena. Bitan rezultat je rasplinuta mrežno uređena podgrupa date mrežno uređene grupe G, koja je konstruisana pomoću mreže svih kompleksnih <em>l</em> &ndash;podgrupa od G.</p> / <p>Let A be a nonempty set, and let <em>ℒ</em> = (L, &le;) be a lattice with 0 and 1. The mapping: &micro;: A &rarr; L is called a fuzzy subset of A. In this work we investigated fuzzy posets and fuzzy ordering relations. We introduced some new notions: fuzzy ordered groups, fuzzy positive cone, fuzzy negative cone, fuzzy lattice ordered group. Considering a structure of all weak fuzzy orderings contained in the crisp order &le;, we concluded that this structure represents a complete lattice. Also, an important task was to investigate the existence of a fuzzy lattice ordered subgroup of an <em>l</em>&ndash;ordered group which is not linearly ordered. A main result is a fuzzy lattice ordered subgroup of a given lattice ordered group G, which is constructed by the lattice of all convex <em>l</em>-subgroups of G.</p>

We analyze the notions of monotonicity and complete monotonicity for Markov Chains in continuous-time, taking values in a finite partially ordered set. Similarly to what happens in discrete-time, the two notions are not equivalent.<br> However, we show that there are partially ordered sets for which monotonicity and complete monotonicity coincide in continuous time but not in discrete-time. / Nous étudions les notions de monotonie et de monotonie complète pour les processus de Markov (ou chaînes de Markov à temps continu) prenant leurs valeurs dans un espace partiellement ordonné. Ces deux notions ne sont pas équivalentes, comme c'est le cas lorsque le temps est discret. Cependant, nous établissons que pour certains ensembles partiellement ordonnés, l'équivalence a lieu en temps continu bien que n'étant pas vraie en temps discret.

The central topic of this thesis is Schnyder's Theorem. Schnyder's Theorem provides a characterization of planar graphs in terms of their poset dimension, as follows: a graph G is planar if and only if the dimension of the incidence poset of G is at most three. One of the implications of the theorem is proved by giving an explicit mapping of the vertices to R^2 that defines a straightline embedding of the graph. The other implication is proved by introducing the concept of normal labelling. Normal labellings of plane triangulations can be used to obtain a realizer of the incidence poset. We present an exposition of Schnyder’s theorem with his original proof, using normal labellings. An alternate proof of Schnyder’s Theorem is also presented. This alternate proof does not use normal labellings, instead we use some structural properties of a realizer of the incidence poset to deduce the result. Some applications and a generalization of one implication of Schnyder’s Theorem are also presented in this work. Normal labellings of plane triangulations can be used to obtain a barycentric embedding of a plane triangulation, and they also induce a partition of the edge set of a plane triangulation into edge disjoint trees. These two applications of Schnyder’s Theorem and a third one, relating realizers of the incidence poset and canonical orderings to obtain a compact drawing of a graph, are also presented. A generalization, to abstract simplicial complexes, of one of the implications of Schnyder’s Theorem was proved by Ossona de Mendez. This generalization is also presented in this work. The concept of order labelling is also introduced and we show some similarities of the order labelling and the normal labelling. Finally, we conclude this work by showing the source code of some implementations done in Sage.

The central topic of this thesis is Schnyder's Theorem. Schnyder's Theorem provides a characterization of planar graphs in terms of their poset dimension, as follows: a graph G is planar if and only if the dimension of the incidence poset of G is at most three. One of the implications of the theorem is proved by giving an explicit mapping of the vertices to R^2 that defines a straightline embedding of the graph. The other implication is proved by introducing the concept of normal labelling. Normal labellings of plane triangulations can be used to obtain a realizer of the incidence poset. We present an exposition of Schnyder’s theorem with his original proof, using normal labellings. An alternate proof of Schnyder’s Theorem is also presented. This alternate proof does not use normal labellings, instead we use some structural properties of a realizer of the incidence poset to deduce the result. Some applications and a generalization of one implication of Schnyder’s Theorem are also presented in this work. Normal labellings of plane triangulations can be used to obtain a barycentric embedding of a plane triangulation, and they also induce a partition of the edge set of a plane triangulation into edge disjoint trees. These two applications of Schnyder’s Theorem and a third one, relating realizers of the incidence poset and canonical orderings to obtain a compact drawing of a graph, are also presented. A generalization, to abstract simplicial complexes, of one of the implications of Schnyder’s Theorem was proved by Ossona de Mendez. This generalization is also presented in this work. The concept of order labelling is also introduced and we show some similarities of the order labelling and the normal labelling. Finally, we conclude this work by showing the source code of some implementations done in Sage.

No description available.

Cette thèse est consacrée à l’étude combinatoire, algébrique et homologique des hyperarbres et des partitions semi-pointées. Nous étudions plus précisément des structures algébriques et homologiques construites à partir des hyperarbres, puis des partitions semi-pointées.Après un bref rappel des notions utilisées, nous utilisons la théorie des espèces de structure afin de déterminer l’action du groupe symétrique sur l’homologie du poset des hyperarbres. Cette action s’identifie à l’action du groupe symétrique liée à la structure anti-cyclique de l’opérade PreLie. Nous raffinons ensuite nos calculs sur une graduation de l’homologie, appelée homologie de Whitney. Cette étude motive l'introduction de la notion d’hyperarbre aux arêtes décorées par une espèce. Une bijection des hyperarbres décorés avec des arbres en boîtes et des partitions décorées permet d’obtenir une formule close pour leur cardinal, à l’aide d’un codage de Prüfer. Nous adaptons ensuite les méthodes de calcul de caractères sur les algèbres de Hopf d’incidence, introduites par W. Schmitt dans le cas de familles de posets bornés, à des familles de posets non bornés vérifiant certaines propriétés. Nous appliquons ensuite cette adaptation aux posets des hyperarbres. Enfin, au cours de notre étude une généralisation des posets des partitions et des posets des partitions pointées apparaît : les poset des partitions semi-pointées. Nous montrons que ces posets sont aussi Cohen-Macaulay, avant de déterminer à l’aide de la théorie des espèces une formule close pour la dimension de l’unique groupe d’homologie non trivial de ces posets / This thesis is dedicated to the combinatorial, algebraic and homological study of hypertrees and semi-pointed partitions. More precisely, we study algebraic and homological structures built from hypertrees and semi-pointed partitions. After recalling briefly the notions needed, we use the theory of species of structures to compute the action of the symmetric group on the homology of the hypertree posets. This action is the same as the action of the symmetric group linked with the anticyclic structure of the PreLie operad. We refine our computations on a grading of the homology : Whitney homology. This study is a motivation for the introduction of the notion of edge-decorated hypertrees. A one-to-one correspondence of decorated hypertrees with box trees and decorated partitions enables us to compute a close formula for the cardinality of decorated hypertrees, thanks to a Prüfer code. Moreover, we adapt computation methods of characters on incidence Hopf algebras, introduced by W. Schmitt for families of bounded posets, to families of unbounded posets satisfying some additional properties, called triangle and diamond posets. We apply these results to the hypertree posets. Finally, we unveil a new family of posets : the semi-pointed partition posets, which generalize both partition posets and pointed partition posets. We show the Cohen-Macaulayness of these posets and obtain, thanks to species theory, a closed formula for the dimension of its unique homology group, which extend the ones established for partition posets and pointed partition posets

Made available in DSpace on 2015-03-26T13:45:37Z (GMT). No. of bitstreams: 1 texto completo.pdf: 727797 bytes, checksum: 105934c0f62e07cc0326f43884b69ff5 (MD5) Previous issue date: 2014-02-17 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this Work, frorn a generalization of the metric Hamming for a Weighted metric by a partial order, We deñne the poset spaces and We study linear NMDS Codes in such spaces, gaining Characterizations for these. With the aid Of such Charac- terizations, We present tWO applications With respect to distributionsz the Weight distribution of a Code and, in particular Case Of the rnetric Obtained by a poset Rosenblomm-Tsfasman, the distribution of points in the unit Cube U" = [0,1) . We also provide sorne Constructions Of NMDS Codes in Rosenbloom-Tsfasman spaces. / Neste trabalho, a partir de uma generalização da métrica de Hamming por urna métrica ponderada por uma Ordem parciaL deñnimos os espaços poset e estu- damos os Códigos lineares NMDS em tais espaços, Obtendo Caracterizações para estes. Com 0 auxílio de tais Caracterizações, apresentamos duas aplicações Com respeito à distribuiçõesz a distribuição de pesos de um Código e, no Caso parti- Cular da métrica obtida por um poset Rosenblomm-Tsfasman, a distribuição de pontos no Cubo unitário U = [0,1)". Fornecemos também algumas Construções de Códigos NMDS em espaços Rosenbloom-Tsfasman.

<p>In this thesis we generalize the well-known connections between closure operators, closure systems and complete lattices. We introduce a special kind of a partial closure operator, named sharp partial closure operator, and show that each sharp partial closure operator uniquely corresponds to a partial closure&nbsp; system. We further introduce a special kind of a partial clo-sure system, called principal partial closure system, and then prove the representation theorem for ordered sets with respect to the introduced partial closure operators and partial closure systems.<br />Further, motivated by a well-known connection between matroids and geometric lattices, given that the notion of matroids can be naturally generalized to partial matroids (by dening them with respect to a partial closure operator instead of with respect to a closure operator), we dene geometric poset, and show that there is a same kind of connection between partial matroids and geometric posets as there is between matroids and geometric lattices. Furthermore, we then dene semimod-ular poset, and show that it is indeed a generalization of semi-modular lattices, and that there is a same kind of connection between semimodular and geometric posets as there is between<br />semimodular and geometric lattices.</p><p>Finally, we note that the dened notions can be applied to im-plicational systems, that have many applications in real world,particularly in big data analysis.</p> / <p>U ovoj tezi uop&scaron;tavamo dobro poznate veze između operatora zatvaranja, sistema zatvaranja i potpunih mreža. Uvodimo posebnu vrstu parcijalnog operatora zatvaranja, koji nazivamo o&scaron;tar parcijalni operator zatvaranja, i pokazujemo da svaki o&scaron;tar parcijalni operator zatvaranja jedinstveno korespondira parcijalnom sistemu zatvaranja. Dalje uvodimo posebnu vrstu parcijalnog sistema zatvaranja, nazvan glavni parcijalni sistem zatvaranja, a zatim dokazujemo teoremu reprezentacije za posete u odnosu na uvedene parcijalne operatore zatvaranja i parcijalne sisteme zatvaranja. Dalje, s obzirom na dobro poznatu vezu između matroida i geometrijskih mreža, a budući da se pojam matroida može na prirodan nacin uop&scaron;titi na parcijalne&nbsp; matroide (defini&scaron;ući ih preko parcijalnih operatora zatvaranja umesto preko operatora&nbsp; zatvaranja), defini&scaron;emo geometrijske uređene skupove i pokazujemo da su povezani sa parcijalnim matroidima na isti način kao &scaron;to su povezani i matroidi i&nbsp; geometrijske mreže. Osim toga, defini&scaron;emo polumodularne uređene skupove i pokazujemo da su oni zaista uop&scaron;tenje polumodularnih mreža i da ista veza postoji&nbsp; između polumodularnih i geometrijskih poseta kao &scaron;to imamo između polumodularnih i geometrijskih mreža. Konačno, konstatujemo da definisani pojmovi&nbsp; mogu biti primenjeni na implikacione sisteme, koji imaju veliku primenu u realnom svetu, posebno u analizi velikih podataka.</p>