Problems to think about and further reading.
More exclamation points means more likely to be readable/solvable before taking college level math courses. (No marking means "something that would be typical in a Sophomore or Junior level college course". Something with a ¡ would be
- (!!) Find a solution to this version of instant insanity:
- (!) Find a solution to this version with five cubes and five colors:
- (!) Design your own version of instant insanity with a unique solution. (Making sure there's definitely no other solution can be tricky.)
- (!) Find all 14 (!) different graphs with degree sequence 4,3,3,2,2,1.
- The Erdős-Gallai Theorem gives an exact formula for identifying when a sequence of numbers is graphic.
- (¡) Brooks' Theorem says that if every vertex in a complete graph has degree at most d then the graph can be colored using d colors unless the graph is complete, or d=2 and the graph is a cycle of odd length.
- Can you come up with an infinite connected graph where all the vertices have even (finite) degree, but the graph does not have an Eulerian cycle? Can you come up with one where it doesn't have an Eulerian path?
- (!!!) Planarity.net actually has a game where you can take planar graphs and rearrange them to be planar.
- (!) Proofs and Refutations: The Logic of Mathematical Discovery by Imre Lakatos is a thorough (fictional) account of a back and forth over figuring out how to apply Euler's formula to three dimensional shapes as a meditation on the philosophy of mathematics.
- (¡) A counterexample to Hedetniemi's Conjecture was found earlier this year after more than 50 years of people looking for one!
- (¡) Wagner's Theorem and Kuratowski's Theorem show that, in two different ways, every non-planar graph contains either K5 or K3,3. While the proofs are intricate, that's mostly because they involve a long chain of ideas, very carefully pinning down the structure of the "simplest possible" non-planar graphs.
- There are infinitely many convex regular polygons (for any integer at least 3, we can have a convex polygon with exactly n sides), and we have seen that there are exactly five regular polyhedra. We can continue investigating what happens in higher dimensions. The same ideas involving Euler's Formula get used (though Euler's formula has to be adapted to higher dimensions): there are 6 convex regular polyhedra in 4 dimensions, but after that, things simplify: in any number of dimensions greater than 4, there are exactly 3.
- We can think abut drawing graphs on any surface, like a donut, a Klein bottle, or anything else. These are closely related to the Euler Characteristic" of the surface.
- (!) For instance: identify some graphs which aren't planar but can be drawn on the surface of a donut, find the Euler characteristic of a donut, and identify some graphs which can't be drawn on a donut.
- If we allow edges to go through 3D space, we can always have edges avoid crossing. But we can ask analogous questions: which graphs can be position in 3D space so that there are not a pair of cycles which pass through each other (a "link")? Which can be positioned so that there are no knots?
- (¡) The Fortress Problem asks how many guards need to be placed at the corners of a polygon to monitor the entire outside of polygon.
- (!!) The slides about the 6 and 5 coloring theorems
- There's a lot of information about graph coloring and its variants, including Hadwiger-Nelson and Ramsey's Theorem (the topic of the cliques project) in The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators by Alexander Soifer
- (!) I learned about the art gallery problem from How to Guard an Art Gallery and Other Discrete Mathematical Adventures by T. S. Michael
- (!!!) Combinatorial games, like Sprouts, the Vertex Coloring Game, and the Shannon Switching Game, are discussed in the spectacular Winning Ways for your Mathematical Plays by Elwyn Berlekamp, John Conway, and Richard Guy. The vertex coloring game (with two colors, for planar graphs) is called Col there, and shows up early. Sprouts and the Switching Game (which they call Bridgit) appear in Volume 3.
- (¡) Fractional colorings and similar ideas are discussed in Fractional Graph Theory: A Rational Approach to the Theory of Graphs by Edward Scheinerman and Daniel Ullman
- (¡¡¡) There's a bibliography which, as far as I know, lists all papers about harmonious colorings (and some related variations). Not much is known, and the papers are hard to read!
- (¡¡¡) I'm writing a book about using techniques from my field (logic) to explain how we can use infinite graphs to simplify arguments about large random graphs.
