Class Note for MATH 796 at KU 3
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
Report this Material
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
Are you sure you want to buy this material for
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'