On a method for random graphs

Zbigniew Palka, Andrzej Rucinśki, Joel Spencer

Research output: Contribution to journalArticle

Abstract

In this paper we examine a method for establishing an almost sure existence of a subgraph of a random graph with a given subgraph property. Since the method has been abused in the literature, we state some conditions under which it can be safely used. As an illustration we apply the method to induced cycles, maximal induced trees and arbitrary subgraphs of a random graph Kn,p.

Original languageEnglish (US)
Pages (from-to)253-258
Number of pages6
JournalDiscrete Mathematics
Volume61
Issue number2-3
DOIs
StatePublished - Sep 1986

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On a method for random graphs'. Together they form a unique fingerprint.

  • Cite this