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.