Approximate structure in large graphs and hypergraphs

图和其他相关组合结构的研究为生物学、理论计算机科学、大数据分析、调度和通信中的许多网络分析提供了理论基础。在最简单的情况下，这些网络产生一个由顶点组成的图，这些顶点的适当对通过边连接。超图是在非二元关系建模时产生的：我们也可以用一条超边连接三元组或更大的顶点集，而不是成对的。在许多情况下，所考虑的图或超图是巨大的，直接分析它们是没有希望的。然而，一种越来越成功的方法(从结构和算法的角度来看)是考虑近似，然后将关于近似设置的知识传回原始设置。在这个项目中，我们将关注通过考虑分数解和超图容器而获得的“近似”信息。通过分数解的逼近：组合问题经常可以被视为整数规划，其中找到最优解往往是困难的。找到分数解(可能在相同的输入上，但通常在小得多的输入上)可能要简单得多，然后目标是从中推断出原始问题的良好(近似)解决方案。我们将在设计、拉丁方和分解问题以及超图匹配的设置中开发一种系统的方法。容器逼近：许多重要的问题，例如数论、着色、随机图、极值组合学和编码理论，可以用适当定义的超图中的独立集来表示。最近出现的超图容器方法允许通过所谓的容器对适当的给定超图的独立集的集合进行简洁的“近似”。然而，在一些重要的问题中，一般的方法似乎是自然的，但该方法目前失败了，例如，因为容器的数量太大而没有用，因此需要新的想法。我们将在满足给定约束的图的计数和典型结构上开发一种适当的方法来解决这类问题。

The study of graphs and other related combinatorial structures provides the theoretical foundation for the analysis of many networks arising in biology, theoretical computer science, big data analysis, scheduling and communication. In the simplest case, these networks give rise to a graph which consists of vertices, with suitable pairs of these vertices connected by edges. Hypergraphs arise when modelling non-binary relationships: instead of pairs we can also connect triples or larger vertex sets by a single hyperedge.In many situations, the graphs or hypergraphs under consideration are huge, and it is hopeless to analyze them directly. However, an increasingly successful approach (both from a structural and algorithmic perspective) has been to consider approximations and then transfer knowledge about the approximate setting back to the original one. In this project, we will focus on `approximate' information gained by considering fractional solutions as well as hypergraph containers.Approximation via fractional solutions: Combinatorial problems can frequently be viewed as integer programs, where it is often intractable to find the optimum solution. Finding a fractional solution (possibly on the same input, but often on a much smaller input) can be much simpler, and the goal is then to infer a good (approximate) solution to the original problem from this. We will develop a systematic approach in the setting of designs, latin squares and decomposition problems, as well as hypergraph matchings.Approximations via containers: Many important problems involving e.g. number theory, colourings, random graphs, extremal combinatorics and coding theory can be formulated in terms of independent sets in suitably defined hypergraphs. The recently emerged method of hypergraph containers allows the succinct `approximation' of the collection of independent sets of a suitable given hypergraph by so-called containers. However, there are important problems where the general approach seems natural but the method currently fails e.g. because the number of containers is too large to be useful and so new ideas are required. We will develop an appropriate approach to solve such problems on the enumeration and typical structure of graphs satisfying given constraints.