Computational Combinatorics

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 »

Boron and Buckyballs

Recent news from the world of chemistry: the result is really the experimental observation of a special new molecule. People call it a “Boron Buckyball”, but this irritates me since we know that the buckyball is a specific fullerene on 60 vertices. In particular, it is the smallest fullerene that satisfies the independent pentagon rule. This new Boron molecule is called “Borospherene” and is quite interesting in its own right, as seen below:

The borospherene molecule. Credit: Zhai et al.

The borospherene molecule. Credit: Zhai et al.

The structure is very interesting when you consider it as a spherically-embedded (i.e. planar) graph: there are many triangular faces which create a cube-like structure, two of the faces of this cube are 6-faces, and the other four are 7-faces! These interesting heptagonal structures are particularly interesting. In the figure above, it appears to be a unit-distance embedding, and this creates a rotation in the opposing 6-faces.

Let’s dig more into the structure of this object, but also into the computational part of the experiment.
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 »

Rainbow Arithmetic Progressions I : Search Algorithm

At Iowa State, we tried an experiment this year to have a Discrete Mathematics Working Seminar where the group that normally meets for a research talk stays for an extra hour a week to work on a research problem. The goal was to break into smaller groups, but we ended up staying as one giant mass of mathematicians, including 5 faculty, a lecturer, and 6 graduate students. We recently posted the result to the arXiv:

S. Butler, C. Erickson, L. Hogben, K. Hogenson, L. Kramer, R. L. Kramer, J. C.-H. Lin, R. R. Martin, D. Stolee, N. Warnberg, and M. Young, Rainbow arithmetic progressions, arXiv:1404.7232 [math.CO]

Today, we will discuss the backtrack-search that was used to gather initial data on this problem. Since the paper features proofs as its main feature, not all of the algorithmic details were discussed (but enough were that anyone could figure out the rest). Here, I’ll flesh out as much detail as I can. In a later post, I will comment on the experimental collaboration.
Read the rest of this entry »

Best Practices for Backtrack Search Algorithms

Almost every algorithm I implement these days is a combinatorial search, which is a fancy way of saying a backtrack search to find combinatorial objects. A recursive algorithm determines a set of choices to make, selects one, and deepens the search. After all options are exhausted, the algorithm steps “up” a level of the search tree and makes a different choice.

Today, I want to discuss a few patterns I have developed in order to make such a backtracking search very error-proof and to make development streamlined. These concepts are particularly helpful when using TreeSearch.
Read the rest of this entry »

Best Practices for Scientific Computing

The following tweet found its way into my Twitter newsfeed.

I thought it would be appropriate to take the advice found in this article and apply them specifically to computational combinatorics. In particular, they identify and outline eight best practices, which I will discuss individually. Further, during the discussion I will include how I apply (or will apply) these concepts during my own development process. Below, I have simply copied their “Summary of Best Practices”. You can investigate each item in more detail in the original article. I’ll add my own ideas under each main topic.

Caveat: I showed this paper to a software engineer (my wife) and she thought all of these items would be obvious to anyone with even a basic understanding of software engineering. However, as the original paper is written for biologists and this blog is written for mathematicians, I find it appropriate to cover these ideas.
Read the rest of this entry »

Finding Cliques and Independent Sets in Circulant Graphs

We recently discussed cliquer, a “fast” algorithm for finding and counting maximum cliques in a graph. Today, I would like to discuss a modification of this algorithm when applied to graphs that have a very restrictive form of symmetry. Specifically, we will discuss circulant graphs and interval subgraphs of distance graphs. These graphs are particularly important for discovering the independence ratio of distance graphs, as discussed in the recently submitted paper, On the independence ratio of distance graphs with James Carraher, David Galvin, Stephen Hartke, and Jamie Radcliffe.

All code and data discussed is available at the distance graph page.
Read the rest of this entry »

Finding and Counting Cliques with cliquer

For a graph G, a clique is a set S \subseteq V(G) such that all pairs of vertices in S are adjacent in G. Determining the maximum size of a clique in a graph is a classic NP-Complete problem, but sometimes you just need to find or count cliques anyway.

Today, we discuss the cliquer algorithm, as designed by Niskanen and Östergård. Their very efficient implementation is available on their cliquer homepage. The entire implementation is very succinct and can be used as a library. In fact, Sage uses cliquer for its backend for clique algorithms. The main algorithm computes the maximum (weighted) clique and also can count maximum or maximal (weighted) cliques. We focus on the unweighted case.
Read the rest of this entry »

Updates to the Manickam-Miklós-Singhi Conjecture

It has been a busy year for the Manickam-Miklós-Singhi Conjecture. (See the earlier post on this topic for the important definitions.) Several new papers have appeared online or on the arXiv. Here is a brief discussion of these recent developments (organized by time of submission, as far as I can tell).
Read the rest of this entry »