Abstract
I was trying to help a group of school students discover a beautiful theorem in combinatorics. The theorem says: in any sequence of k2+1 distinct numbers, there is either an increasing subsequence of k+1 numbers or a decreasing subsequence of k+1 numbers. The students eventually figured this out. They also figured out why k2 instead of k2+1 would not do: there are sequences of k2 numbers that have neither an increasing nor a decreasing subsequence of k+1 numbers. (Try to build one for k=3.) Just when I thought I had told them everything that I could about the theorem, one of them asked how many such sequences with numbers 1,2, ..., k2 were there. I did not know. I did not want to google. I wanted to understand. I went back to an algorithm I had learnt years ago. It gave me the answer. I understood a little more. I want to tell you what I found, and why that made me happy.
Biodata of the Speaker
Prof. Jaikumar Radhakrishnan is a renowned researcher in the area of theoretical computer science, randomness and computing, quantum computation, combinatorics, and information theory. He was a professor at STCS, TIFR for a long time. Presently he is at ICTS Bangalore. He has been a magnificent mentor to many students, and many of his PhD students are in academia in India and abroad. He was awarded the Shanti Swarup Bhatnagar Prize for Science and Technology (India's highest honour for excellence in science, mathematics, and technology) in 2008. He is also well known for explaining complicated results in an amazingly simple and engaging manner.