The best-known symbol of the Olympic movement is the set of five interlocking rings — blue, yellow, black, green, and red — on a white field. These six colors have the property that at least one of them is present on the flag of each nation. But is there a smaller set of colors that has the same property? It turns out that this question is a direct application of the “hitting set problem” in graph theory. I’ll explain what that problem is and then show how we can use some math and some Clojure to answer our question.
- But first, a clarification
- A brief primer on hypergraphs
- The hitting set problem
- The hitting set solution
But first, a clarification
According to the Wikipedia article on the Olympic symbol, Pierre de Coubertin is quoted as saying
…the six colours [including the flag’s white background] thus combined reproduce the colours of all the nations, with no exception. The blue and yellow of Sweden, the blue and white of Greece, the tricolours of France, England and America, Germany, Belgium, Italy, Hungary, the yellow and red of Spain next to the novelties of Brazil or Australia, with old Japan and new China. Here is truly an international symbol.
Here de Coubertin seems to be making a much stronger statement than the one I’ve made: He says that every color that appears on any national flag is one of the six Olympic colors. A bit of research makes this claim plausible. If you look at Wikipedia’s list of countries’ flags by color, it is indeed true that most of the flags use only the six Olympic colors, and of the exceptions, none had been adopted when de Coubertin introduced his design in 1912 (although the flag of Ireland, a third of which is orange, had come to be regarded as the national flag1 by the time the Olympic rings were first actually used, at the Antwerp games in 1920). For this article I’ll stick to my original claim about the colors — de Coubertin’s claim is definitely less mathematically interesting!
A brief primer on hypergraphs
In order to understand the hitting set problem we’ll need to introduce some graph theory terminology. A graph consists of a bunch of dots (called vertices) that are connected by lines (called edges):
In this common version of a graph (formally called a “simple graph”), each edge connects exactly two vertices together, and it’s not possible to have more than one edge connecting the same pair of vertices. (In other words, the edges must be unique.)
To look at the hitting set problem we’ll actually need to use hypergraphs. A hypergraph also consists of a bunch of vertices and a bunch of edges, but now each edge can connect any number of vertices. (Edges may be called hyperedges in this context.) In this case it doesn’t make sense to think of edges as lines connecting the vertices, so we’ll represent them as areas:
In our formulation, each edge may contain any nonzero number of vertices, and edges need not be unique.
How does this relate to our flags’ colors? If we think of each flag color as being a vertex then each flag is an edge: The vertices the edge contains are the colors used by the flag. To pick just a couple of flags to demonstrate,
(To simplify things we’re going to ignore shades of colors; the Swedish flag uses a lighter shade of blue than the U.S. flag, for example, but for our purposes they’re both just blue.)
The hitting set problem
Given a hypergraph H, a hitting set of H is a set T of vertices such that every hyperedge of H contains at least one of the vertices of T. In other words, T has a nonempty intersection with each hyperedge. The most obvious hitting set is the set of all of the vertices: Since all of the vertices are in this set, of course each hyperedge will contain one of those vertices! Usually when people talk about the hitting set, however, what they’re looking for is the minimal hitting set — the hitting set of the smallest possible size.
In terms of flags and colors, the minimal hitting set is the smallest possible set of colors such that at least one of the colors appears on each flag. Take a look at our three-flag example above. In general, the smallest possible size for the minimal hitting set is one, which happens when one (or more) of the vertices is a member of every hyperedge. That’s not the case here — there’s no single color that all three flags have in common — so let’s look for hitting sets with two elements. It turns out that there are five: white and yellow; red and yellow; red and blue; black and blue; and yellow and blue. If you’re bored you can verify for yourself that for each of these pairs, all three flags use at least one color in the pair. (It’s worth pointing out that, as in this example, there can be more than one minimal hitting set.)
The hitting set solution
I asked for help with this problem on the Computer Science Stack Exchange, and user A.Schulz pointed me to the first chapter of Parameterized Complexity Theory by Jörg Flum and Martin Grohe, which contains an algorithm for finding minimal hitting sets. (The algorithm gives exact results, which — given that the problem is NP-complete2 — makes it inappropriate for use with large hypergraphs.) I’ve written a small Clojure library called hitting-set to implement the algorithm. The main function,
minimal-hitting-sets, takes a “hypergraph” of the form
and issues a set of minimal hitting sets that looks like
Looks good! How are we going to get a hypergraph containing the colors of all the nations’ flags? More Clojure. Wikipedia has a nice “list of countries by colors of national flags”, and using the Enlive framework we can scrape this page to extract a list of countries and the corresponding lists of colors in their flags. I’ve done this in the olympic-colors project, which is available from GitHub. Its one and only public function is called
flags, and it returns a hypergraph in just the format we need. If we combine these two libraries, the answer to our question — how many colors do we really need on the Olympic flag? — is short and quick in coming:
So if we can trust Wikipedia (and my programming ability) then this would do just as well to represent every nation:
I haven’t gone into any detail about the implementation of the hitting set algorithm in Clojure, or about the use of Enlive to scrape a Wikipedia article, but the details can be found in the README files, in the code documentation, and in the code itself.
There are many other applications of the hitting set problem. In the future I’ll look at the hitting set of a city bus system, the large hypergraph of which will require us to abandon our exact algorithm in favor of an approximate one.
The office of the Taioseach says about the Irish flag, “Associated with separatism in the past, flown during the Rising of 1916 and capturing the national imagination as the banner of the new revolutionary Ireland, the tricolour came to be acclaimed throughout the country as the National Flag. It continued to be used officially during the period 1922–1937, and in the latter year its position as the National Flag was formally confirmed by the new Constitution…” ↩︎