权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Approximate structure in large graphs and hypergraphs

大图和超图的近似结构

基本信息

批准号：
EP/S00100X/1
负责人：
Deryk Osthus
金额：
$ 41.71万
依托单位：
University of Birmingham
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2019
资助国家：
英国
起止时间：
2019 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FS00100X%2F1
关键词：
Approximate structure large graphs 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.

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