Apologies if the content of this post is not mathematical enough and is consequently in the wrong place. For context, I graduated with my masters in mathematics about 8/9 years ago and then went on to do other things, leaving maths behind. Recently I've got into learning Graph Theory (initially to help someone who was writing a module) and am having thoughts about taking up the torch again and doing a phd.

Now, I am able to learn the material (a 4th year graph theory module) and solve the exercises without too much difficulty and believe that Graph Theory is something I could be good at. When I have finished, I have a Springer book lined up - Graduate texts in Mathematics. However I remember next to nothing about Number Theory, Group Theory, Rings, Fields, Analysis, Topology, Probability, Set Theory, Logic etc... (basically the whole of the rest of maths). Now at the moment it seems that if one has solid foundation in mathematics, a feel for combinatorics, and the ability to abstract/visualise, this is all you need to do Graph Theory, and that all these other areas are almost entirely separate.

My question is, how long will this go on for? Could I, in theory, get to the frontiers of understanding in Graph Theory and come up with new ideas, with my current level of knowledge about the rest of maths? Can anyone, who is experienced in Graph Theory, provide any insight on this?

Many Thanks

  • 1
    $\begingroup$ One thing to keep in mind is that if you do a PhD (at least in the US) you'll have to pass qualifying exams in subjects like abstract algebra, real analysis, or topology. $\endgroup$ – littleO Jan 10 at 10:34
  • $\begingroup$ thanks littleO, noted. $\endgroup$ – t-tough Jan 10 at 10:42

It really depends. Graph Theory is a vast field. You can specialize in areas of graph theory where you don't need much of the other mathematical areas, except for standard logic and very basic set theory. If graph theory excites you I would definitely do it. Once you have found the right topic and you feel like you need more knowledge from other areas, it should be no problem to learn the things you need, especially if you already have a background in mathematics (even if you feel like that you do not remember anything which is quite normal actually). Of course, this does not cover the formalities mentioned in the comments by littleO (starting an actual PhD etc.).

However, I feel like that this alone is not a satisfying answer, so let me elaborate a little bit more information which might help you.

I'm going to list some of the topics I feel like you will need to start.

  • Basic mathematical logic, proof techniques (induction, proof by contradiction, ...),
  • Very basic set theory,
  • Algorithms and complexity analysis,
  • If you want to dive into algebraic graph theory, then of course you will need linear algebra to some extend,
  • If you want to dive into extremal graph theory, then you will also need probability theory,
  • Basic topology, this is in fact really useful if talking about planar graphs or $k$-planar graphs,
  • (Ramsey theory; it is actually quite useful in many situations but I wouldn't focus too much on it for now)

However, everything mentioned can become very complex very quickly. I would like to name a few examples. There is a nice concept called "Flag Algebras" by Razborov for solving problems in extremal graph theory. It is extremly useful and used quite often in research for this area. However, if you read his paper, you will quickly realize that simple mathematics is not necessarily enough. You can check it out here. Also, you can search for papers which used his method. Most of them are not necessarily using easy mathematics as well.

Proofs in structural graph theory are usually quite hefty too. Check out the famous strong perfect graph theorem and its "recent" proof by Chudnovsky et. al. You can check the paper out here. Even if it is not easy, this is actually a good example for a result which doesn't use any other mathematics than graph theory itself (of course logic and set theory...).

You can of course specialize on algorithmic aspects of graph theory as well for which you will need knowledge of computer science. A famous example is the graph colouring problem. Research for determining upper bounds for the chromatic number of certain graph families is mostly done without keeping in mind that we still need to find an efficient algorithm which does perform the actual colouring. You quickly come to the point where you want to dive into complexity theory because it is quite fascinating (polynomial reductions etc.) and you quickly realize that the problems which are researched the most in graph theory are the $\mathcal{NP}$-complete problems.

There are many more examples, I have just named very few. In summary, however, there is nothing in my eyes that stops you from dealing with graph theory. Studying a research area is a process and during this process you will notice where your knowledge gaps are and these gaps are always closable.

  • 2
    $\begingroup$ Thanks so much David, for the detailed and thoughtful answer. $\endgroup$ – t-tough Jan 11 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.