Probabilistic Methods in Combinatorics

Joel Spencer
Additional contact information
Joel Spencer: Courant Institute

A chapter in Proceedings of the International Congress of Mathematicians, 1995, pp 1375-1383 from Springer

Abstract: Abstract In 1947 Paul Erdős [8] began what is now called the probabilistic method. He showed that if $$\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right){{2}^{{1 - \left( {\begin{array}{*{20}{c}} k \\ 2 \\ \end{array} } \right)}}} n.) In modern lanuage he considered the random graph G(n,.5) as described below. For each k-set S let BS denote the “bad” events that S is either a clique or an independent set. Then Pr[BS] = 21-(k/2) so that ΣPr[BS]

Date: 1995
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-0348-9078-6_132

Ordering information: This item can be ordered from
http://www.springer.com/9783034890786

DOI: 10.1007/978-3-0348-9078-6_132

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().