A connection between a convex programming problem and the LYM property on perfect graphs

✍ Scribed by Victor K. Wei

• Publisher: John Wiley and Sons
• Year: 1988
• Tongue: English
• Weight: 772 KB
• Volume: 12
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190120413

✦ Synopsis

We derive three equivalent conditions on a perfect graph concerning the optimal solution of a convex programming problem, the length-width inequality, and the simultaneous vertex covering by cliques and anticliques. By combining proof techniques including Lagrangian dual, Dilworth's Theorem, and Kuhn-Tucker Theorem, we establish a strong connection between the three topics. This provides new insights into the structure of perfect graphs. The famous Lubell-Yamamoto-Meschalkin (LYM) Property or Sperner Property for partially ordered sets is a specialization of our results to a subclass of perfect graphs.