Research projects in Discrete Mathematics and Theoretical Computer Science

Graham Farr, Kerri Morgan and Rebecca Robinson
Faculty of Information Technology, Monash University, Clayton, Victoria 3800, Australia
Graham.Farr@monash.edu, Kerri.Morgan@monash.edu, Rebecca.Robinson@monash.edu

Contents

Introduction
PROJECTS
     1. Tutte-Whitney polynomials
     2. Transforms and minors for binary functions
     3. Powerful sets and codes
     4. Algebraic properties of graph polynomials
     5. Topological containment
     6. Online Graph Atlas
     7. Cost-effectiveness of algorithms
Glossary

Introduction

Our research projects fall within discrete mathematics and theoretical computer science. This type of mathematics is fundamental to the modern world. It includes the mathematics of computation, communication, and information.

We work on (a) the theory of algorithms, computation, and information, and (b) combinatorial structures used in computer science, including graphs (abstract networks), maps (graphs embedded in two-dimensional surfaces), matroids (structures that generalise both graphs and finite subsets of a linear space), and codes.

Below we list some research topics for PhD students. All of them have a strong theoretical component. The first few, 1-4, require a stronger mathematical background, and may involve little or no programming (though the possibility of doing some programming, to search for examples or try out ideas, cannot be ruled out completely, and some projects based on 4 may involve more programming). The later ones, 5-7, involve more programming, together with some system-building (especially for 5) or computational experiments.

Most of the terms used in the descriptions below can be found in textbooks or online references. You can also look up our Glossary at the end. Above all, do not hesitate to ask questions!

We belong to both the cross-faculty Discrete Mathematics Research Group and the Faculty of I.T. For further information about the Group, see the schedule of events at http://users.monash.edu/~gfarr/research/res-gp-mtgs.html and the blog at https://blogs.monash.edu/discretemaths/.

“There is nothing so practical as a good theory.” (Kurt Lewin, 1943)

1. Tutte-Whitney polynomials

Graham Farr and Kerri Morgan

Counting is arguably the oldest and most fundamental mathematical activity, and lies at the heart of combinatorics.

Given a graph, there are many things about it that you might want to count, including:

• spanning trees
• forests
• spanning subgraphs
• colourings, with a given number of colours (where each vertex is given a colour, and adjacent vertices get different colours)
• flows, where each edge is given a flow (or current) from a given set of values, and flow is conserved (i.e., inflow = outflow) at each vertex; we are especially interested in cases where no edge has zero flow
• acyclic orientations, where each edge must be given a direction so that there is no directed cycle in the graph

• network reliabiltiy: it enables computation of the probability that a network remains connected, if all its links can fail, independently of each other and with the same probability;
• coding theory: it can be specialised to give the weight enumerator of a binary linear code, which captures the distribution of codewords according to their weight;
• statistical physics: it can be transformed to give the partition functions of the Ising and Potts models;
• knot theory: it contains the Jones polynomial of an alternating link.

2. Transforms and minors for binary functions

Graham Farr and Kerri Morgan

A binary function is a function that assigns, to each subset of a finite set, a number (which may be thought of as its “weight”). Binary functions generalise cutset spaces of graphs. It turns out that binary functions that do not come from a graph can still have Tutte-Whitney polynomials that contain a lot of interesting information (1993, 2004, 2007). For example, Tutte-Whitney polynomials of general binary functions contain the weight enumerator of an arbitrary code (so it doesn't need to be linear), and the reliability probability of an arbitrary clutter.

In previous work, I developed a theory of minor operations for binary functions (extending the deletion and contraction operations for graphs and matroids) along with a family of transforms that extend duality. These are the basis of the minor order, under which one binary function is a minor of another if it can be obtained from the other by some sequence of deletions and contractions.

In the special case of graphs, the minor order relation is used for good characterisations of many graph properties. For example: a graph is a forest if and only if it does not contain a triangle as a minor; a graph is a series-parallel graph if and only if it does not contain K₄ as a minor; and a graph is planar if and only if it does not contain K₅ or K_3,3 as a minor (Wagner's variant of Kuratowski's Theorem).

This project is to investigate the minor order relation for binary functions, find excluded minor characterisations for important classes of these functions, and develop the theory of excluded minor characterisations for these objects.

3. Powerful sets and codes

Graham Farr and Kerri Morgan

A set S ⊆ {0,1}^E of binary vectors, with positions indexed by E, is said to be a powerful code if, for all X ⊆ E, the number of vectors in S that are zero in the positions indexed by X is a power of 2. By treating binary vectors as characteristic vectors of subsets of E, we say that a set S ⊆ 2^E of subsets of E is a powerful set if the set of characteristic vectors of sets in S is a powerful code. Powerful sets (codes) include cocircuit spaces of binary matroids (equivalently, linear codes over GF(2)), but much more besides. Our original motivation was that, to each powerful set, there is an associated nonnegative-integer-valued rank function (1993), although it does not in general satisfy all the matroid rank axioms. Powerful sets are special cases of binary functions (see above), and in fact are precisely the binary functions that have Tutte-Whitney polynomials that are “proper” polynomials in that their exponents are all integers. But powerful sets are interesting in their own right, as a natural generalisation of binary linear spaces, independently of the role they also play in the world of binary functions.

A.Y.Z. Wang (UESTC) and I have laid some foundations for a theory of powerful sets, focusing on their combinatorial properties. We proved fundamental results on special elements (loops, coloops, frames, near-frames, and stars), their associated types of single-element extensions, various ways of combining powerful sets to get new ones, and constructions of nonlinear powerful sets. We showed that every powerful set is determined by its clutter of minimal nonzero members. (This provides a loose analogue for the concept of a basis in a linear space, and extends the fact that the cutset space of a graph is generated by cutsets.) Finally, we showed that the number of powerful sets is doubly exponential, and hence that almost all powerful sets are nonlinear.

Our paper included some open questions. Some other topics for further work: develop a theory of duality for powerful sets; investigate coding-theoretic properties of powerful sets; find new interesting evaluations of Tutte-Whitney polynomials of powerful sets; refine our estimates for the numbers of powerful sets of each order. Some of these topics have been the subject of some further investigation with colleagues, but it is early days and there is lots of room for new participants.

4. Algebraic properties of graph polynomials

Kerri Morgan and Graham Farr

An important feature of any polynomial is its roots. The roots of the Tutte polynomial, and graph polynomials arising from partial evalutions of this polynomial (for example, the chromatic polynomial), give important information about the graph including the chromatic number of the graph, and the number of components and blocks in a graph.

The question of which numbers can be roots of a given graph polynomial and related questions interest mathematicians, computer scientists and physicists. The interest in physics arises from the connection between the Tutte polynomial and the Potts model partition function. The Potts model is used to study how local interactions in a network affect some global properties of the network. It has been used in analysis of behaviour in social networks, community detection, developmental biology, foam behaviours and tumour growth. The limit points of the complex roots of these functions give possible locations of physical phase transitions. This has motivated a large amount of research in identifying root-free and root-dense regions for the Tutte and chromatic polynomials of some families of graphs.

Possible research questions include:

• Is there an algorithm that, given a polynomial of degree n, finds a graph with a Tutte/chromatic/... polynomial with the given polynomial (or a shifted version of it) as a factor?
• Can we prove that two graphs have chromatic roots that are related in non-trivial ways --- preferably, without going to the trouble of computing these polynomials and their roots directly (since that is generally very difficult)? The same type of question can be asked about other graph polynomials in the Tutte-Whitney family.
• Can we find new relationships between the structure of the graph and the algebraic properties of the roots of the graph polynomials?

5. Topological containment

Graham Farr and Rebecca Robinson

Informally, a graph G topologically contains another graph H (the pattern graph) if it has a subgraph which has the same “shape” as H (although it might not necessarily be isomorphic to H). Formally, G topologically contains H if there is a subgraph of G that can be obtained from H by replacing the edges of H by paths, where all these paths have to be disjoint from each other (except possibly at their endpoints). There is alternative terminology for this, e.g., G contains an H-subdivision.

Suppose H is fixed, and ask, what is the structure of graphs that do not topologically contain H? This is a different question for each H. Some general results are known (due to Grohe, Kawarabayashi, Marx and Wollan, 2011), which give a rough description of graphs that do not topologically contain H, and it is known that each such class of graphs can be recognised in polynomial time (due to Robertson & Seymour, 1985, 1995). But these polynomial-time algorithms are not practical, and really not even implementable. So there remains interest in determining the exact structure of graphs that do not topologically contain a particular fixed pattern graph H, and finding good, efficient, implementable algorithms to detect topological containment of such a fixed H.

If H is, say, the triangle graph (a 3-cycle), then the graphs that do not topologically contain H are just the forests. If H is the tetrahedron (a 4-clique), then the graphs that do not topologically contain H are just the series-parallel graphs (Dirac, 1952; Duffin, 1965). Characterisations are also known for K_3,3 (Hall, 1943) and the wheels with 4, 5, 6, and 7 spokes (the first two by me, the last two by Rebecca Robinson with me). We are now trying to develop further results of this type. A major goal is to deal with K₅ (i.e., a 5-clique), which may help us solve a major open problem in graph theory, Hajós's Conjecture (1940s). A distinctive feature of our approach is the use of computer search, to assist us in constructing proofs that require a large amount of case analysis. This is joint work with Rebecca Robinson.

6. Online Graph Atlas

Graham Farr, Paul Bonnington and Kerri Morgan

This is about constructing a large repository of graphs that can be queried by users in various ways. The user might ask for graphs with a particular size range that have some particular combination of properties and parameter values. There are many theoretical and practical problems that arise in this project; some relate to construction of the repository, while others relate to the relationships between the various parameters. There is room for several PhD students. This is joint work with Paul Bonnington, Kerri Morgan, and a current PhD student. It started with a pilot project involving Honours student Nick Barnes in 2009, followed by another Honours student project, with Man Son Jason Sio, in 2010.

7. Cost-effectiveness of algorithms

Graham Farr

This topic was introduced in a recent paper: https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/viewArticle/2349.html
Cost-effectiveness is an important issue when considering the real costs of using algorithms to solve practical problems when approximate solutions may be acceptable and computational resources are limited. Given a problem and a variety of possible algorithms with different computational complexities and different performances, how do you decide which one to use? Cost-effectiveness is about balancing solution quality with time spent, in a quantitative way; most previous work considers these issues in isolation from each other. There is much scope for both theoretical and experimental work. Emphasis could be on optimisation algorithms, or machine learning algorithms, or both.

Glossary

binary function: a function f : 2^E → C that assigns numbers to all the subsets of a set. These numbers may be complex numbers, though in particular cases a more restricted range may be appropriate, such as the real numbers or the set {0,1}. In most cases of interest, we require that f(∅) ≠ 0. The prototypical example is when E is the edge set of some graph and f is the indicator function of the cutset space of the graph: it assigns value 1 to every member of the cutset space, and 0 to all other subsets of E.

binary matroid: a matroid in which the rank function is the rank function of some binary linear space (i.e., linear space over GF(2)).

clutter: a collection of incomparable sets. In other words, within the collection, no set properly contains any other set. So the sets form an antichain under the subset relation. Also known as a Sperner family.

contraction: the operation of removing an edge from a graph and identifying its endpoints. The two endpoints are “merged” into a single vertex. Imagine an edge shrinking, or contracting, to nothing, so that its two endpoints become one. Any edge that was adjacent to one of the endpoints of the contracted edge is now adjacent to the vertex formed by identifying those endpoints. Everything else in the graph is unchanged. Contraction extends to matroids and binary functions. It is, in a precise sense, the dual of deletion.

cutset: a minimal set of edges whose removal disconnects some component of a graph.

cutset space (also called cocircuit space):
Its members are disjoint unions of cutsets. We call it the cutset space because the symmetric difference of any two members of the cutset space is again a member of the cutset space, so they form a linear space over the two-element field under position-wise mod-2 addition (i.e., position-wise XOR). Every cutset space has a corresponding binary function, namely the indicator function of the cutset space.

deletion: the operation of simply removing an edge from a graph, leaving its endpoints --- and everything else in the graph --- unchanged. Deletion extends to matroids and binary functions. Deletion is, in a precise sense, the dual of contraction.

dual of a planar graph: the vertices of the dual graph represent the faces of the original graph, and two vertices in the dual are adjacent if their corresponding faces share an edge (in the original graph). Duality extends to matroids, and has been shown to be an instance of the Hadamard transform (i.e., n-dimensional mod-2 discrete Fourier transform (1993)).

matroid: a pair (E, r), where E is some set (called the ground set) and r : 2^E → Z_≥0 is a function that assigns, to every subset X ⊆ E, a nonnegative integer r(X), called the rank of X, such that

1. r(X) ≤ |X| for all X;
2. if X ⊆ Y then r(X) ≤ r(Y) ;
3. r(X∩Y) + r(X∪Y) ≤ r(X) + r(Y) for all X,Y.     (submodularity)

minor: a graph H is a minor of a graph G if H can be obtained from G by some sequence of deletions and contractions. The terminology extends to matroids and binary functions.

rank function:
For a graph G = (V, E), the rank of a set of edges X ⊆ E is the number of vertices incident with edges in X minus the number of connected components of the subgraph formed by X.
For a matroid, see above.
For a binary function, a rank function can be obtained by the rank transform (1993). This can play the role of a conventional rank function in some situations, although it does not, in general, satisfy the matroid rank axioms.

set system: just a collection of some subsets of a set.

subdivision of an edge: the operation of inserting a new vertex into the middle of an edge of a graph, thereby subdividing it. Equivalently, we delete the edge, add a new vertex, and add two new edges incident at that new vertex, one going to each of the endpoints of the former edge.
subdivision of a graph: a new graph obtained by some sequence of subdivisions of edges. Equivalently, edges in the original graph are replaced by paths, to form a new graph, with all internal vertices of these paths being disjoint from all other vertices in the new graph. A graph G is a subdivision of another graph H (or, G is an H-subdivision, for short) if and only if H can be obtained from G by a sequence of edge contractions in which every contracted edge has an endpoint of degree 2 (at the time the contraction is done). Graph G contains an H-subdivision if some subgraph of G is an H-subdivision, or in other words, if H is a topological minor of G.

topological minor: a graph H is a topological minor of a graph G if H can be obtained from G by some sequence of deletions and contractions in which an edge cannot be contracted unless at least one of its endpoints has degree 2. So a topological minor is a special type of minor; not all minors are topological minors. For example, a 4-spoke wheel is a minor of a triangular prism, since it can be obtained by contracting one of the “side” edges of the prism (i.e., one of the edges that does not belong to a triangle). But that particular contraction is forbidden, when forming topological minors, because neither endpoint of that edge has degree 2. Topological minors do not extend to matroids (or binary functions), since there is no notion of vertices, or vertex degree, for those objects. Alternative terminology: H is a topological minor of G if and only if G contains an H-subdivision.

Tutte polynomial: a two-variable polynomial, denoted by T(G; x, y), which can be defined for any graph G by
T(G; x, y)   =   R(G; x-1, y-1) , where R(...) is the Whitney rank generating function.
First studied by W.T. Tutte (1954).

weight enumerator of a code: a generating polynomial whose coefficients give the number of codewords of each possible weight.
Introduced by Florence Jessie MacWilliams (1963).

Whitney rank generating function: a two-variable polynomial, denoted by R(G; x, y), defined for any graph G by
R(G; x, y)   =   ∑_X⊆E x^r(E)-r(X)y^|X|-r(X) ,
where r is the rank function of the graph.
First studied by Hassler Whitney (1932).

Created 20 April 2017;
Last updated 23 April 2017.
Please send comments, corrections and enquiries to Graham.Farr@monash.edu