If you want to know what motivated me to create TrueShelf (an AI powered adaptive learning platform) and the future of learning, please read my interview on Edsurge.
Wish you all a Very Happy New Year. Here is a list of my 10 favorite open problems for 2014. They belong to several research areas inside discrete mathematics and theoretical computer science. Some of them are baby steps towards resolving much bigger open problems. May this new year shed new light on these open problems.
- 1. Combinatorics : Prove that trees with diameter 6 are graceful. (see earlier posts graceful tree conjecture, graceful diameter-6 trees).
- 2. Optimization : Improve the approximation factor for the undirected graphic TSP. The best known bound is 7/5 by Sebo and Vygen.
- 3. Algorithms : Prove that the tree-width of a planar graph can be computed in polynomial time (or) is NP-complete.
- 4. Fixed-parameter tractability : Treewidth and Pathwidth are known to be fixed-parameter tractable. Are directed treewidth/DAG-width/Kelly-width (generalizations of treewidth) and directed pathwidth (a generalization of pathwidth) fixed-parameter tractable ? This is a very important problem to understand the algorithmic and structural differences between undirected and directed width parameters.
- 5. Space complexity : Is Planar ST-connectvity in logspace ? This is perhaps the most natural special case of the NL vs L problem. Planar ST-connectivity is known to be in . Recently, Imai, Nakagawa, Pavan, Vinodchandran and Watanabe proved that it can be solved simultaneously in polynomial time and approximately O(√n) space.
- 6. Metric embedding : Is the minor-free embedding conjecture true for partial 3-trees (graphs of treewidth 3) ? Minor-free conjecture states that “every minor-free graph can be embedded in with constant distortion. The special case of planar graphs also seems very difficult. I think the special case of partial 3-trees is a very interesting baby step.
- 7. Structural graph theory : Characterize pfaffians of tree-width at most 3 (i.e., partial 3-trees). It is a long-standing open problem to give a nice characterization of pfaffians and design a polynomial time algorithm to decide if an input graph is a pfaffian. The special of partial 3-trees is an interesting baby step.
- 8. Structural graph theory : Prove that every minimal brick has at least four vertices of degree three. Bricks and braces are defined to better understand pfaffians. The characterization of pfaffian braces is known (more generally characterization of bipartite pfaffians is known). To understand pfaffians, it is important to understand the structure of bricks. Norine,Thomas proved that every minimal brick has at least three vertices of degree three and conjectured that every minimal brick has at least cn vertices of degree three.
- 9. Communication Complexity : Improve bounds for the log-rank conjecture. The best known bound is
- 10. Approximation algorithms : Improve the approximation factor for the uniform sparsest cut problem. The best known factor is .
Here are my conjectures for 2014 🙂
- Weak Conjecture : at least one of the above 10 problems will be resolved in 2014.
- Conjecture : at least five of the above 10 problems will be resolved in 2014.
- Strong Conjecture : All of the above 10 problems will be resolved in 2014.
Have fun !!
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
- Add source or level (high-school/undergraduate/graduate/research).
- 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.
- Add any post to your Favorites
- 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 facebook, twitter and google+. Here is a screenshot highlighting the important features.
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 :
If you know any interesting Erdos links, leave a comment.
Here is a painting of Paul Erdos, I made couple years back.
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.
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.
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 , is defined to be , if and to be , if . Here is the number of components of .
Conjecture (Chvatal 1973) : There exists a positive real number such that for every graph , implies is Hamiltonian.
3. Perfect Matchings and Bipartite Graphs
Theorem : Let be a set, and suppose that for . Let be a bipartite graph such that
b) has a perfect matching , and
c) if any edge of is deleted, property (b) fails to hold in the resulting graph.
Then, the number of vertices in with degree is at most .
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 denote the minimum number of perfect matchings a k-regular bipartite graph on 2n points can have. Then, .
5. Elementary Graphs
Conjecture : For there exist constants and such that every k-regular elementary graph on 2n vertices, without forbidden edges , contains at least perfect matchings. Furthermore as .
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 .
Theorem : A graph is perfect if and only if it does not contain, as an induced subgraph, an odd hole or an odd antihole.
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.
Let’s see how TrueShelf evolves.
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.
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 , 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 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 .
Exercise : Construct a family of nonempty sets that does not have a sunflower.
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 fixed finite field.
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 nonempty sets, each of cardinality l or less has a sunflower”. This conjecture is still open. It is open even for p=3.
- [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]