Combinatorics Special Session

Australian Mathematical Society Annual Meeting University of Sydney, September 1998.

Graph cohomology – a combinatorial problem appearing in algebra, topology, and physics

Dror Bar-Natan (Hebrew University of Jerusalem)

Using the standard “edge contraction” map and the odd but simple notion of “antisymmetric (oriented) sets” we construct the graph complex: a vector space with one basis element for each graph, together with a square-zero endomorphism d called “the differential”. Graph cohomology is (ker d)/(im d); simple to define, but far from understood. Various variants of graph cohomology relate to various parts of algebra, topology, and physics, and better understanding of graph cohomology will teach us new things in these fields. We briefly illustrate these relationships with two examples, saying a few words on Lie algebras and a few words on knot theory. No prior knowledge of these subjects and/or of homology theory will be assumed. Up to a sign, the talk will end 10 minutes earlier than scheduled.

Chemical applications of graph generation

Gunnar Brinkmann (Bielefeld)

Fakultät für Mathematik, Universität Bielefeld

D 33501 Bielefeld

Email: gunnar@mathematik.uni-bielefeld.de

The aim of this talk is not to present the newest techniques and algorithms designed for applications of structure enumeration in chemistry, but to give just a short sketch of the most important applications.

In the beginning the role of structure enumeration in automatic structure elucidation and for finding the most probable structure of some hypothetical structure will be sketched. Examples of enumeration programs used in chemistry will be given.

Then some applications of structure generation in mathematical chemistry will be presented. The questions dealt with in this context are very similar to purely mathematical problems.

At the end of the talk I will give some examples showing that structure enumeration is also a useful tool in mathematical research.

Parameterized complexity: retrospective and open questions

Rod Downey (Victoria University of Wellington, New Zealand)

Parameterized complexity is an attempt to try to understand the contribution of various aspects of a combinatorial problem to its overall complexity. We now see the area as a major paradigm towards the problem of paractically coping with theoretical intractability.

It seems appropriate, after nearly 10 years, to look at the successes, and to articulate some of the major open questions. The author gave a similar talk in the SIAM minisymposium on parameterized complexity as part of the SIAM meeting on Discrete mathematics in Toronto earlier this year.

The talk is intended to be relatively general.

Combinatorics of Forrester-Baxter paths

Omar Foda (University of Melbourne)

I would like to discuss aspects of the combinatorics of the paths that label eigenstates of Forrester-Baxter statistical mechanical models. I also wish to point out an unexpected connection with the modular group.

Group representations and symmetric embeddings of graphs

Jozef Širáň (Slovak University of Technology, Bratislava)

A number of theorems on highly symmetric embeddings of graphs rely on representations of groups. We describe the connection of group representations to graph embeddings and survey briefly the known results. Focusing on representations within the symmetric groups or matrix groups we outline new results on Cayley maps and other highly symmetrical graph embeddings.

Semi-Latin squares

Walter Wallis (Southern Illinois University)

A Semi-Latin square of side n and strength k (SLS(n, k)) is a generalization of a set of k mutually orthogonal Latin squares of side n. These squares are important when no set of k MOLS exist, and have also proved useful in other cases. Specifically, indecomposable SLS(n, k) (ones not equivalent to sets of MOLS) have several applications. This talk will survey the existence of SLS, with emphasis on the indecomposable case.

Perfect factorisations and Latin squares without subsquares

Ian Wanless (University of Melbourne)

A k-factor in a graph G is a subgraph which includes every vertex of G and is regular of degree k. A partitioning of the edges of G into 1-factors is called a 1-factorisation. A 1-factorisation is perfect if the union of any two 1-factors is a single (Hamiltonian) cycle. In this talk we consider perfect factorisations of the complete graph K_{n} and the complete bipartite graph K_{n,n}. In particular we investigate links between such factorisations and Latin squares which have no proper subsquare.

Hamiltonian decompositions of regular graphs

N. C. Wormald (University of Melbourne)

The most natural model of random regular graphs is uniform: for fixed d, choose a graph uniformly at random from all d-regular graphs with n vertices. It was shown several years ago that the resulting graph is a.a.s. hamilitonian; that is, the probability that it is hamiltonian tends to 1 as n → ∞. In fact it was shown that for odd d ≥ 3, the graph a.a.s. decomposes into (d−1)/2 edge-disjoint Hamilton cycles plus a perfect matching. The proof involves the concept of contiguity of sequences of probabilistic spaces. The obvious conjecture was that for even d ≥ 4, the graph a.a.s. decomposes into d/2 edge-disjoint Hamilton cycles.

The standard technique for approaching such problems will be described. Along the way we will consider the following question. Choose independently four random perfect matchings M_{1}, M_{2}, M_{3}, M_{4} of 2k vertices. What is the probability that M_{1} ∪M_{2}, M_{2} ∪M_{3}, M_{3} ∪ M_{4} and M_{4} ∪ M_{1} all induce Hamilton cycles? This question does not appear to yield to any standard approach.

This work is joint with Jeong Han Kim.