Discrete Structures for Computer Science. Counting, Recursion, and Probability

Аннотация

In this chapter, we introduce some problems that will be solved later in this book. Along the way, we recall some notions from discrete mathematics that you are assumed to be familiar with. These notions are reviewed in more detail in Chapter 2. Ramsey Theory studies problems of the following form. How many elements of a given type must there be so that we can guarantee that some property holds. In this section, we consider the case when the elements are people and the property is “there is a large group of friends or there is a large group of strangers”.