Erdos-Ko-Rado type problems, Isoperimetric inequalities, and other topics in Combinatorics.

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

Combinatorics is the area of mathematics that is concerned with the relationship between the size of mathematical structures, and their other (geometric/structural) properties. It is mainly concerned with discrete mathematical objects, such as graphs and hypergraphs. It has very close links with Theoretical Computer Science and Discrete Analysis; it also has growing connections to Algebra, Geometry and Number Theory. A classical example of a problem in Combinatorics is to determine the maximum possible number of edges in an n-vertex graph with no triangle; this problem was solved by Mantel over a century ago, but the analogous problem where one replaces a triangle with a cycle of length eight, remains open to this day. Most of the analogous problems for hypergraphs, also remain completely open. There has been much exciting progress in Combinatorics in recent years, utilising techniques both from within Combinatorics itself, and also from other areas of mathematics such as Algebra, Analysis and Probability Theory. This PhD project involves gaining familiarity with research-level techniques in Combinatorics (including those utilising algebraic, analytic and probabilistic methods), and simultaneously tackling some unsolved problems in Combinatorics. One area of investigation in the project is that of Erdos-Ko-Rado type problems. These ask for the largest possible size of a family of objects in which any two of the objects `agree' in some way. Recently, several Erdos-Ko-Rado type problems have been tackled successfully using techniques from Algebra and Analysis. Many, however, remain unsolved. For example, a question of Sos: how many subsets of (1, 2, ..., n) can you take, such that any two of the subsets share an arithmetic progression of length 3? Virtually nothing is known about this question. Another area of investigation is that of isoperimetric inequalities. Isoperimetric problems are classical objects of study in mathematics. In general, they ask for the smallest possible `boundary' of an object of a certain `size'. Perhaps the oldest is the isoperimetric problem in the plane: among all subsets of the plane of area 1, which has the smallest boundary? The answer was `known' to the ancient Greeks, but it was not until the 19th century that a rigorous proof was given. In the last fifty years, there has been a great deal of interest in `discrete isoperimetric inequalities'. These deal with discrete notions of boundary in graphs. They have important applications in computer science and information theory. One very natural unsolved problem in this area is the isoperimetric problem for r-element sets, popularised by Bollobas and Leader; there are many others.