COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2002

In 1995 the Institute of Electrical and Electronic Engineers (IEEE) approved the 802.12 international standard for transmitting information at 100Mbit/s over copper telephone cabling. Under this standard, messages are encoded from 5-bit data groups into 6-bit code groups prior to transmission. The code mapping was chosen to satisfy physical, economic and social constraints simultaneously.

Nine years after designing this code as a Hewlett-Packard employee and presenting its properties to the IEEE I have permission to explain its underlying structure. I shall show how the code was found using a combination of geometrical insight, combinatorial reasoning and computer search.

Let D be a digraph with real-valued costs on the vertices and let the cost of a cycle be the sum of the costs of its vertices. Clearly, if we allow negative costs then it is NP-hard to find a minimum cost cycle since the hamiltonian cycle problem can be posed in this way.

In this talk we show how to solve the problem of finding a minimum cost cycle in polynomial time for some classes of digraphs that are structurally related to tournaments. This includes well studied classes of digraphs such as extended semicomplete digraphs and quasi-transitive digraphs. As it will be clear from the talk the solution for quasi-transitive digraphs builds heavily on their nice decomposition properties and strong relation to extended semicomplete digraphs.

This is joint work with Gregory Gutin and Anders Yeo of Royal Holloway, University of London.

Previous Talks:

VERTEX SEPARATION is an important, NP-complete graph problem. It is eqivalent to several other problems, the most well-known among which is PATHWIDTH. It is known that vertex separation is solvable in polynomial time on graphs of bounded treewidth. However, even the best known algorithm on bounded-treewidth graphs can hardly be called practical. Therefore, there are efforts to design practical algorithms for that graph parameter on even more restricted graph classes.

We present an outline of an exact vertex separation algorithm on maximal outerplanar graphs, which are a subset of graphs of treewidth two. The work is still in progress, right at this moment. The presentation will introduce the results achieved so far, and will make a comparison with the algorithms for the vertex separation of ordinary trees.

A graph is planar if it can be drawn on the plane with vertices at unique locations and no edge intersections except at the vertex endpoints. Due to the wealth of interest from the computer science community, there are a number of remarkable but complex O(n) planarity algorithms. The presentation will discuss a new simplified O(n) planarity testing algorithm that is based on embedding one edge of an input graph at a time while maintaining planarity of the embedded portion of the graph.

This new algorithm is interesting not only for the ease with which it can be implemented and proven both correct and O(n) but also because it forms the foundation for simplified solutions to numerous related problems, including planar embedding, the identification of a Kuratowski subgraph (a portion of a non-planar input graph which obstructs planarity), outerplanar graph embedding and obstruction identification, and the search for subgraphs homeomorphic to K_2,3 and K_3,3.

Paul Erdos talked about "The Book", kept by God, in which the perfect proofs of mathematical theorems are recorded. He also said that you need not believe in God but, as a mathematician, you should believe in The Book.

The volume "Proofs from THE BOOK", by Martin Aigner and Gunter Zeigler is dedicated to Erdos' memory. The first section of *this* book is entitled "Six proofs of the infinity of primes". I don't have the courage to assert that I can do all six proofs in 50 minutes (we shall see), hence the title.

A Venn diagram is a collection of simple closed curves in the plane with the property that all possible intersections of the interiors and exteriors of these curves are nonempty and connected. A Venn diagram with n curves is referred to as a an n-Venn diagram. We consider n-Venn diagrams with n-fold rotational symmetry and examine the dual graph of these diagrams. A number of interesting combinatorial properties leads to a simple generation scheme and we survey and expand on some work on generating symmetric 7- and 11-Venn diagrams.

A torus is a surface shaped like a doughnut. A graph is toroidal if it embeds on the torus with no crossing edges. A topological obstruction for the torus is a graph G with minimum degree three that is not embeddable on the torus but for all edges e, G-e embeds on the torus. A minor order obstruction has the additional property that for all edges e, G contract e embeds on the torus.

The aim of our research is to find all the obstructions to the torus (both minor order and topological). To date, we have found 239,322 topological obstructions and 16,629 minor order obstructions. Previously, only a few thousand had been determined. This talk discusses the techniques used to find these obstructions.

In this talk we will look at Fermat's two squares theorem which states the condition under which an integer may be written as the sum of two squares. This was judged by Hardy as one of the most beautiful results in number theory. Although this theorem is old, we present a fairly recent proof of one of the key lemmas. If time permits we will briefly mention some other results in this direction.

Let the generating set X be a subset of a group G. The directed Cayley graph is the graph whose vertex set is G and where arcs leaving vertex g in G are of the form g --> gx for each x in X. Undirected Cayley graphs can be defined similarly.

This talk will explore previously known as well as new results about Cayley graphs with respect to enumeration, isomorphism and Hamiltonicity.

A graph has a Gray code for proper k-colourings if is possible to list all its proper k-colourings in such a way that consecutive elements in the list differ in the colour of exactly one vertex. In this talk, I will show the existence of Gray codes for proper k-colourings for several graphs and values of k.

For fixed k and values t[1..k] we try to count the number of aperiodic strings a[1..n] for which S_k(a) = t_k, where S_k is the k-th elementary symmetric function. The alphabet of the string a is a ring R. After setting up a general framework, specific results are given for the following cases:

• (a) R is Z(q), the ring of integers mod q, and k=1, or q=4 and k=2.
• (b) R is F(q), the finite field of q elements, and k = 3.

We describe a heuristic for 4-colouring a planar graph based on Kempe's method of recolouring Kempe chains. The heuristic gives rise to a special family of graphs which cause the algorithm to cycle. The structure of these graphs is described, and a modified heuristic is presented. In practice the method is found to always succeed in 4-colouring a graph in O(n^2) time. A proof that it works would be another proof of the 4-colour problem.

I shall also describe how this heuristic relates to the successful proofs of the 4-colour problem, and the obstacles that remain to developing this heuristic into a proof. This is joint work with Bill Kocay (Computer Science, University of Manitoba).