Perfect Graphs of Fixed Density: Counting and Homogeneous Sets

Author(s)

Boettcher, Julia ^[1] ; Taraz, Anusch ^[2] ; Wuerfl, Andreas ^[2]

Affiliation

^[1] London Sch Econ, Dept Math, London WC2A 2AE - England

^[2] Tech Univ Munich, Zentrum Math, D-85747 Garching - Germany

• Document type: Journal article
• Source: COMBINATORICS PROBABILITY & COMPUTING; v. 21, n. 5, p. 661-682, SEP 2012.
• Web of Science Citations: 1

Abstract

For c is an element of (0, 1) let P-n(c) denote the set of n-vertex perfect graphs with density c and let C-n(c) denote the set of n-vertex graphs without induced C-5 and with density c. We show that lim(n ->infinity) log(2) vertical bar P-n(c)vertical bar/((n)(2)) - lim(n ->infinity) log(2) vertical bar C-n(c)vertical bar/((n)(2)) - h(c) with h(c) = 1/2 if 1/4 <= c <= 3/4 and h(c) = 1/2 H(vertical bar 2c - 1 vertical bar) otherwise, where H is the binary entropy function. Further, we use this result to deduce that almost all graphs in C-n(c) have homogeneous sets of linear size. This answers a question raised by Loebl and co-workers. (AU)

• FAPESP's process: 09/17831-7 - Embedding and packing problems in extremal graph theory
• Grantee: Julia Boettcher
• Support Opportunities: Scholarships in Brazil - Post-Doctoral