TrueShelf 1.0

One year back (on 6/6/12) I announced a beta version of TrueShelf, a social-network for sharing exercises and puzzles especially in mathematics and computer science. After an year of testing and adding new features, now I can say that TrueShelf is out of beta.

TrueShelf turned out to be a very useful website. When students ask me for practice problems (or books) on a particular topic, I simply point them to trueshelf and tell them the tags related to that topic. When I am advising students on research projects, I first tell them to solve all related problems (in the first couple of weeks) to prepare them to read research papers.

Here are the features in TrueShelf 1.0.

• Post an exercise (or) multiple-choice question (or) video (or) notes.
• Solve any multiple-choice question directly on the website.
• Add topic and tags to any post
• Show text-books related to a post
• Show related posts for every post.
• View printable version (or) LaTex version of any post.
• Email / Tweet / share on facebook (or) Google+ any post directly from the post.
• Like (a.k.a upvote) any post.

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 facebooktwitter and google+. Here is a screenshot highlighting the important features.

Happy Birthday Paul Erdos

Today (March 26 2013) is the 100th Birthday of Paul Erdos. The title of my Blog is inspired by one of his famous sayings “My Brain is Open”. In one of my earlier posts I mentioned a book titled “The Man Who Loved Only Numbers” about his biography.

Paul Erdos published more than 1500 papers. Most of them left a legacy of open problems and conjectures. What is your favorite open problem from Erdos’s papers ? Leave a comment. Hope we can solve some of his open problems during this special year.

Here are some interesting links :

Here is a painting of Paul Erdos, I made couple years back.

Recreational Math Books – Part II

In my previous post (see here) I mentioned some interesting puzzle books. In today’s post I will mention different type of recreational math books i.e., biographical books. Here are my top three books in this category. They are must-read books for anybody even remotely interested in mathematics.

There are about three mathematics : (1)  Andrew Wiles, whose determination to solve Fermat’s Last Theorem inspires future generations and gives a strong message that patience and focus are two of the most important assets that every mathematician should posses. (2) Paul Erdos, whose love for mathematics is so deep and prolific and (3) Srinivasa Ramanujan, whose story is different from any other mathematician ever.

This is one of the first “recreational” books I read. It starts with the history of Fermat’s last theorem (FLT), discusses the life style of early mathematicians and moves on to talk about Andrew Wiles’s 8 year long journey proving FLT. Watch this BBC documentary for a quick overview of Andrew Wiles’s story.

Paul Erdos is one of the greatest and most prolific mathematicians ever. The title of my blog is inspired by one of his famous sayings “My Brain is Open”. I don’t want to reveal any details of this book. You will enjoy this book more if you read it without knowing anything about Paul Erdos. I should warn you that there are some really tempting open problems in this book. When I first read this book (during my PhD days) I spent almost one full semester reading papers related to Twin Prime Conjecture and other number-theoretic problems. I also wrote a paper titled “A generalization of Erdos’s proof of Bertrand-Chebyshev’s theorem”. Watch this documentary “N is a number” for a quick overview of Paul Erdos’s story.

This is a very dense book. I bought it five years back and only recently finished reading it. This books covers lots of “topics” : south indian life-style, Hardy’s life, Ramanujan’s proofs and his flawed proofs, his journey to work with Hardy, his health struggles etc. It is definitely worth-reading to know the details of Ramanujan’s passion for mathematics.

—————————————————————————————————————————————

Recreational Math Books – Part I

Most of us encounter math puzzles during high-school. If you are really obsessed with puzzles, actively searching and solving them, you will very soon run out of puzzles !! One day you will simply realize that you are not encountering any new puzzles. No more new puzzles. Poof. They are all gone. You feel like screaming “Give me a new puzzle“. This happened to me around the end of my undergrad days. During this phase of searching for puzzles, I encountered Graceful Tree Conjecture and realized that there are lots of long-standing open “puzzles”. I don’t scream anymore. Well… sometimes I do scream when my proofs collapse. But that’s a different kind of screaming.

Sometimes, I do try to create new puzzles. Most of the puzzles I create are either very trivial to solve (or) very hard and related to long-standing conjectures. Often it takes lots of effort and ingenuity to create a puzzle with right level of difficulty.

In today’s post, I want to point you to some of the basic puzzle books that everybody should read. So, the next time you see a kid screaming ”Give me a new puzzle“, simply point him/her to these books. Hopefully they will stop screaming for sometime. If they comeback to you soon, point them to Graceful Tree Conjecture

I will mention more recreational math books in part 2 of this blog post.

Open Problems from Lovasz and Plummer’s Matching Theory Book

I always have exactly one bed-time mathematical book to read (for an hour) before going to sleep. It helps me learn new concepts and hopefully stumble upon interesting open problems. Matching Theory by Laszlo Lovasz and Michael D. Plummer has been my bed-time book for the last six months. I bought this book 3 years back (during my PhD days) but never got a chance to read it. This book often disappears from Amazon’s stock. I guess they are printing it on-demand.

If you are interested in learning the algorithmic and combinatorial foundations of Matching Theory (with a historic perspective), then this book is a must read. Today’s post is about the open problems mentioned in Matching Theory book. If you know the status (or progress) of these problems, please leave a comment.

—————————————————————————-

1 . Consistent Labeling and Maximum Flow

Conjecture (Fulkerson) : Any consistent labelling procedure results in a maximum flow in polynomial number of steps.

—————————————————————————-

2. Toughness and Hamiltonicity

The toughness of a graph $G$, $t(G)$ is defined to be $+\infty$, if $G = K_n$ and to be $min(|S|/c(G-S))$, if $G \neq K_n$. Here $c(G-S)$ is the number of components of $G-S$.

Conjecture (Chvatal 1973) : There exists a positive real number $t_0$ such that for every graph $G$, $t(G) \geq t_0$ implies $G$ is Hamiltonian.

—————————————————————————-

3. Perfect Matchings and Bipartite Graphs

Theorem : Let $X$ be a set, $X_1, \dots, X_t \subseteq X$ and suppose that $|X_i| \leq r$ for $i = 1, \dots, t$. Let $G$ be a bipartite graph such that

a) $X \subseteq V(G)$,

b) $G - X_i$ has a perfect matching , and

c) if any edge of $G$ is deleted, property (b) fails to hold in the resulting graph.

Then, the number of vertices in $G$ with degree $\geq 3$ is at most $r^3 {t \choose 3}$.

Conjecture : The conclusion of the above theorem holds for non-bipartite graphs as well.

—————————————————————————-

4. Number of Perfect Matchings

Conjecture (Schrijver and W.G.Valiant 1980) : Let $\Phi(n,k)$ denote the minimum number of perfect matchings a k-regular bipartite graph on 2n points can have. Then, $\lim_{n \to \infty} (\Phi(n,k))^{\frac{1}{n}} = \frac{(k-1)^{k-1}}{k^{k-2}}$.

—————————————————————————-

5. Elementary Graphs

Conjecture : For $k \geq 3$ there exist constants $c_1(k) > 1$ and $c_2(k) > 0$ such that every k-regular elementary graph on 2n vertices, without forbidden edges , contains at least $c_2(k){\cdot}c_1(k)^n$ perfect matchings. Furthermore $c_1(k) \to \infty$ as $k \to \infty$.

—————————————————————————-

6. Number of colorations

Conjecture (Schrijver’83) : Let G be a k-regular bipartite graph on 2n vertices. Then the number of colorings of the edges of G with k given colors is at least $(\frac{(k!)^2}{k^k})^n$.

—————————————————————————-

Theorem : A graph is perfect if and only if it does not contain, as an induced subgraph, an odd hole or an odd antihole.

—————————————————————————-

TrueShelf

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 trueshelf.com to make these exercises public. In 2011, towards the end of my PhD, I started using the trueshelf.com domain and made a public blog so that anybody can post an exercise. [ Notice that I did not use the trueshelf.com 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 np2n. 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 knp(k+1)n for all integer n>1 and k <=n ?

A positive answer for kn 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 < kn, 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 ?

The Sunflower Lemma

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.

• 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.