13
$\begingroup$

I am teaching a course in combinatorics and large part of it is dedicated to the probabilistic method especially in the case of graphs. The course is an undergraduate level (almost none of the students will pursue a PhD in mathematics).

Last year when I though the course I had very hard time finding appropriate questions for the students. So for instance problems in Alon and Spencer’s book are way too hard. I am looking for textbooks or online notes which contain less challenging problems. For example, problems which are direct implication of a method or problems which are broken down to small parts, etc. If the reference actually has solutions or hints, that will be a nice bonus.

Clarification: After seeing Ravi’s answer I think I should be clearer. Olympiads problems are probably the complement of what I am looking for. They tend to be elementary but tricky. I, on the other hand, look for problems where the method might not be very elementary, but the answer is direct. So for instance, near the end of the course I teach them the Local Lemma. I would like to find 2-3 problems where I can more or less just ask the students to plug in the numbers and use the lemma to deduce the existence of some graph. I then will be happy to give them something more sophisticated but maybe with some hints or broken down to small parts.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

I gave a couple of lectures to some bright high-school students on the probabilistic method. For the lectures, I created a handout of 38 problems with hints at the end. The link is here.

I wouldn't say the problems are easy (many come from olympiads), but maybe some will suit your purposes, especially if you provide the hints.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Hah, I almost commented to say, "Ravi Boppana used to have a good list of questions ...." $\endgroup$
    – JBL
    Commented Jul 13, 2010 at 22:55
5
$\begingroup$

We dealt with the probabilistic method in our undergrad randomized algorithms class at Berkeley, and used Mitzenmacher's book. Chapter 6 is about the probabilistic method and has a bunch of exercises that don't require as much computational yoga as Olympiad problems or Alon and Spencer.

The chapter is mostly about combinatorics, and not about algorithms. For instance, one of the questions in Chapter 6 is to show if $4 \binom{k}{2} \binom{n}{k-2} 2^{1-\binom{k}{2}} \leq 1$, then it's possible to two-color the edges of $K_n$ so there's no monochromatic $K_k$ subgraph, which is a direct application of Lovasz.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .