全体会议(标题和摘要)

主要内容

茱莉亚Bottcher:简并图的大小Ramsey数与G(n,p)的划分普适性
图G的r- color size-Ramsey number是图H的最小边数,使得H的任何r- color都有一个单色的G-copy。
随机图在大小拉姆齐数的研究中起着重要的作用。利用随机图,我们建立了具有有界极大度的d退化图的尺寸-拉姆齐数的一个新界。

在演讲中,我将总结关于大小-拉姆齐数的已知知识,解释与随机图的联系以及它们所谓的划分普遍性,并概述我们在证明中使用的方法。

基于与彼得·艾伦的合作。

鲍里斯·Bukh:随机的代数结构
我将给出一类依赖于随机多项式的随机构造。这些建筑有一个令人愉快的特性,即好的事件几乎同时发生。然后,我将展示如何使用这些结构来构建接近最优的极值图,以及相关的对象。

彼得Keevash:着色圆环面
我们证明了Engbers和Galvin的猜想以及Kahn和Park关于离散环面Z_m^d的q-染色数的猜想(我们给出了固定q和偶数m在d上的渐近),我们的方法也适用于同态。这是和马修·詹森的合作。

Andrzej Ruciń滑雪:嵌入Erdős-Rényi随机图到随机正则图
Erd之间的关系ő因此 enyi模型\ (G (n, m)\)和常规模型\ \ (G (n、d)\)2004年,Kim和Vu首次研究了随机图。特别地,他们展示了一个广泛的范围\ (\),一个人可以把两者结合起来,这样A.A.S.\ (\ \ G (n, m) \子集G (n, d)\),在那里\ (m = (10 (1) \ tfrac {2 m} n\).后来是杜德克,弗里兹,鲁奇ń滑雪,ŠIleikis稍微扩展了m的范围,并将他们的结果推广到随机的\ (k \)统一超图。不过,范围\ (m)已被限制为\ (m = o (n ^ k)\)
最近,在证明二部随机图的一个类似结果时,我们发现了一种方法来涵盖这种情况\ (m = \θ(n ^ 2)\)也除了标准的转换技术之外,这个证明在很大程度上依赖于一个关于双色准随机图中存在交替循环的纯粹确定性结果。在我的演讲中,我将概述二部模型的证明。这是与T的联合功。Klimoš卵子,空空的。苍鹭”,M。Šileikis。

Alex Scott:带有禁止诱导子图的图
众所周知(例如考虑随机图),n个顶点上的图不需要有完整的子图或大小超过log n的独立集。但如果我们考虑的图不包含某些特定的诱导子图呢?Erdos和Hajnal在20世纪80年代推测,对于每一个图H,都有一个常数c,使得每一个在n个顶点上没有诱导复制H的图,都包含一个大小为n^c的团或稳定集。Erdos-Hajnal猜想仍然是非常开放的,但我们将讨论一些进展和相关的结果。这包括与玛丽亚·查德诺夫斯基、雅各布·福克斯、保罗·西摩和索菲·斯皮克尔的合作。

Asaf Shapira:在未知分布下测试图表
图属性测试的目的是了解图的全局属性和局部统计量之间的关系。在经典模型中,图的局部统计量是相对于顶点集上的均匀分布定义的。如果一个图的局部统计能允许人们区分满足P的图和不满足P的图,那么一个图的性质P就是可测试的。
Goldreich最近介绍了该模型的一种推广,即赋予输入图的顶点集一个任意和未知的分布,并询问哪些属性可以在经典模型中测试,也可以在这个更一般的设置中测试。我们通过给出这些属性的一个(令人惊讶的“干净”)表征来完全解决这个问题。为此,我们证明了顶点加权图的一个相互独立的移除引理。

与L. Gishboliner合作

Dan Spielman:有限自由概率与Ramanujan图
我们引入了一个有限模拟的Voiculescu自由概率,它允许我们计算某些随机矩阵的期望特征多项式,并证明了这些多项式的根位置的界。我们概述了如何用这个理论来证明存在各种顶点数和次数的二部拉马努扬图。

假设没有自由概率或拉马努詹图的先验知识。

您的浏览器中已禁用JavaScript