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.