### 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 3

### 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 3

### 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

Wednesday 42 Dilworthls Theorem and Graph Theory A chain cover of a poset P is a collection of chains whose union is P Theorem 1 Dilworth s Theorem In any nite poset the minimum size of a chain couer equals the maximum size of an antichain If we switch chain 7 and antichain the result remains true and becomes nearly trivial Proposition 2 Trivial Proposition In any nite poset the minimum size of an antichain couer equals the maximum size of an chain This is much easier to prove than Dilworth s Theorem Proof For the 2 direction if G is a chain and A is an antichain cover then no antichain in A can contain more than one element of C so A Z On the other hand let A as E P the longest chain headed by as has length i then is an antichain cover whowe cardinality equals the length of the longest chain in P B These theorems have graph theoretic consequences The chromatic number xG of a graph G is the smallest number k such that G has a proper h coloring The clique number wG is the largest size of a clique in G a set of pairwise adjacent vertices Since each vertex in a clique must be assigned a different color it follows that 1 MG 2 MG always however equality need not hold for instance for a cycle of odd length The graph G is called perfect if wH xH for every induced subgraph H Q G De nition 1 Let P be a nite poset lts comparability graph Gp to be the graph G with vertices P and edges myleyorrrZZl lt doesnlt matter whether or not we require the chains to be pairwise disjoint Equivalently G p is the underlying undirected graph othe transitive closure of the Hasse diagram of P The incomparability graph G p is the complement of G p that is x y are adjacent if and only if they are incomparable For example if P is the poset Whose Hasse diagram is shown on the left then Gp is P plus the edges f f d c A A f b e a a b c a d b e c P GP GP A chain in P corresponds to a clique in G p and to a coclique in G p Lik vise an antichain in P corresponds to a coclique in G p and to a clique in G p Observe that a covering of the vertex set of a graph by cocliques is exactly the same thing as a proper coloring Therefore the Trivial Proposition and Dilvvorth s Theorem say respectively that Theorem 3 Comparability and incomparability graphs of posets are perfect Theorem 4 Perfect Graph Theorem LovasZ 1972 Let G be a nite graph Then G is perfect if and only if G is perfect Theorem 5 Strong Perfect Graph Theorem SeymourChudnovsky 2002 Let G be a nite graph Then G is perfect if and only if it has no obuious bad counterexamples ie induced subgraphs of the form C or G where r 2 5 is odd The GreeneKleit man Theorem There is a wonderful generalization of Dilvvorth s theorem due to C Greene and D Kleitman 1976 Theorem 6 Let P be a nite poset De ne two sequences ofpositiue integers A12g aa1a2am by A1Akmax01UU0k CZ QP chains u1 ak maxA1 U UAkz A Q P disjoint antichains Then 1 A and u are both partitions of P 239e weakly decreasing sequences whose sum is 2 A and u are conjugates 239e Mij A121 For example consider the following poset Then A 372272 and u 441 Dilworth s Theorem is now just the special case M E

### 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."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### 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.