Computational Combinatorics

Category: Paper Reviews

The Erdős Discrepancy Problem

Computational combinatorics made a big splash last spring when Konev and Lisista announced their SAT-solver-based proof of the Erdős Discrepancy Problem for constant C=2. Recently, Le Bras, Gomes, and Selman announced another SAT-based solution for C=3, but when restricting the sequences to have a special property.

I was working on a draft blog post to talk about these results, but then Terry Tao went and solved the full conjecture. I tweeted about it and got many responses, my favorite being simply the following image:


To help those who have difficulty with Tao’s paper (and I am not qualified to read any part of his solution), I made a short video describing the problem, or read below.

Read the rest of this entry »

Hypohamiltonian Planar Graphs

Brendan McKay uploaded a short-but-sweet article to the arXiv titled Hypohamiltonian planar cubic graphs with girth five. Let’s quickly break down all of the words of this title:

  1. A graph is hypohamiltonian if it does not contain a hamilton cycle, but the deletion of any vertex does create a hamilton cycle.
  2. A planar graph is a graph that can be embedded in the plane with no edge crossings.
  3. A cubic graph is a 3-regular graph.
  4. The girth of a graph is the length of the shortest cycle.

McKay details the search for the smallest (and first known) graphs of this type, which have order 76. There are three non-isomorphic examples. The data for these graphs (and more) is available online [Note: at this time, it appears the data is not yet online].

The three smallest examples of hypohamiltonian planar cubic graphs of girth 5. The numbers give the face lengths for faces other than 5-faces. Figures by B.D. McKay.

The three smallest examples of hypohamiltonian planar cubic graphs of girth 5. The numbers give the face lengths for faces other than 5-faces. Figures by B.D. McKay.

Read the rest of this entry »

Shannon Capacity of Odd Cycles

Breaking news: Mathew and Östergård have improved lower bounds on the Shannon capacity of some odd cycles. These improvements over a very old and difficult problem come via some sophisticated algorithms.
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 »

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 »

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 »

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 »

3-Uniform Friendship Hypergraphs

A very brief welcome to EXCILL2 participants. Thanks for visiting!

Today we discuss On a question of Sós about 3-uniform friendship hypergraphs by Hartke and Vandenbussche. These authors presented several new examples of friendship hypergraphs exhibiting a property that was not known to be possible. Their method applies careful use of integer programming as a black box. First, a careful construction of an integer linear program discovered some examples (and non-existence of examples) for small orders. Then, by making some symmetry assumptions, they constructed some larger integer programs that found larger examples, hinting towards an infinite family. The existence of larger examples remains open, although Lia, van Reesa, Seoa, and Singhi recently proved some structure theorems that apply to the examples found by Hartke and Vandenbussche.
Read the rest of this entry »

A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture

Stephen Hartke and I recently uploaded our paper, A Branch-and-Cut Strategy for the Manickam-Miklós-Singhi Conjecture to the arXiv. We build a computational method to verify a conjecture involving the number of nonnegative k-sums in a nonnegative sum of n real numbers. With this method, we proved a stronger statement than the conjecture for all k\leq 7 and formed a stronger conjecture.

The method makes use of linear programming techniques and software, so begins our discussion of linear and integer programming methods. Read on to discover the method and also to figure out what is going on with the picture below.
Read the rest of this entry »

Generating Fullerenes

Today, we discuss “Generation of Fullerenes” by Brinkmann, Goedgebuer, and McKay, recently published in the Journal of Chemical Information and Modeling. A fullerene for our purposes is a cubic planar graph where every face has length 5 or 6. However, the definition of fullerene as a molecule is valuable as well (and why this paper was published in a chemistry journal). Since we previously discussed generating cubic graphs, we could use that algorithm and restrict our output to graphs that satisfy our requirements, but this method is wasteful as there are many more cubic graphs of order n than fullerenes of order n. Since their method uses canonical deletion, we only need to describe our base objects and our augmentation step.
Read the rest of this entry »