论文标题
通过本地占用的图形结构
Graph structure via local occupancy
论文作者
论文摘要
第一作者与Jenssen，Perkins和Roberts（2017）一起最近展示了硬核模型在无三角形图上的局部特性如何保证存在大型独立集，该集合的大小与Shearer（1983）相匹配的大小与最著名的渐近差异相匹配。目前的工作通过两种方式加强了这一点：首先，通过通过Lovász局部引理的应用来保证更强的图形结构；其次，通过根据局部稀疏性扩展超越三角形图，例如处理有限的局部边缘密度，有限的本地霍尔比和有界集团数的图。这一概括和改进了其他早期的工作，包括Shearer（1995），Alon（1996）和Alon，Krivelevich和Sudakov（1999），以及Molloy（2019），Bernshteyn（2019）和Achlioptas，Iliopoulos和Sinclair（2019）的最新结果。我们的结果源自围绕硬核模型构建的通用框架。它在我们称之为本地占用的属性上枢转，在通过概率信息中得出图形结构的方法之间进行了干净的分离，并验证必要的概率信息本身。
The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of large independent sets, of size matching the best-known asymptotics due to Shearer (1983). The present work strengthens this in two ways: first, by guaranteeing stronger graph structure in terms of colourings through applications of the Lovász local lemma; and second, by extending beyond triangle-free graphs in terms of local sparsity, treating for example graphs of bounded local edge density, of bounded local Hall ratio, and of bounded clique number. This generalises and improves upon much other earlier work, including that of Shearer (1995), Alon (1996) and Alon, Krivelevich and Sudakov (1999), and more recent results of Molloy (2019), Bernshteyn (2019) and Achlioptas, Iliopoulos and Sinclair (2019). Our results derive from a common framework built around the hard-core model. It pivots on a property we call local occupancy, giving a clean separation between the methods for deriving graph structure with probabilistic information and verifying the requisite probabilistic information itself.
