Let <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D%20=%20(%5Cmathbb%7BP%7D,%20%5Cpreceq)" data-classname="equation_inline" data-title="" /> be a finite poset (partially ordered set) with cardinality <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?n" data-classname="equation_inline" data-title="" />. A linear extension of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> is an order-preserving bijection <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma" data-classname="equation_inline" data-title="" />: <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D%20%5Crightarrow%20%5Bn%5D" data-classname="equation_inline" data-title="" />, that is, if <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?x%20%5Cpreceq%20y" data-classname="equation_inline" data-title="" /> in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> then <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma(x)%20%5Cle%20%5Csigma(y)" data-classname="equation_inline" data-title="" />. We define the poset probability <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" /> as the proportion of linear extensions where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Csigma(%5Calpha)%20%5Cle%20%5Csigma(%5Cbeta)" data-classname="equation_inline" data-title="" />. We are primarily interested in <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" /> for incomparable elements <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha%20%5Cparallel%20%5Cbeta" data-classname="equation" data-title="" />. The probability has significance in areas such as information theory. Let <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?e(%5Cmathbb%7BP%7D)" data-classname="equation_inline" data-title="" /> denote the total number of linear extensions of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" />. We prove that the poset probability can be evaluated as <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)%20=%20%5Cfrac%7B%20%5Csum_%7BT%20%5Cin%20B(%5Calpha,%5Cbeta)%7D%20e(T)%20e(%5Cmathbb%7BP%7D%20%5Csetminus%20(T%20%5Ccup%20%5C%7B%5Calpha%5C%7D))%7D%7Be(%5Cmathbb%7BP%7D)%7D" data-classname="equation" data-title="" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?B(%5Calpha,%5Cbeta)" data-classname="equation_inline" data-title="" /> is the set of order ideals of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" /> without <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha" data-classname="equation" data-title="" /> or <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cbeta" data-classname="equation" data-title="" />, where we can add <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Calpha" data-classname="equation_inline" data-title="" /> to get a new order ideal of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathbb%7BP%7D" data-classname="equation_inline" data-title="" />. The practicality of the preceding formula is explored and we show that <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?T%20%5Cin%20B(%5Calpha,%5Cbeta)%20%5CLeftrightarrow%20%5Cleft%5C%7B%20x%20%7C%20x%20%5Cprec%20%5Calpha%20%5Cright%5C%7D%20%5Csubseteq%20T%20%5Ctext%7B%20and%20%7D%20T%20%5Ctext%7B%20order%20ideal%20of%20%7D%0A%5Cleft%5C%7B%20x%20%7C%20%5Calpha%20%5Cnot%20%5Cpreceq%20x,%5C%20%5Cbeta%20%5Cnot%20%5Cpreceq%20x%7D" data-classname="equation" /> The formula is particularly useful for certain classes of posets such as partition posets which are examined in further detail. We apply the formula to prove that, for all partition posets of shape <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Bn,n%5D" data-classname="equation_inline" data-title="" />, the probability obeys <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P((2,a)%20%5Cpreceq%20(1,a+1))%20=%20%5Cfrac%7B%20C_a%20C_%7Bn-a%7D%7D%20%7BC_n%7D" data-classname="equation" data-title="" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?C_n" data-classname="equation_inline" data-title="" /> is the nth Catalan number and <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?a%20%3C%20n" data-classname="equation_inline" data-title="" />. We also explore how Monte Carlo methods can be used to estimate <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?P(%5Calpha%20%5Cpreceq%20%5Cbeta)" data-classname="equation_inline" data-title="" />.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-187176 |
| Date | January 2022 |
| Creators | Jaldevik, Albin |
| Publisher | Linköpings universitet, Algebra, geometri och diskret matematik, Linköpings universitet, Tekniska fakulteten |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0026 seconds