Perfect Graphs of Fixed Density: Counting and Homogeneous Sets

Autor(es)

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

Afiliação do(s) autor(es)

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

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

• Tipo de documento: Artigo Científico
• Fonte: COMBINATORICS PROBABILITY & COMPUTING; v. 21, n. 5, p. 661-682, SEP 2012.
• Citações Web of Science: 1

Resumo

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)

• Processo FAPESP: 09/17831-7 - Problemas de imersão e empacotamento em teoria extremal dos grafos
• Beneficiário: Julia Boettcher
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado