Hostname: page-component-74656f9884-54qdv Total loading time: 0 Render date: 2026-11-09T23:18:27.591Z Has data issue: false hasContentIssue false
  • English
  • Français

Perfect Graphs of Fixed Density: Counting and Homogeneous Sets

Published online by Cambridge University Press:  14 May 2012

JULIA BÖTTCHER ,
ANUSCH TARAZ  and
ANDREAS WÜRFL
JULIA BÖTTCHER
Affiliation:
Department of Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, UK (e-mail: j.boettcher@lse.ac.uk)
ANUSCH TARAZ
Affiliation:
Zentrum Mathematik, Technische Universität München, Boltzmannstraße 3, D-85747 Garching bei München, Germany (e-mail: taraz@ma.tum.de, wuerfl@ma.tum.de)
ANDREAS WÜRFL
Affiliation:
Zentrum Mathematik, Technische Universität München, Boltzmannstraße 3, D-85747 Garching bei München, Germany (e-mail: taraz@ma.tum.de, wuerfl@ma.tum.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

For c ∈ (0,1) let n(c) denote the set of n-vertex perfect graphs with density c and let n(c) denote the set of n-vertex graphs without induced C5 and with density c.

We show that \[\lim_{n\to\infty}\log_2 |\cP_n(c)|/\binom{n}{2}=\lim_{n\to\infty}\log_2 |\cC_n(c)|/\binom{n}{2}=h(c)\] with otherwise, where H is the binary entropy function.

Further, we use this result to deduce that almost all graphs in n(c) have homogeneous sets of linear size. This answers a question raised by Loebl and co-workers.

Keywords

Primary 05C3005C6905C17

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 5 , September 2012 , pp. 661 - 682
Copyright
Copyright © Cambridge University Press 2012

References

[1]Alekseev, V. E. (1993) Range of values of entropy of hereditary classes of graphs. Discrete Math. Appl. 3 191–199.CrossRefGoogle Scholar
[2]Alon, N., Balogh, J., Bollobás, B. and Morris, R. (2011) The structure of almost all graphs in a hereditary property. J. Combin. Theory Ser. B 101 85–110.CrossRefGoogle Scholar
[3]Alon, N., Fischer, E., Krivelevich, M. and Szegedy, M. (2000) Efficient testing of large graphs. Combinatorica 20 451–476.CrossRefGoogle Scholar
[4]Alon, N. and Shapira, A. (2008) A characterization of the (natural) graph properties testable with one-sided error. SIAM J. Comput. 37 1703–1727.CrossRefGoogle Scholar
[5]Balogh, J., Bollobás, B. and Simonovits, M. (2004) The number of graphs without forbidden subgraphs. J. Combin. Theory Ser. B 91 1–24.CrossRefGoogle Scholar
[6]Bollobás, B. and Thomason, A. (1997) Hereditary and monotone properties of graphs. In The Mathematics of Paul Erdös II (Graham, R. L. and Nešetřil, J., eds), Vol. 14 of Algorithms and Combinatorics, Springer, pp. 70–78.CrossRefGoogle Scholar
[7]Bollobás, B. and Thomason, A. (2000) The structure of hereditary properties and colourings of random graphs. Combinatorica 20 173–202.Google Scholar
[8]Chudnovsky, M., Robertson, N., Seymour, P. and Thomas, R. (2006) The strong perfect graph theorem. Ann. Math. 164 51–229.CrossRefGoogle Scholar
[9]Erdős, P., Frankl, P. and Rödl, V. (1986) The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs Combin. 2 113–121.CrossRefGoogle Scholar
[10]Erdős, P. and Hajnal, A. (1989) Ramsey-type theorems. Discrete Appl. Math. 25 37–52.CrossRefGoogle Scholar
[11]Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 1087–1091.CrossRefGoogle Scholar
[12]Gyárfás, A. (1997) Reflections on a problem of Erdős and Hajnal. In The Mathematics of Paul Erdős II (Graham, R. L. and Nešetřil, J., eds), Vol. 14 of Algorithms and Combinatorics, Springer, pp. 93–98.Google Scholar
[13]Hardy, G. H., Littlewood, J. E. and Pólya, G. (1988) Inequalities, Cambridge Mathematical Library, Cambridge University Press, reprint of the 1952 edition.Google Scholar
[14]Jukna, S. (2001) Extremal Combinatorics, Springer.CrossRefGoogle Scholar
[15]Komlós, J., Shokoufandeh, A., Simonovits, M. and Szemerédi, E. (2000) The regularity lemma and its applications in graph theory. In Theoretical Aspects of Computer Science (Khosrovshahi, G. B., Shokoufandeh, A. and Shokrollahi, M. A., eds), Vol. 2292 of Lecture Notes in Computer Science, Springer, pp. 84–112.Google Scholar
[16]Loebl, M., Reed, B., Scott, A., Thomason, A. and Thomassé, S. (2010) Almost all F-free graphs have the Erdős–Hajnal property. In An Irregular Mind, Vol. 21 of Bolyai Society Mathematical Studies, Springer, pp. 405–414.CrossRefGoogle Scholar
[17]Marchant, E. and Thomason, A. (2011) The structure of hereditary properties and 2-coloured multigraphs. Combinatorica 31 85–93.CrossRefGoogle Scholar
[18]Prömel, H. J. and Steger, A. (1991) Excluding induced subgraphs: Quadrilaterals. Random Struct. Alg. 2 55–72.CrossRefGoogle Scholar
[19]Prömel, H. J. and Steger, A. (1992) Almost all {B}erge graphs are perfect. Combin. Probab. Comput. 1 53–79.CrossRefGoogle Scholar
[20]Prömel, H. J. and Steger, A. (1992) Excluding induced subgraphs III: A general asymptotic. Random Struct. Alg. 3 19–31.CrossRefGoogle Scholar
[21]Szemerédi, E. (1975) On sets of integers containing no k elements in arithmetic progression. Acta Arithmetica 27 199–245.CrossRefGoogle Scholar
[22]Thomason, A. (2011) Graphs, colours, weights and hereditary properties. In Surveys in Combinatorics 2011, Vol. 392 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 333–364.CrossRefGoogle Scholar
[23]Turán, P. (1941) On an extremal problem in graph theory. Matematicko Fizicki Lapok 48 436–452.Google Scholar