I have been teaching (courses related to algorithms and complexity) for the past six years (five years as a PhD student at GeorgiaTech, and the past one year at Princeton). One of the most challenging and interesting part of teaching is creating new exercises to help teach the important concepts in an efficient way. We often need lots of problems to include in homeworks, midterms, final exams and also to create practice problem sets.

We do not get enough time to teach all the concepts in class because the number of hours/week is bounded. I personally like to teach only the main concepts in class and design good problem sets so that students can learn the generalizations or extensions of the concepts by solving problems hands-on. This helps them develop their own intuitions about the concepts.

Whenever I need a new exercise I hardly open a physical textbook. I usually search on internet and find exercises from a course website (or) “extract” an exercise from a research paper. There are hundreds of exercises “hidden” in pdf files across several course homepages. Instructors often spend lots of time designing them. If these exercises can reach all the instructors and students across the world in an efficiently-indexed form, that will help everybody. Instructors will be happy that the exercises they designed are not confined to just one course. Students will have an excellent supply of exercises to hone their problem-solving skills.

During 2008, half-way through my PhD, I started collected the exercises I like in a private blog. At the same time I registered the domain to make these exercises public. In 2011, towards the end of my PhD, I started using the domain and made a public blog so that anybody can post an exercise. [ Notice that I did not use the domain for three years. During these three years I got several offers ranging upto $5000 to sell the domain. So I knew I got the right name 🙂 ] Soon, I realized that wordpress is somewhat “static” in nature and does not have enough “social” features I wanted. A screenshot of the old website is shown below.

The new version of TrueShelf is a social website enabling “crowd-sourcing” of exercises in any area. Here is the new logo, I am excited about 🙂

The goal of TrueShelf is to aid both the instructors and students by presenting quality exercises with tag-based indexing. Read the TrueShelf FAQ for more details. Note that we DO NOT allow users to post solutions. Each user may add his own “private” solution and notes to any exercise. I am planning to add more features soon.

In the long-run, I see TrueShelf becoming a “Youtube for exercises”. Users will be able to create their own playlists of exercises (a.k.a problem sets) and will be recommended relevant exercises. Test-preparation agencies will be able to create their own channels to create sample tests.

Feel free to explore TrueShelf, contribute new exercises and let me know if you have any feedback (or) new features you want to see. You can also follow TrueShelf on facebook, twitter and google+.

Let’s see how TrueShelf evolves.

A Generalization of Erdos’s Proof of Bertrand-Chebyshev Theorem

Bertrand’s postulate states that for every positive integer n, there is always at least one prime psuch that n < p < 2n. This was proved by Chebyshev in 1850, Ramanujan in 1919 and Erdos in 1932.

Legendre’s conjecture states that there is a prime number between n2 and (n+1)2 for every positive integer n. It is one of the four Landau’s problems, considered as four basic problems about prime numbers. The other three problems are

  • Goldbach’s conjecture : Every even integer n > 2 can be written as the sum of two primes ?
  • Twin prime conjecture : There are infinitely many primes p such that p+2 is prime ?
  • Are there infinitely many primes p such that p-1 is a perfect square ?

All these problems are open till date !! Lets look at the following generalization of the Bertrand’s postulate :

Does there exist a prime number p, such that kn < p < (k+1)n for all integer n>1 and k <=n ?

A positive answer for k = n would prove Legendre’s conjecture. Recently I generalized Erdos’s Proof of Bertrand-Chebyshev’s Theorem and proved the following theorem :

Theorem : For any integer 1 < k < n, there exists a number N(k) such that for all n >=N(k), there is at least one prime between kn and (k+1)n.

Like Erdos’s Proof, my generalization uses elementary combinatorial techniques without appealing to the prime number theorem. An initial draft is available on my homepage.

I have the following question :

Are there infinitely many primes p such that p+k is prime ?

Is the answer known for any fixed k > 2 ? What if k is allowed to depend on p ? If you know any papers addressing such questions, please leave a comment.

The Sunflower Lemma

Today’s post is about the Sunflower Lemma (a.k.a the Erdos-Rado Lemma). I learnt about Sunflower Lemma while reading Razborov’s Theorem from Papadimitriou’s computational complexity book.

A sunflower is a family of p sets \{P_1,P_2,\dots,P_p\}, called petals, each of cardinality at most l, such that all pairs of sets in the family have the same intersection, called the core of the sunflower.

The Sunflower Lemma : Let Z be a family of more than M=(p-1)^{l}l! nonempty sets, each of cardinality l or less. Then Z must contain a sunflower.

Exercise : Prove the Sunflower Lemma

The best known lower bound on M is (p-1)^l.

Exercise : Construct a family of  (p-1)^l nonempty sets that does not have a sunflower.

We develop counterparts
of the Sunflower Lemma for distributive lattices, graphic matroids, and matroids
representable over a xed nite eld.

Sunflower lemma plays a crucial role in Razborov’s theorem [Razborov’85]. [McKenna’05] generalized the Sunflower Lemma for distributive lattices, graphic matroids, and matroids representable over a fi xed fi nite fi eld.

I am not aware of other applications of Sunflower Lemma. If you know any, please leave a comment.

Open problems :

  • Improve the upper/lower bound on M.
  • Erdos and Rado conjectured that “For every fixed p there is a constant C = C(p) such that a family of more than C^{l} nonempty sets, each of cardinality l or less has a sunflower”. This conjecture is still open. It is open even for p=3.

References :

  • [Razborov’85] A. A. Razborov, Some lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl. 31 (1985), 354-357.
  • [McKenna’05] Geoffrey McKenna, Sunflowers in Lattices, The Electronic Journal of Combinatorics Vol.12 2005 [pdf]