The probabilistic method - reference to less challenging questions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T23:27:02Z http://mathoverflow.net/feeds/question/31760 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31760/the-probabilistic-method-reference-to-less-challenging-questions The probabilistic method - reference to less challenging questions Yiftach Barnea 2010-07-13T20:13:52Z 2010-07-14T00:28:30Z <p>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).</p> <p>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. </p> <p><strong>Clarification</strong>: 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. </p> http://mathoverflow.net/questions/31760/the-probabilistic-method-reference-to-less-challenging-questions/31771#31771 Answer by Ravi Boppana for The probabilistic method - reference to less challenging questions Ravi Boppana 2010-07-13T22:37:44Z 2010-07-13T22:37:44Z <p>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 <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1943887#p1943887" rel="nofollow">here</a>. </p> <p>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. </p> http://mathoverflow.net/questions/31760/the-probabilistic-method-reference-to-less-challenging-questions/31780#31780 Answer by Charles Chen for The probabilistic method - reference to less challenging questions Charles Chen 2010-07-14T00:28:30Z 2010-07-14T00:28:30Z <p>We dealt with the probabilistic method in our undergrad randomized algorithms class at Berkeley, and used <a href="http://www.amazon.com/Probability-Computing-Randomized-Algorithms-Probabilistic/dp/0521835402" rel="nofollow">Mitzenmacher's book</a>. 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. </p> <p>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.</p>