Extremal Problems Linking Graphs and Set Systems

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

Many problems and results from extremal set theory, can be generalised by imposing some graph structure on the ground set. This often leads to interesting questions which involve a mixture of graph theoretic and other combinatorial techniques. We will initially consider extending the concept of separating set systems in this way. Existing work in this direction mainly involves separating paths and even here there are some intriguingly open problems. Questions can be asked involving particular graph families, general bounds, or more complicated structures than paths, and each of these directions has a different flavour.Another point of interface between graphs and set systems is the discrete hypercube. Here, we propose to work on problems concerning the path and cycle structure, a starting point being Norine's antipodal colouring conjecture. We also propose to develop some ideas of the supervisor and Nicholas Day, on Voronoi games in the hypercube, which brings problems from metric geometry into the hypercube setting.