July 5, 2018: Creativity through Computer algebra

The Blog entry Creativity through computer algebra illustrates how computer algebra projects can be creative. In the last part, I illustrate how one can come up with new questions.
It mentions the square-graphs G(n) for which the vertices are the numbers 1 to n and where the edges are pairs (a,b) for which a+b is a square. One question which came out when experimenting with these graphs is that for n bigger or equal to 32, these graphs G(n) are Hamiltonian. The question was probed with the following code:
F[n_]:=Module[{e={}},Do[If[IntegerQ[Sqrt[x+y]], e=Append[e,x->y]],{x,n-1},{y,x+1,n}];e];
Puzzle[n_]:=FindHamiltonianCycle[UndirectedGraph[Graph[F[n]]]];
Do[If[Length[Puzzle[n]]>0,Print["G(",n,") is Hamiltonian"]],{n,1,152}]
So, far we have checked that the graphs G(32), G(33),... G(151) are Hamiltonian. Here is a picture of the square graph G(151). So, far Mathematica gets stuck when checking whether G(152) is Hamiltonian. This illustrates that checking the Hamiltonian property is a hard problem. The actual paths look pretty random so that we also don't have a way to ``guess" the Hamiltonian path for larger n:
F[n_]:=Module[{e={}},Do[If[IntegerQ[Sqrt[x+y]],e=Append[e,x->y]],{x,n-1},{y,x+1,n}];e];
G[n_]:=Map[First,Flatten[First[FindHamiltonianCycle[UndirectedGraph[Graph[F[n]]]]]]];
ListPlot[G[151],Joined->True]
I recently thought a bit about Hamiltonian graphs in in this project illustrated below. Unlike for general graphs, graphs which triangulate a manifold are Hamiltonian and the proof is constructive:
Here is the graph G(151) for which the Hamiltonian Graph property has been established.


Oliver Knill, Department of Mathematics, Harvard University, One Oxford Street, Cambridge, MA 02138, USA. SciCenter 432 Tel: (617) 495 5549, Email: knill@math.harvard.edu Quantum calculus blog, Twitter, Youtube, Vimeo, Linkedin, Scholar Harvard, Academia, Google plus, Google Scholar, ResearchGate, Slashdot, Ello, Webcam, Spring 2018 office hours: Mon-Fri 4-5 PM and by appointment.