Computational Combinatorics

Category: On Being a Mathematician

So Long, and Thanks for All the Theorems

Since I first learned about graph theory in my intro algorithms class, I have been intensely focused towards learning more about graphs and doing mathematics as a passion and a profession. At the end of this semester, I close the book on that part of my career, leave my academic position, and return to my original plan: developing software.
Read the rest of this entry »

On the arXiv

Whenever I write a paper, I put it on the arXiv. The arXiv is an open-access paper repository run by Cornell University. It’s pretty fantastic to know that almost anyone can have an immediate international audience by posting a paper to the arXiv. My use is two-fold: I upload papers and I look forward to the evening paper dump in my RSS feed five times a week. It is a great way to be actively connected to the research world. As such, I try to convince my coauthors to upload papers to the arXiv and have never had one complaint.

That is, until something interesting happened. I’ll tell the story very quickly, then talk about pros and cons for using the arXiv. This will entirely skip any copyright issues with journals, and focus on the benefits of public/private preprints. Please add your comments!
Read the rest of this entry »

On Reproducibility

Recently, Stephen Hartke spoke about our work on uniquely K_r-saturated graphs, and afterwards he spoke to a very famous mathematician, who said, roughly:

“Why did you talk about the computation? You should just talk about the results and the proofs and hide the fact that you used computation.”

While this cannot be an exact quote, I believe it is a common attitude among mathematicians. While the focus is on solving problems, the use of computation is seen as a negative, so the final research papers make little mention of their computational methods. This is a huge problem in my opinion. While computations can report exact results, and sometimes even prove results, every execution is an experiment. It is unknown before the execution what the results will be, or how long it will take.

Computational combinatorics is a combination of mathematics, engineering, and science: We prove things, we build things, and we experiment. Since computer proofs are experiments, it is important that they be reproducible. Today, I want to discuss a bit about how we can improve our presentation of algorithms and computation in order to make results more reproducible.
Read the rest of this entry »

Rainbow Arithmetic Progressions II: The Collaboration

In the previous post I briefly discussed the algorithms that played a role in the recent paper Rainbow arithmetic progressions. Today, I want to take a detour from our typical discussion of computational methods and instead discuss the collaboration that led to this paper.

It is important to explicitly say that while this paper was very collaborative, and used the expertise and hard work of many individuals, this blog post was written entirely by me during office hours and in a hurry. Any opinions, errors, or other reason to be angry with the content here is entirely my fault and not the fault of my fantastic coauthors. While I’m at it, let me actually list my coauthors by name:

Steve Butler, Craig Erickson, Leslie Hogben, Kirsten Hogenson, Lucas Kramer, Richard L. Kramer, Jephian C.-H. Lin, Ryan R. Martin, Nathan Warnberg, and Michael Young.
Read the rest of this entry »