# Discrete Mathematics & Algebraic Combinatorics

New models of lattice polygons and polyominoes
(posted for 2017/2018 - also listed in Mathematical Physics & Statistical Mechanics)

Self-avoiding walks were originally conceived in the 1940s as a model of long polymers like DNA, but have since been the subject of many results in combinatorics, mathematical physics and probability theory, including some exciting developments in just the last few years. One useful tool is the concept of irreducible self-avoiding walks, which act a bit like the primes in number theory, and are connected to renewal processes in probability theory.

The goal of this project is to study the related concepts of irreducible polygons and polyominoes. This may involve looking at the corresponding renewal processes, doing some numerical series analysis, or using analytic combinatorics to search for solvable models.

Contact Nicholas Beaton nrbeaton@unimelb.edu.au

Self-interacting polymers in confinement
(posted for 2017/2018 - also listed in Mathematical Physics & Statistical Mechanics)

Self-avoiding walks on a lattice are a classical model of long polymer chains, and when equipped with a nearest-neighbour interaction energy they form a simple yet rich model of collapsing polymers. However, very little has been proven rigorously about the model in two or more dimensions.

The goal of this project is to study a simplified version of the model, namely interacting walks and/or loops in a two-dimensional strip or three-dimensional tube. These can be analysed using a transfer-matrix approach. One question is the zero-temperature limit in both the positive and negative energy regimes — that is, when very few or very many interactions are preferred. Another is the possibility of using self-interacting walks as a (highly simplified) model of strand-exchange operations in polymers like DNA, with potential applications to Monte Carlo methods for dense polymers.

Contact Nicholas Beaton nrbeaton@unimelb.edu.au

Schubert puzzles
(Posted for 2017/2018)

"Puzzles" are remarkable combinatorial objects that appear naturally in Schubert calculus and in the Littlewood--Richardson rule. They have various incarnations, but can be for example depicted as square-triangle tilings of certain regions of the plane:

The goal of the project is to familiarise oneself with these objects, and then to understand how their counting is related to an associative algebra. This, combined with the enumeration of particular configurations (Pieri rule), is enough to characterize the algebra. One can then try to generalize the counting by introducing weights for various tiles, and see if this preserves associativity.

Contact: Paul Zinn-Justin pzinn@unimelb.edu.au

Linear algebra and statistics
(posted for 2017-2018)

The purpose of this project is to explore how geometric quantities like angles and projection, familiar from linear algebra, show themselves in multi-dimensional statistics

Contact Peter Forrester pjforr@unimelb.edu.au

Continued fractions
(posted for 2017-2018)

The mathematics underlying continued fractions shows itself in many different sub-disciplines, for example number theory, dynamical systems and the analysis of algorithms. After some familiarising with the classical theory, the project aims to consider the less familiar complex case, where the numbers appearing are Gaussian integers.

Contact Peter Forrester pjforr@unimelb.edu.au

Perfect codes in Cayley graphs
(Also listed in Operations Research, posted for 2016-2017)

Perfect codes have been important objects of study ever since the dawn of coding theory in the late 1940s, and after more than six decades they still receive much attention today. The aim of this project is to study perfect codes in Cayley graphs, which are generalizations of perfect codes in the classical setting.

Contact Sanming Zhou sanming@unimelb.edu.au

Arc-transitive graphs
(Also listed in Operations Research, posted for 2016-2017)

A finite graph is a finite set together with a family of 2-element subsets of the set; each element in the set is called a vertex and each 2-element subset in the family is called an edge. An oriented edge is called an arc. If all vertices have the “same status” in the graph and all arcs have the “same status” as well, then the graph is said to be arc-transitive. Examples of arc-transitive graphs include the 1-skeletons of the five Platonic polyhedral. The study of arc-transitive graphs has long been an important area in algebraic graph theory with strong links to group theory. The goal of this project is to study some families of arc-transitive graphs whose automorphism groups contain a subgroup acting imprimitively on the vertex set.

Contact Sanming Zhou sanming@unimelb.edu.au

Cores of graphs
(Also listed in Operations Research, posted for 2016-2017)

A homomorphism from a graph X to a graph Y is a mapping from the vertex set of X to the vertex set of Y that preserves the adjacency relation. Two graphs X, Y are said to be homomorphically equivalent if there is a homomorphism from X to Y and also there is a homomorphism from Y to X. The smallest induced subgraph of X that is homomorphically equivalent to X is called the core of X. This notion plays an important role in understanding structure and colouring of graphs. It is also closely related to several application domains, including synchronization. The purpose of this project is to understand the cores of some families of graphs, especially Cayley graphs of some finite groups.

Contact Sanming Zhou sanming@unimelb.edu.au

Exact solutions for polygon and walk models
(Also listed in Mathematical Physics & Statistical Mechanics, posted for 2016-2017)

Lattice paths and polygons are studied extensively in combinatorics and statistical physics where they serve as simple toy models for polymers and vesicles. Mostly these have been studied on the square lattice. One project is to find exact solutions to such models on other two-dimensional, say Archimedean, lattices. In another project we aim to extend the exact solution for punctured staircase polygons to more general cases, see I Jensen and A Rechnitzer, Exact perimeter generating function for a model of punctured staircase polygons, J. Phys. A: Math. Theor. 41 215002 (2008).

Contact: Iwan Jensen I.Jensen@ms.unimelb.edu.au

Plane partitions, generating series and free fermions
(Also listed in Mathematical Physics & Statistical Mechanics, posted for 2016-2017)

Plane partitions are important combinatorial objects, with a rich theory that has influenced many different disciplines of contemporary mathematics and physics. Plane partitions generalize the concept of integer partitions to two dimensions. Given an integer $$n \geq 1$$, a plane partition $$\pi$$ of weight n is an array of non-negative integers $$\pi(i,j)$$ such that for all $$i,j \geq 1$$,

\begin{align*} \pi(i,j) \geq \pi(i+1,j), \quad\quad \pi(i,j) \geq \pi(i,j+1), \quad\quad \text{and} \quad\quad \sum_{i,j} \pi(i,j) = n. \end{align*}

It is often convenient to think of plane partitions as columns of cubes of height $$\pi(i,j)$$ stacked over each coordinate square $$(i,j)$$, giving rise to a three dimensional representation.

Calculating the number of plane partitions of a given weight $$n$$ is a classical enumerative problem that was solved by Percy MacMahon in 1912. The solution of this problem is phrased in terms of a generating series, a standard device in discrete mathematics which acts as a 'clothes-line' for the numbers that interest us. Today many different generating functions of plane partitions exist, corresponding to the various ways of refining their counting, for example by allowing different coloured cubes (as in the figure above).

The aim of this project is to calculate the generating series of some classes of plane partitions which have not yet been considered in the literature, using a powerful framework from mathematical physics, the fermionic Fock space. This technique has already led to great success in studying the statistics of plane partitions, as seen most notably in the work of Fields Medallist Andrei Okounkov and collaborators.

Contact: Michael Wheeler mwheeler@ms.unimelb.edu.au