Posted: July 19th, 2015
No Comments »
As many of you know, I spent most of my last two years working on Ramsey theory for my master's thesis. I took on several subprojects around graph theory and mathematical programming so now that it is done, I thought I would share some of the things I learned in the process.
In this post, I will write about a family of graphs that are important for extremal graph theory. These graphs represent the relationship between points in the projective geometry defined by 3-dimensional vectors of elements in a Galois field, where two vertices representing two points and are joined by an edge if is in the pole of . The graph is undirected because, by definition, if is in the pole of , then is in the pole of . The interesting feature of these graphs (as explained in this seminal paper) is that, if is joined to points and by edges, and these are in turn joined by edges to a point , then , because the line passing through points and is unique so the pole of is the pole of . In plain English, this means there are no simple cycles of length 4 in these graphs. That turned out to be important for my thesis, so I wanted to illustrate one of these graphs in my write-up.
My weapon of choice was Maxima. I just realized I have not posted about Maxima before, but that is actually my go-to software whenever I have to deal with mathematical programming. It is a great tool for prototyping things that require non-trivial concepts of math. In the particular case of these graphs I was trying to draw, Maxima provides a package to deal with Galois fields and a package to make (and even draw) graphs, so I had everything I needed... except experience with Maxima. Despite being an occasional Maxima user for several years, I am not an expert in the commands and expressions, so my first version of the code was pretty clunky and did not feel like Maxima. I turned to the expertise of the Maxima community in their mailing list, and they were exteremely helpful. The version of the code that I like the most is as follows:
nelements: ef_order() / gf_order()$
extelements: makelist(ef_exp(gen, i), i, 0, nelements - 1)$
vertexset: map(lambda([p], map(gf_n2p, ef_p2l(p, 3))), extelements)$
block([matrix_element_mult: gf_mult, matrix_element_add: gf_add],
pg: make_graph(vertexset, lambda([p, q], is(p . q = 0))))$
Some comments about the code: In the original version, you will see I built a set of all 3-D vectors of elements in the Galois field in question, and then built equivalence classes out of them based on a finding a scalar that would make one vector a scalar multiple of the other. This was very slow, and the code looked very contrived. The idea behind this version of the code came from Volker van Nek, who pointed me to the ef_ calls that deal with extension fields over the original Galois field. In this case, I want to extend my original Galois field to 3 dimensions , so I call ef_primitive_poly(3). This sole idea makes generating the points straightforward, as you can see in the code above. Another important improvement over the original code was the call to make_graph instead of create_graph. This idea was suggested by Andrej Vodopivec. While it seems those two functions should do the same thing, the main difference in their behavior is that... make_graph is cool an create_graph is not. make_graph works great when you know the rule that defines whether there is an edge between the objects you are calling vertices or not, which is the case in this example. One last thing I leared from Robert Dodier was the block function, which lets me scope variable assignments to a defined sequence of commands. In my case, I wanted to override the way dot products are calculated, but I didn't want this setting to affect subsequent commands.
In addition to the technical considerations mentioned above, I have to say I am very impressed by the Maxima community participating in their Maxima-discuss list. These are extremely well-versed members helping newcomers like me build interesting, slick solutions to computer algebra problems. I think this is a great asset in the Maxima community and I expect to get more involved with it in the future.