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.