9
$\begingroup$

I am a 10th grader and I'm very interested in mathematics. As of now, I'm into math contests and I take great pleasure in solving problems from contests such as the AIME/USAMO/IMO. These only require high school level mathematical knowledge and are based mainly on problem-solving.

However, since a few months, advanced mathematics has caught my attention and I find unsolved problems to be very interesting, such as Brocard's Problem of $n!+1$ being a perfect square and Andrica's Conjecture of prime number gaps. I can understand all such problems well, but when I try and read the existing papers on the conjecture, I barely understand anything because of my limited knowledge. Until now, I have been good at math olympiads and general problem-solving in these contests, but I understand that this is another level of mathematics and it would require a far greater background than I have right now.

My dream is to do research and make some substantial progress on such problems, and at first glance, problems in graph theory seem the most appealing to me, especially after the minimal introduction I had to it through math contest problems.

So, which textbooks should I read in order to build a solid foundation for Graph Theory?

I wish to build enough background so that I can at least understand open problems in the field and understand the existing work done on them.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ for some problems graph theory, you don't need to know much. you can start thinking about a problem right now. $\endgroup$
    – mathworker21
    Commented Jan 28 at 6:00
  • 3
    $\begingroup$ @SakshamSethi One caution: you should not assume that your work at this point will lead to a paper. You are still laying foundations for yourself; writing a paper is an excellent goal to work towards but from where you're at IMHO you should be more focused on the work towards it than the paper itself. $\endgroup$
    – Steven Stadnicki
    Commented Jan 28 at 19:01
  • 2
    $\begingroup$ In the same vein of Tian Vlasic, a nice starting point (if you are tailored at publishing) could be working out details of so-called "folklore results". That is, take a result that is almost known to experts, but nobody has ever really worked out the details. Study the involved definitions, make the needed calculations, and submit to a minor journal. While this is not satisfactory from a problem-solving point of view, it would allow you to become at ease with research topics and practices while publishing (it is also a service to the community). Knowing of such results is not easy, but [...] $\endgroup$
    – Andrea Marino
    Commented Jan 29 at 12:33
  • 2
    $\begingroup$ I suggest you get in touch with professors in graph theory from your area, go to seminars of the group (if any), and propose yourself to make some humble calculations. I think free work is always welcomed, and if you catch a Professor who encourages your ambition, it could also mentor you through your early career. $\endgroup$
    – Andrea Marino
    Commented Jan 29 at 12:36
  • 6
    $\begingroup$ @SakshamSethi See my answer to another MO question. It never hurts to know more math, but de Grey's work really required almost no textbook knowledge. My advice to you at this stage is to try to train yourself to ask and answer your own questions. Don't worry about whether your questions are new or old, easy or hard, interesting or uninteresting (as long as the questions are interesting to you). This attitude of always asking and answering your own questions is far more important to cultivate than any specific textbook knowledge. $\endgroup$
    – Timothy Chow
    Commented Jan 29 at 13:31

4 Answers 4

Reset to default
11
$\begingroup$

I feel that you are asking two questions. (A) How to get started in research? and (B) What are some good books (for a high school student) in graph theory? Question (A) is in scope for mathoverflow, while question (B) is more appropriate for mathstackexchange. So you should go ask question (B) there.

As for question (A), I think that there are two approaches (and of course you can/should take some combination of both):

  1. "Go to school." That is, go to your mathematics classes, ask questions, learn the material, get a degree, then get another degree, and so on. Talk to the teacher (and eventually the professor), and the other students, to understand what they know, and what they find interesting. Oh, and "school" includes mathstackexchange and mathoverflow and the internet more generally.

  2. "Figure it out yourself." That is, buy a notebook and make a list of questions you find interesting. Write down your own questions. Try to solve the questions of others and yourself. Buy/download a few books that look interesting and spend a year trying to read a few of them (or a few chapters of one book, or a few pages of one book...).

You may find the following questions and their answers useful:

Undergraduate research in Topological Quantum Field Theory

A Learning Roadmap request: From high-school to mid-undergraduate studies

Learning through guided discovery

How to escape the inclination to be a universalist or: How to learn to stop worrying and do some research.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you so much for the response. I believe that I would need to read introductory textbooks in Graph Theory to get a solid foundation. However, after this, how do I know which open problems in this field are accessible for me? I am willing to spend one or two years working on a problem, but I don't wish to spend an enormous amount of time for my first paper. $\endgroup$
    – Saksham Sethi
    Commented Jan 28 at 17:38
  • $\begingroup$ Yes, reading a few books is a nice way to learn. After that, the only way to "know which open problems in this field are accessible", is to try thinking about a few of them. If you are interested in writing papers quickly, you might start with a few which are less research focused. Finally, some people work better alone, some work better with a friend or two, and some work better in a large group. So you could try the various ways and see what works for you. Of course, there is the issue of finding other people to talk maths with. Try college... or the internet! $\endgroup$
    – Sam Nead
    Commented Jan 28 at 19:29
  • 1
    $\begingroup$ Regarding "go to school": some universities even allow bright and under-challenged high school (or equivalent) students to attend introductory lectures. An acquaintance of mine attended Analysis I & II at the local university while in 10th grade. If this is at all possible, this would enormously benefit your skills in mathematical exposition and in how to write a proof. (There may even be graph theory lectures you might be able to enroll in.) $\endgroup$
    – Stephan Kolassa
    Commented Jan 29 at 13:04
8
$\begingroup$

In addition to Sam Nead's answer, which is about how to get started in math research, I want to direct the OP's attention to many lists of open problems in graph theory. For someone with a background in the IMO, who likes problem solving, this is a concrete way to get into research. If you manage to solve one of these open problems, you can publish the solution (there are several MO threads about undergrad math journals that you might find useful, e.g., this one).

Ok, lists of open problems in graph theory:

http://dimacs.rutgers.edu/~hochberg/undopen/graphtheory/graphtheory.html

http://www.openproblemgarden.org/category/graph_theory

Collection of conjectures and open problems in graph theory

Open Problems for Undergraduates

Does there exist a comprehensive compilation of Erdos's open problems?

https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics#Graph_theory

https://mathweb.ucsd.edu/~erdosproblems/

https://dwest.web.illinois.edu/ (two links to lists of open problems)

Spirkl - Open problems for the 2020 Barbados graph theory workshop

Open problems for the Barbados graph theory workshop 2017

Open problems in spectral graph theory: https://arxiv.org/abs/2305.10290 and https://arxiv.org/abs/1907.04349

https://www.cs.upc.edu/~sedthilk/grow/Open_Problems_GROW_2013.pdf

Nguyen - Open problems for the second 2022 Barbados workshop

https://www.quora.com/What-are-some-interesting-unsolved-problems-in-graph-theory-or-topology

Stout - Some open problems and conjectures

Aldous - Some of my favorite open problems

Steinerberger - Some open problems

Kaul - Some open problems

Gera - Graph theory - Favorite conjectures and open problems - 1

Gera - Graph theory - Favorite conjectures and open problems - 2

Simonovits - Important open problems in extremal graph theory

Improve this answer
$\endgroup$
4
$\begingroup$

Sam Nead and David White have given very good answers so far. I want to expand on some related aspects. I've done a research in graph theory with high school students before which led to a just published paper so I have some experience here. (I've done more work of a similar sort with number theory and high school students.)

One thing one needs to be careful about, is that almost any problem that is listed in an open problems collection has had a fair number of people look at it before. So one thing that is important to do is to not try to answer the whole question, but look at some manageable part.

A related issue is that to be blunt, some people who do research mentorship with high school and undergraduate students hoard problems since finding really good problems for this can be tough. I've shared things with students who aren't mine before, but that's generally been when I've had a glut of problems, which is rare. That said, I do have a specific research problem which I'm going to just throw out here because it is both somewhat on the topic, and because I have a bunch of others currently in my stash, and I'm not going to have another graph theory student group for a while. This assumes some small familiarity with the Hadwiger–Nelson problem.

I call this project "How not to solve the Hadwiger–Nelson problem."

Coloring a hex grid carefully gives $\operatorname{HN}(2) \leq 7$, that is the chromatic number of the unit graph on the plane is at most 7. One can try the same thing with other grids, but for the other two obvious ones, triangle and square grids one gets a worse result. To some extent this seems to be due to the hex grid being the most well behaved grid in many respects.

What happens if we insist on coloring tilings of the plane and use even more irregular shapes? Regular pentagons cannot tile the plane, but there are 15 families of irregular pentagons which do tile the plane. One project direction is to see what numbers they give (almost certainly pretty bad) for the Hadwiger–Nelson bound.

There are other tiles which may be of interest here, such as the standard octagon with square grid pattern.

Recently, David Smith discovered a set of so-called Einstein tiles. An Einstein (German for one-stone) was a long sought for single tile that could completely tile the plane and do so aperiodically. These tiles are very irregular and so one would expect that they give even worse bounds. How much worse are they?

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thanks a lot for the comprehensive answer. Since you are experienced with Graph Theory research, I hope you can answer the following question for me: In order to make progress on some unsolved problem about graph coloring, do I need to be familiar with all of the content from an introductory graph theory textbook, or would the knowledge from the "Coloring" chapter of that book suffice? $\endgroup$
    – Saksham Sethi
    Commented Jan 28 at 22:55
  • $\begingroup$ @SakshamSethi For this particular problem, my guess is knowledge of coloring would be straightforward. I suspect that this problem can be handled with a fair bit of geometric reasoning without too much graph theory. $\endgroup$
    – JoshuaZ
    Commented Jan 29 at 0:26
  • 1
    $\begingroup$ @SakshamSethi You might want to look at Alexander Soifer's Mathematical Coloring Book, which de Grey cited as a source of inspiration. It is important, when learning to develop a research mindset, to avoid thinking of textbooks as mountains of material that you must climb. Soifer's book is an inspirational book more than an instructional book. Approach it as such and you will find that there is a lot you can do with very little knowledge. $\endgroup$
    – Timothy Chow
    Commented Jan 29 at 13:50
  • $\begingroup$ Got it. Thanks! $\endgroup$
    – Saksham Sethi
    Commented Jan 29 at 22:30
4
$\begingroup$

Stay away from prime numbers and number theory!

You won't make progress there. Too many smart people have been there already. You should start with easier (less known) problems. Also, learn programming.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Right! This is what I realized a few days ago. I decided to switch to much less-known problems in Graph Theory which is still a relatively new subject. BTW, yes, I am very comfortable with Python :) $\endgroup$
    – Saksham Sethi
    Commented Jan 28 at 21:43

Not the answer you're looking for? Browse other questions tagged .