Introduction to Ramsey Theory: Students' Projects

Subsection 8.1.1 Interviewee background and how they developed a passion for mathematics

Dr. Sahasrabudhe:

I always liked math and it was always very fun, but I didn?t realize there was this whole world of proving and problem-solving in math. I never got a sense of how deep it was. I remember my mom got me a book of the Fibonacci Numbers when I was younger that showed connections between things, but it didn't really get into the depth of it.

However, I had a friend whom I would teach music theory and he would teach me math.

In further conversations, he had some questions in biology that happened to be related to graphs. There was this question he needed for his biology research relating to the degree sequence of a graph. The question was a form of is there a graph with a certain degree sequence. That was my first question, which we didn't know was graph theory at the time, that we ultimately solved. It?s not hard to solve by the way and it was a known problem from ages ago.

I mentioned this problem to somebody, by the time I was at SFU, and they told me this was a combinatorics problem, which pushed me in the direction of math.

We asked Julian what course at SFU inspired him to become a mathematician. He goes on about really liking calculus and real analysis even though they are very “nuts and bolts” courses. He jokingly states he would be too embarrassed to tell any mathematicians he knows about this. However, his connection to a mentor struck the most.

Dr. Sahasrabudhe:

I had a great TA, who I am still friends with to this day. We had a lot of conversations about mathematics and this is where for the first time I got a good feeling about the bigger mathematical universe.

This was the beginning.

We heard that in high school in Russia, there are a lot of mathematic clubs. I heard that the elusive Grigori Perelman was part of one of these and they tackled subjects including graph theory. Were you ever part of one of these clubs and if not, how did your interest in mathematics begin?

Dr. Axenovich:

When I started school, it was still the Soviet Union and we were involved in the Space Program and I think that was a political decision hence that's a reason why the mathematics program and education were so strong. I think everyone at that time in the 70s/80s had an excellent mathematics education.

A lot of hours, 6 days of school and every day we had math class. Started from 6th grade, algebra and geometry were separate from regular math classes. I went to a normal school and not a special mathematics school so the only slightly unusual thing for me is when I was in the 4th grade, our class was selected to be the first experimental class to study informatics. The first computers were just coming up, so we got these Apple computers and we got to program as 4th graders.

That was actually really fun.

I actually wanted to do computer science before I switched to mathematics. Later, in high school, I lived close to Novosibirsk State University. Really close, maybe like 400 meters away and I would attend seminars and some lectures at the university. That was good.

Novosibirsk is a place in Siberia where there is a university but also 30 or 40 scientific institutes. It is a scientific area including an institute of mathematics. It is connected to the university but basically, it is an independent entity of research.

It was lucky for me to be around that. No clubs, really, at that time. What I did and what I still think there still is are these math high schools in Russia. Some of them are in person, but some are also online instruction. I lived so close to one of those schools but they didn't let locals in, I could not take part. I could participate in doing the problem solving, so they would send something through mail once a month or so, you would solve it, write your answers down, send it back, and graduate students would correct them and send it back.

It was a lot of fun. There were some problems that you normally wouldn't see in the school curriculum.

Subsection 8.1.2 Ramsey theory and math techniques

Dr. Sahasrabudhe:

I really like the aesthetic aspect of math.

I like Ramsey Theory because the statements are so simple. They are so simple they smash your face right off. For example, you look at a graph and Ramsey Theory says this always happens.

Every time I work on a project, by the way, this is not a hyperbole, I genuinely ask can I explain to myself why this problem is interesting in 2 sentences. If it's more complicated than this I feel it?s not worth my time.

Ramsey Theory is a little bit unfair by this metric because the statements are so beautiful and simple.

We asked Dr. Butler why Pigeonhole Principle is so central to Ramsey Theory and why they both work well together.

Dr. Butler:

If you look at Ramsey Theory and look through the proof it's Pigeonhole Principle. The goal of Ramsey Theory is to say something exists. Likewise, the Pigeonhole Principle is also saying that something exists, so they work well, but of course, there?s a tradeoff. In the Pigeonhole Principle if you have enough of something then it must be true that something happens. So, when you dig into the proof of Ramsey Theory it just boils down to saying if you have a large universe of events, some events are interesting. That really in the end is just the Pigeonhole Principle.

This question is about why proving bounds are important in Ramsey Theory. However, he also does talk a bit about Erdős here and more generally why mathematicians solve questions outside of those posed in the ?real? world.

Dr. Butler:

From a practical standpoint, the application of Ramsey Theory is not so clear. It's not so clear that there is one, but why should that stop mathematicians! Mathematicians don't worry about the application.

Who knows, maybe in a hundred years we'll spot it.

I think it more of wanting to understand behaviour. Erdős was a motivating force for Ramsey Theory for many years. In fact, one of his papers was basically a proof of Ramsey Theory. If you're familiar with the Happy Ending Problem, which is a problem with putting points in the plane. The question asks how many points you need to get a convex polygon within certain vertices. This is really Ramsey Theory that provides the upper bound, so in a sense, you could say, maybe if we understood Ramsey Theory better, we could improve certain bounds.

Erdős had a lot of questions regarding what we could do in Ramsey Theory. Also, Erdős had a real knack for asking questions. He would ask a series of questions that had a hidden question, which was what he was trying to get answered. Instead of asking the real question, he would put out a series of questions to be able to get the answer to the big meta-question. So perhaps the most useful thing that has happened when pursuing things like bounds are not the bounds themselves, but the proof techniques that were developed.

In a lot of math, the actual theorems aren't the important things, it's the tools that you've developed that will get the most use out of.

Within Ramsey theory, there are so many theorems in it such as Hales-Jewett. How would you describe these theorems and why do they serve as the key theories for Ramsey theory?

Dr. Axenovich:

I would say that these theorems, or class of theorems, again all point to unavoidable structures in partitions so it all comes down to partition. For example, van der Waerden looks at partitions of integers.

This is a fundamental question. We still do not understand enough about this. They are important for number theorists and we all know our understanding of numbers is very limited. There is still a lot to learn about prime numbers. So, these theories are fundamental to understanding this very simple thing of mathematics and numbers.

In our class we've discussed Ramsey Theory a lot and we started to touch on theorems such as van der Waerden's theorem and the Hales-Jewett theorem. We were looking through your papers and we noticed you have done research on anti-Ramsey numbers. What are those in a general term?

Dr. Axenovich:

In general, I like to study extensions of Ramsey results to general patterns. Ramsey Theory talks about mostly monochromatic structures, graphs, monochromatic this and that. There are extensions of that and there are some gibberish results of canonical results of Ramsey's theorem that tell you if you have a complete graph and colour all its edges, you won't know how many colours there are. There could be a few, there could be a lot.

Basically, no matter how you colour the graph you neither have a monochromatic or multi-colour pattern (rainbow) or patterns like stars in one direction. That is a classical result.

Anti-Ramsey Theory asks how do you force these multi-colored structures? Of course, you have to have enough colours so a natural condition is having a lot of colours. The question then becomes is if there are enough colours, there should be a clear-cut rainbow to see and that is captured by anti-Ramsey number so that with the fewest colours, you will definitely see multi-colored structures.

I have done research on that in different settings as well.

We have seen some proofs so far in our class where Dr. Jungic mentions that something may be a clever technique. When you are proving something that is difficult, do you start off with a very specific idea of what technique or do you just look at it and tackle it and it just comes to you?

Dr. Axenovich:

Good question.

You try to play around with the question first. What many mathematicians do and what I do is to look at the simple cases and see if I really understand what the problem is presenting. I try to understand its nature and see what I want to do. In this field, many people try to use a standard toolbox. For example, can a

When you exhaust your list and you can't find something, maybe the question is not so good because someone has probably also seen this already and the problem is just boring. You try to think and decide which way you want to go. If it doesn't bring you where you want, and you can't stop thinking about it then you go to bed thinking about it, it just pops in your head and you go “OH! Why didn't I think of this other observation” and at that moment you are super happy for about 2 seconds (laughter). I guess for me, it works. Just recently, I had a paper on Ramsey numbers. I worked for quite a bit, but I couldn't get an interesting result. There was nothing for special cases and it got pretty complicated. But then, somehow, I realized you can use this simple tool which is a very famous technique in mathematics and you just think “why didn't I think of this earlier” then everything just falls into place (laughter).

Ron Graham described Ramsey theory as a type of combinatorics. Others have described it as graph theory. How would you classify it?

Dr. Axenovich:

I think Ramsey theory goes in my view, goes a little bit between the fields.

I would not associate with graphs necessarily. Hales-Jewett for example is not graph theory.

I would say that this is a class of results in discrete mathematics. Let's say it's a class of results in discrete mathematics that claims unavoidable structures in partitions.

So, we all think in terms of colours but who cares about colours, you could be think of colouring as a partition where you split the chunks, and some chunk should have something cool happening. That's how I would describe it.

Unavoidable structures in partition.

Subsection 8.1.3 Ron Graham, math history, and more

Dr. Butler:

Ron was a unique and singular person. There are very few people like Ron, probably no one like Ron when you put it all together.

As far as what it was like working with Ron, the nice thing is that Ron was a lot like Erdős. So, what was so special about Erdős? Well, he was around before the internet. In this way, he was sort of a central point of contact for a lot of mathematicians. He would share news and problems, as he traveled. Also, he was a source for references if you were looking for a particular paper. We take these things for granted nowadays because we have Google and such.

However, it was a big deal back in the day, as it was not so easy to find. This has been a benefit to the combinatorics community because, compared to other disciplines, this community is much more collaborative. We are very much more open to sharing information and problems. So, Ron kept that going, being the central hub of combinatorics.

The nice thing about Ron was everybody talked to Ron and Ron talked to everyone. As a result, he was always on the phone, or rather in constant communication with the community.

Consequently, people would send problems to him and he would sort the question and give the appropriate questions to the appropriate mathematician.

If you hung out with Ron, you'd get to hear a question. Usually, when I heard a question, I would say that sounds interesting and I could make a good contribution. Often Ron would call up and ask me that he needed data for a certain problem. I would go and run some data, soon enough I became Ron's computer guy which is something I didn't expect to become.

In doing so, we were essentially doing experimental math and after I ran the data, I'd show Ron. We would go back and forth eventually finding a pattern. After doing so, we would go try to prove it. Ron was good at really thinking about things. He wasn't one of those mathematicians who had very exotic tools. He had basic tools, but he used them well. He would write on grid paper and would just work on the problem. Also, he worked example after example.

All the pages he left behind are now at my house. I've got folders full of Ron Graham. He made comments on the paper that were his thought process, and he would chip away. He had a philosophy, although not a surprising one, but it's nice to say out loud.

He would take the problem and start breaking it into parts, so instead of thinking about it as a big problem, he would think of them as small problems. He would do small cases and often he'd make progress and would say: “I think we can do better.”

I'd make progress as well, so it was a real back and forth. I was a lot of the computation in the writing and he was a lot of ideas. You know, we traded off.

It was amazing that Ron was so productive. You'd think he just sat around all day doing math. But it felt like whenever I was around him, we weren't doing math at all.

Yeah, we talked about math, but usually, we would go do errands. Like something needs to be fixed around the house, for example, a slackline. Then it was: “Hey that movie just came out, let's go see it.” So, I was like, when do we get the math done!

I think he told me once: “Well, last night I was lying in bed at 3 am thinking about a problem.” So I thought to myself that's when you get the math done! So, he was great at using up the whole day.

He was a great co-author and a wonderful person.

Dr. Butler tells us a humorous but cautionary tale, about checking your work and never making assumptions.

Dr. Butler:

There's a book called Ramsey Theory, written by Joel Spencer, Ron Graham and Bruce Rothschild. They had a proof of Ramsey's Theorem in the book, but the thing is when they first published it the proof was wrong! What happened was they all assumed that the other people would check, so nobody went back in and double-checked it. In the second edition, it was fixed.

Dr. Butler answered our question regarding how he got an Erdős number of one. Also, he answered our question asking on how he met Ron Graham and started to work with him.

Dr. Butler:

I worked with Ron because I was a student of his wife, Dr. Fan Chung. In the first year of graduate school, they were moving.

Grad students are free labor, so they got us to help them move. I am a large person, so they said, “we?ll definitely get Steve!” Of Course, it wasn?t much of a move. The house was in La Jolla and they were moving to the house in front of them to get a better ocean view which was about 200 meters from their old house. That was the first day I met Ron.

I really wanted to work with Ron. I wished I could say I had a master plan. Instead, I found an excuse.

I thought to myself I needed to sit in on Ron's class. Maybe something will happen, or I don't know. Then I started to notice the chalkboard at the front of the class. The previous person wouldn't erase them. I started to get in the habit of erasing the chalk board. Soon we started talking and at some point, he told me he had a paper list that several graduate students have started over the years, but never really finished it. They always sort of petered out.

I thought alright good there are projects. I was like I'm going to do Ron Graham's papers. So, I started scan and clean up the papers and put them on his website. By the time the project was done, we had become friends. Then he would start giving me problems and I was able to answer the problems.

Subsection 8.1.4 Takeaway from math for non-mathematicians

Dr. Butler:

Math is not meant to be something just mathematicians do. Math is about problem-solving and the most important thing that people need to understand is that math plays a bigger role in their life than they think. It isn't something to be afraid of, it's something to be used.

I wish the population just really had the ability to understand numbers. It feels kind of strange to be in the U.S right now I think, but most of you are probably in Canada if you're at Simon Fraser. So, Canada is a little different than the U.S right now. It feels like there's some sort of anti-science push. I don't know why, but I think the big thing that needs to happen is for people to realize math is helpful and a beneficial thing. It's something that should be studied and embraced.

Subsection 8.1.5 The Beauty of Mathematics

Dr. Axenovich:

Well, I think mathematics in general is amazing to me because it tells a story of the human brain and what it is capable of.

It is like when you listen to Bach, there is a beauty and harmony in math. There is an aesthetic to it to an extent.

For me, mathematics is nice because it is completely precise. There is no ambiguity, doubt, no statements which are free for interpretation of human opinions. There are no political opinions, anything like that so math is just the absolute truth.

Of course, most of the math produced will be somewhere wasted but important and beautiful results will stay forever. Longer than anything. For me, this was a motivation to do mathematics versus computer science because computer science is exciting to solve problems and it is very cool and creative but look at how computer science has progressed.

In 2 years, your code: nobody will look at it. Nobody publishes a code. Well, maybe someone will publish Google's code one day (laughter) but there could be something superior soon but in math, there won't be something like that.

To me, that is very motivating because when you write a paper, you know there is a chance something will read it in 300 years. That is very humbling, so you try very hard not to put something stupid in there, but I think like music, it is very special. I think math and music are very similar like that.