### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for MATH 796 at KU

### View Full Document

## 16

## 0

## Popular in Course

## Popular in Department

This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 16 views.

## Reviews for Class Note for MATH 796 at KU

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Friday 11808 Posets De nition A partially ordered set or poset is a set P equipped with a relation 3 that is re exive antisymmetric and transitive That is for all x y 2 E P l x S x re exivity 2 If x S y amd y S x then x y antisymmetry 3 If x S y and y S 2 then x S 2 transitivity We ll usually assume that P is nite Example 1 Boolean algebras Let 1 2 n a standard piece of notation in combinatorics and let Q7 be the power set of We can partially order Q7 by writing S S T if S Q T 123 12 13 23 N A Y The rst two pictures are Hasse diagrams They don t include all relations just the covering relations which are enough to generate all the relations in the poset As you can see on the right including all the relations would make the diagram unnecessarily complicated De nitions Let P be a poset and z y E P o x is covered by y written 95 lt y if x lt y and there exists no 2 such that x lt 2 lt y o The interval from x to y is xy2 P 953233 This is nonempty if and only if x S y and it is a singleton set if and only if x The Boolean algebra Q7 has a unique minimum element namely 3 and a unique maximum element namely Not every poset has to have such elements but if a poset does we ll call them 0 and 1 respectively De nition A poset that has both a O and a l is called bounded An element that covers 0 is called an atom and an element that is covered by l is called a coatorn For example the atoms in Q7 are the singleton subsets of De nition A subset C C P is called a Chain if its elements are pairwise comparable It is called an antichain or clutter if its elements are pairwise incomparable 123 123 123 gt 4 3949 1 2 1 2 1 2 3 1 2 1 chain antichain antichain neither Ranked Posets One of the many nice properties of n is that its elements fall nicely into horizontal slices sorted by their cardinalities Whenever S lt T it is the case that lTl 5 1 A poset for which we can do this is called a ranked poset However we can t de ne ranked in this way because it is tautological Instead De nition A poset is ranked if every maximal chain has the same cardinality A poset is graded if it is ranked and bounded If P is a graded poset its rank function r P A N is de ned as Mac length of any chain from O to 95 Here length measures the number of steps not the number of elements 7 ice edges rather than vertices in the Hasse diagrami Note Maximal chain and maximum chain are not synonyms Maximal means not contained in any other while maximum means of greatest possible size Every maximum chain is certainly maximal but not necessarily vice versaithat s precisely what it means for a poset to be ranked An easy consequence of the de nition is that if x lt y then My Mac 1 proof left to the reader De nition Let P be a ranked poset with rank function r The rankgenerating function of P is the formal power series FPII Z a xeP Thus for each k the coefficient of qlC is the number of elements at rank k We can now say that the Boolean algebra is ranked by cardinality In particular Fae Z 11 1 11 Sch Of course if you expand this polynomial out it is palindromic because the coefficients are a row of Pascal s Triangle That is 7 is ranksymmetric In fact much more is true For any poset P we can de ne the dual poset Pquot by reversing all the order relations or equivalently turning the Hasse diagram upside down It s not hard to prove that the Boolean algebra is selfdual ices 7 E Q from which it immediately follows that it is ranksymmetric The following is a nonranked poset an important example to have around called N5 Example 2 The partition lattice Let ll be the poset of all set partitions of E g two elements of H5 are S 134 2 5 abbr S 134l25 T l3 4 25 abbr T 13l4l25 The sets 134 and 25 are called the blocks of S We can impose a partial order on Hn by putting T S S if every block of T is contained in a block of S for short T re nes S 1234 123 123M 124m 134m 234m 12 34 13 24 1423 ampMV39 lt t v gtVr 12w 1 23 13m 1234 13W 23m4 1423 24MB 34m2 2 3 1l2l3l4 o The covering relations are of the form merge two blocks into one o H is graded With 0 1 2 n and l 12 n The rank function is MS n7 o The coef cients of the rankgenerating function of H are the Stirling numbers of the second kind Sn k number of partitions of into k blocks That is Fnq FHJQ 2301 Mamet k1 For example F301 1 Sq q2 and F401 1 6q 7112 q

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.