Things a Graph Theorist Should Do at Least Once

by Derrick Stolee

The theory blogs have been repeating the idea of “Things a [insert field] researcher should do at least once” including theoretical computer science, complexity theory, and algorithmic game theory. I figured I should chime in with what a graph theorist should do at least once.

  • Use the probabilistic method.
  • Use the regularity lemma, or re-prove a theorem that used it without using the regularity lemma.
  • Define a new (interesting) graph parameter or operation and show how it is similar and/or different to previous parameters and operations.
  • Prove a TONCAS theorem (The Obvious Necessary Condition is Also Sufficient).
  • Use a reduction to prove a problem is hard (NP-hard, GI-hard, NL-hard, etc.).
  • Create a new graph algorithm to show a problem is not hard.
  • Use a computer to find examples or prove small cases.
  • Use the linear algebra method.
  • Use linear programming and duality.
  • Use discharging.
  • Learn how to spell and pronounce Erdős.
  • Use a game version of a parameter.
  • Use graphons.
  • Create an algebraic construction.
  • Use the spectral method.

Feel free to suggest additional items. Also, I was trying to find appropriate links for everything and couldn’t find a good link for “graphon”. Let me know if you have a good web source for info on graphons.