Graphs and Matroids

点击翻译按钮获取中文摘要

This research deals is in the area of mathematics known as combinatorics. This is the study of objects built from discrete objects, and especially their structural properties. My own work is in graphs, hypergraphs and matroids.***Graphs are a set of vertices, some of which are adjacent and some of which are not. It is useful to think of a pair of adjacent vertices as an edge; thus we say that if two vertices are adjacent then they are joined by an edge. As a simple example, a graph can represent a computer network: the vertices correspond to computers and the edges are direct connections. This already suggests an important property: different parts of the graph can be connected (in the graph theory sense of the word) without being directly connected. The study of connectivity in graphs is extremely important, and a wide range of applications and connections. For instance, the extent to which a graph can remain connected despite some of its edges being removed is a measure of the reliability of a computer network. Perhaps surprisingly, the eigenvalues of the adjacency matrix of the graph give a lot of information about this.***Hypergraphs can be thought of as a generalization of graphs where edges can contain more than two vertices. Thus a hypergraph is a set of vertices, together with some particular collection of subsets of them, each of these subsets being an "edge". My interest in these is from the point of view of factorizations, which can be thought of as a way of colouring the set of edges such that each colour is represented the same number of times at each vertex. The motivating question is: if some of the edges are already assigned colours in some way, when can we complete the colouring to a factorization? There are some "obvious" necessary conditions on the parameters (an example in the simplest case: if we want to pair up the vertices of a graph there better be an even number of them), the question is are these conditions sufficient? Are there any deep obstacles to structure, or are the trivial obstacles the only ones?***Matroids are another discrete structure, with a ground set of elements, where certain subsets of these elements considered "independent". There are a few rules: the empty set should be independent, any subset of an independent set is again independent, and given two independent sets of different sizes, there is an element in the larger one but not the smaller that can be added to the smaller to make a new independent set. This is inspired by the linear independence of set of vectors in a vector space, but is much more general. It turns out that there is a strong geometrical flavour (in particular there are well-defined notions of line, plane, etc). Matroids have strong connections to discrete optimization: finding an optimal assignment between candidates and tasks, and finding the shortest path between points in a network are both examples of finding a maximum weight basis in a matroid.