A cliff

The “combinatorial explosion” is a well-known phenomenon. I recently came across a very dramatic example of it.

I was trying to compute the function F(n,k), defined to be the maximum of |S|×|P|, over all sets S of k-subsets and all sets P of k-partitions (partitions with k parts) of {1,…n} with the property that no set in S is a transversal for any partition in P.

I wrote a GAP program, formulating the question as a problem about cliques in a certain graph, and using Leonard Soicher’s very nice GAP package GRAPE. The program finds all “maximal” pairs (S,P), computes the product of their sizes, and returns the largest value.

For n = 6, the program finds the values for all k in less than three-quarters of a second on my laptop. They are 0, 21, 150, 125, 12, 0.

On the other hand, the program has been running on my (more powerful) desktop machine in St Andrews for more than two days now on the case n = 7, k = 3, and has not yet reached a conclusion.

When Europeans settled in Sydney in 1788, several expeditions tried to find a route across the Blue Mountains. They followed valleys which terminated in unscaleable cliffs. 25 years on, Blaxland, Wentworth and Lawson re-thought the strategy, followed the top of a ridge, and succeeded. I think I am going to have to do a bit of re-thinking in this case!

Incidentally, this question is not unrelated to the topic of the preceding post on the lattice of subgroups of a group. Sometime soon I will discuss the connection …

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , , , , . Bookmark the permalink.

4 Responses to A cliff

  1. Dima says:

    That’s an instance of edge-maximal biclique problem you get, I gather… Indeed, it’s not hard to convert it into a max-clique problem for the suitably modified edge graph, but I’m not 100% sure if the general GAP code will do the best thing here.

    • It’s actually vertex-maximal, in the bipartite graph of k-sets and. k-partitions. Part of the difficulty is that we are maximizing a nonlinear function. (It would be linear in the edge geaph, but that’s a much larger graph.)

      • Dima says:

        Vertex-maximal biclique problem (finding a biclique with maximum number of vertices) in bipartite graphs is solvable in polynomial time! This is already mentioned in Garey-Johnson classical book on NP-complete problems. But you’re looking to maximise |S|x|P|, i.e. the number of edges in the corresponding biclique; this is called edge-maximal biclique problem (known to be NP-hard).

  2. Travelling salesman is NP-hard but instances with thousands of vertices can be solved in practice. My point is that this somewhat innocent-sounding problem takes a million times as long for n=7 as for n=6. I don’t think I ever looked at a question where the complexity ramped up quite so steeply.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.