下面这个很自然的问题是由钟和埃尔德格斯在80年代早期提出的，此后被重复了很多次。在所有边数固定的r-图H中，Turán数ex(n, H)的最小值是多少?他们真正关注的是一个等价的，也许更自然的问题，即在n个顶点和e条边的任何r-图中都无法避免的r-图的最大尺寸是多少?在最初的论文中，他们在e的大部分范围内渐进地解决了这个问题。在后续工作中，Chung和erdkus解决了3-均匀情况，并提出了4-均匀情况作为自然的下一步。在这篇论文中，我们在这个问题上取得了40多年来的第一个进展，通过渐近地解决了4-一致的情况，给了我们一些关于答案应该如何表现的一般指示。©2021 Elsevier Inc.

在压缩感知中，M × N传感矩阵上的限制等距特性(RIP)(其中M < N)保证了稀疏向量的高效重建。如果一个矩阵在s-稀疏向量上表现为delta-近似等距，则该矩阵具有(s, delta)- RIP性质。众所周知，一个M × N的i.i.d. N(0,1 /M)项的矩阵，只要s小于或类似于delta(2) M/ logN，就有高概率为(s, delta)-RIP。另一方面，大多数先前旨在确定性地构造(s, delta)-RIP矩阵的工作都失败了，当s >>根M.时，另一种寻找RIP矩阵的方法可能是绘制一个随机高斯矩阵并证明它确实是RIP。然而，有证据表明，当s >>根M时，无论在最坏情况还是平均情况下，这个认证任务在计算上都是困难的。在本文中，我们研究了M × N个具有i.i.d.n (0,1 /M)个条目的矩阵在“可能但困难”的情况下，在根M << s小于或类似于M/ logN的情况下，验证RIP属性的确切平均情况时间复杂度。基于低度似然比的分析，我们给出了严格的证据，证明需要亚指数运行时N-<(Omega)除以波浪号>(s2/ M)，证明了最大容忍稀疏性和所需计算能力之间的平稳权衡。由于Koiran和Zouzias的原因，这个下界本质上是紧密的，与现有算法的运行时间相匹配。我们的硬度结果允许delta取(0,1)中的任何常数值，这捕获了压缩感知的相关区域。这改进了Wang等人现有的平均硬度结果，该结果仅限于delta = o(1)。

有序图是顶点集具有线性顺序的图。我们证明了对于每一个正整数k，存在一个常数ck>0，使得在n个顶点上的任意有序图G，其性质是G及其补都不包含大小为k的诱导单调路径，既没有团，也没有大小至少为nc的独立集合。这加强了Bousquet, Lagoutte和Thomassé的结果，他们证明了无序图的类似结果。上述论文的一个关键思想是表明，在n个顶点上的任何无序图，如果不包含大小为k的诱导路径，并且对于某个小c(k)>0，其最大度不超过c(k)n，则包含两个不相交的线性大小子集，它们之间没有边。对于有序图，这种方法失败了，因为通过Fox的构造，当k≥3时，类似的陈述是错误的。我们提供了一些进一步的例子，表明这个陈述对于避免其他有序树的有序图也不成立。

图划分，或根据某些条件将图划分为两个或多个部分，在离散数学中很自然地出现，这类问题已被广泛研究。在20世纪90年代，Ando推测每个三次图的顶点可以被分割成两个部分，从而产生同构子图。利用概率方法和精细的重着色参数，我们证明了大型连通图的安藤猜想。

在这篇简短的笔记中，我们证明了以下关于盒的交图的Kővári-Sós-Turán定理的类比。如果G是n个轴平行盒的交点图，且G不包含Kt,t的副本，则G最多有ctn(log n)2d+3条边，其中c = c(d)>0只取决于d。我们的证明是基于探索箱性、分离维和偏序集维之间的联系。利用这种方法，我们还证明了K2的Basit, Chernikov, Starchenko, Tao和Tran的构造，平面上点和矩形的2-free关联图可以用来推翻Alon, Basavaraju, Chandran, Mathew和Rajendraprasad的猜想。证明了存在分离维数为4的图具有超线性的边数。

给定一个采用张量T:××…→F (F是一个字段),i-flattening等级的T矩阵的秩的行索引的列索引通过B =…×××××…一个,其条目由T T的max-flattening等级的相应值被定义为mfrank (T) = max弗兰克张量T (T):→F叫做semi-diagonal,如果T(…,)≠0每一个∈和T(…,)= 0每一个…,∈都截然不同。本文证明了如果T:A→F是半对角线，则mfrank(T)≥[所给出的公式]，这个界是可能的最佳界。我们给出了这个结果的几个应用，包括著名的Frankl-Wilson定理在禁交上的推广。此外，针对Aharoni和Berger的一个猜想，我们表明，如果r-均匀多超图H的边用z种颜色着色，使得每个颜色类都是大小为t的匹配，那么H包含大小为t的彩虹匹配，前提是z>(t−1)(rtr)。这改进了Alon和Glebov, Sudakov和Szabó之前的结果。

给定一个图H，极值数ex(n, H)是无H图中n个顶点上的最大边数。我们在一些关于二部图的极值数的猜想上取得了进展。首先，对二部图K-s,K-t的细分写K-s,K-t'，我们证明ex(n, K-s,K-t') = O(n(3/2 - 1/2s))。这证明了Kang, Kim和Liu的一个猜想，并且紧于隐含的常数，对于t足够大的s。其次，对于任何整数s, k >= 1，我们证明对于特定的图L依赖于s和k, ex(n, L) = Theta(n(1+s/sk+1))，回答了Kang, Kim和Liu的另一个问题。这个结果涉及到Erdos和Simonovits的一个旧猜想，它断言每个有理数r是(1,2)的一个元素，对于某些适当的图H，在ex(n, H) = Theta(n(r))的意义上是可实现的，给出无限多个新的可实现指数，并暗示1 + 1/k是所有k >= 1的可实现指数的极限点。用H-k表示图H的k细分，这一结果也表明，对于任意二部图H和任意k，存在delta > 0使得ex(n, Hk-1) = O(n(1+1/k-delta))，部分解决了Conlon和Lee的问题。第三，扩展Conlon和Lee的一个最新结果，我们证明了任何在一侧具有最大度r且不包含C-4作为子图的二部图H满足ex(n, H)= o(n(2-1/r))。

我们研究Erdos和Hajnal在90年代初提出的以下问题。对于所有n个顶点的图G，当G中的任意m个顶点同时包含一个团和一个大小为log n的独立集合时，m的最小可能值是多少?我们构造了一些例子，表明m最大为2(2(log log n)1/2+o(1))，从自然猜测，即随机图中获得了大约根号n的上界的两倍次多项式改进。我们的(概率)结构产生了拉姆齐图的新例子，它虽然没有非常大的同质子集，但在任何小的顶点子集中都包含团和大小为log n的独立集。这在随机图中是不成立的。我们的证明是基于使用词典编纂产品和使用随机性之间的相互作用。

我们证明了二部图G中的每一个完美匹配都与G中至少一半的完美匹配相交。这个结果在图的邻接矩阵的恒量方面，以及在图上的无序和排列方面，具有等价的公式。我们给出了几个相关的结果和开放性问题。

我们考虑了连接性增强问题(CAP)，这是可生存网络设计领域的一个经典问题。它是关于以最便宜的方式将图的边连通性增加一个单位。更准确地说，给定一个k边连通图G=(V,E)和一组额外边，任务是找到额外边的最小基数子集，其与G的相加使图(k+1)边连通。如果k是奇数，已知该问题可以简化为树增强问题(TAP)——即G是一棵生成树——最近已经取得了重大进展，导致近似因子低于1.5(目前最佳因子为1.458)。然而，到目前为止，援助计划的进展并没有转到共同行动计划。事实上，就在最近，Byrka、Grandoni和Ameli (STOC 2020)通过提出一种基于与TAP的最新进展脱节的方法的1.91近似算法，成功地获得了CAP的第一个低于2的近似因子。我们首先通过介绍允许利用TAP的见解和方法来接近CAP的技术来弥合TAP和CAP之间的差距。然后，我们介绍了一种基于新的分析技术的新方法，使近似因子低于1.5。通过这些成分，我们得到了CAP的-近似算法，因此也得到了TAP。这导致了目前这两个问题的最佳近似结果以统一的方式，通过显著改进上述CAP的1.91近似，以及Grandoni, Kalaitzis和Zenklusen (STOC 2018)对TAP的1.458最佳近似因子。此外，我们从最近的TAP进展中继承的一个特征是，当额外链路上最大与最小成本之间的比率有界时，我们的方法可以处理加权设置，在这种情况下，我们获得了低于1.5的近似因子。

一个典型的分解问题是，某个图G的边是否可以被分割成另一个图h的不相交副本。这个领域中最古老和最著名的猜想之一是由Ringel在1963年提出的，它涉及到将完整图分解成树的不相交副本。它说任何有n条边的树将2n+1次放入完整图K2n+1。在本文中，我们对大n证明了这个猜想。

对于每一个正整数n，我们构造一个具有n个顶点和独立数O(n(3/4))的哈塞图。这样的图具有色数Omega(n(1/4))，这大大改进了先前最著名的具有色数Theta(log n)的Hasse图结构。此外，如果我们还要求周长至少为k >= 5，则我们构造的Hasse图独立数不超过n(1-1/2 -4+o(1))。证明的依据是在多入射平面上存在点线排列，并避免了某些我们认为有独立意义的禁止子构型。这些结果还具有以下令人惊讶的几何结果。它们暗示在平面上存在一个C (n)曲线族，使得离点图G (C)是无三角形的(或具有高周长)，但G的色数是n的多项式。同样，由于Pach, Tardos和Toth，以前最著名的结构只有对数色数。

证明了每个n-顶点竞赛G都有一个色数不小于n5/9-o(1)的无环子图，同时存在一个n-顶点竞赛G，其每个无环子图的色数不小于n3/4+o(1)。这有力地建立了纳萨尔和尤斯特的猜想，并改进了他们的另一个结果。我们的证明结合了概率和谱技术以及一些额外的想法。特别地，我们证明了一个引理，表明每个具有许多可传递子竞赛的竞赛都有一个几乎是可传递的大子竞赛。这可能是无关紧要的。

我们考虑线性约束表现为(递归)块结构的整数和线性规划问题:如果删除少量约束，问题分解为独立且有效可解决的子问题。一个突出的例子是n倍整数规划问题及其推广，在最近的文献中得到了相当大的关注。以前已知的解决这些问题的算法是基于增强框架的，这是一种局部搜索的定制整数编程变体。在本文中，我们提出了一种不同的方法。我们的算法依赖于参数搜索和一个新的接近界。我们证明了块结构线性规划可以通过Norton, Plotkin和Tardos的参数搜索框架与Megiddo的多维搜索技术相结合的适应性有效地解决。这也形成了我们的算法的一个子例程的整数规划情况下，通过解决它的一个强松弛。然后我们证明，对于这种松弛的任何给定的最优顶点解，在ℓ1-distance内存在一个最优整数解，与问题的维数无关。这反过来又使我们能够有效地找到一个最优整数解。我们将我们的技术应用于n倍结构的整数规划和线性规划或有界对偶树深度，这是该领域的两个基准问题。 We obtain the first algorithms for these cases that are both near-linear in the dimension of the problem and strongly polynomial. Moreover, unlike the augmentation algorithms, our approach is highly parallelizable. Read More: https://epubs.siam.org/doi/10.1137/1.9781611976465.101

我们开发了一种基于Friedman-Pippenger树嵌入技术(1987)及其算法版本的通用嵌入方法，主要是由于Aggarwal等人(1996)，增强了回滚思想，允许按顺序回溯先前执行的嵌入步骤。这被证明是将大周长图嵌入扩展图的强大工具。作为该方法的应用，我们解决了两个问题:•对于图H，我们用Hq表示从H得到的图，通过将其边细分为q−1个顶点。我们证明了k-size-Ramsey数[方程]对于n个顶点上的每个有界度图H和q = Ω(log n)都满足[方程]，这是最优的常数因子。这证实了Pak(2002)的一个猜想。•我们给出了一个确定的多项式时间算法，用于查找强展开器图中给定顶点对之间的顶点不相交路径。更精确地说，设G为λ = O(d1−ε)的(n, d， λ)-图，设P为G中对于某个小常数c的不相交顶点对的任意集合，使得在G中每个顶点的邻域内来自P的顶点最多为d/4个。然后存在一个多项式时间算法，在P中每个顶点对之间寻找不相交顶点路径，且每条路径长度相同[方程]。对的数量和路径的长度都是最优的，直到一个常数因子;结果回答了Alon和Capalbo(2007)的一个问题的离线版本。

最近，人们对将公平性方面纳入经典聚类问题的兴趣激增。最近引入的两种k-中心问题的变体是由Bandyapadhyay、Inamdar、Pai和Varadarajan介绍的彩色k-中心问题，以及由Harris、Pensyl、Srinivasan和Trinh介绍的公平稳健k-中心问题。为了解决公平性问题，与传统的k-Center相比，这些模型包含了额外的覆盖约束。这些模型的先验逼近结果需要放松一些通常的硬约束，如待打开中心的数量或涉及的覆盖约束，因此只能得到常因子伪逼近。在本文中，我们介绍了一种新的方法来处理这种覆盖约束，导致(真)逼近，包括彩色k-中心的4-逼近(解决了Bandyapadhyay, Inamdar, Pai和varadarajan提出的一个开放问题)和公平稳健k-中心的4-逼近，其中(真)常数因子逼近的存在也是开放的。我们补充了我们的结果，表明如果允许无限数量的颜色，那么彩色k-Center不承认具有有限近似保证的近似算法，假设P≠NP。此外，在指数时间假设下，如果颜色的数量在地面集的大小上增长得比对数快，那么问题是不可逼近的。

Füredi、Kahn和Seymour(1993)关于非一致超图匹配的一个著名猜想指出，对于任何边权值为w的超图，都存在一个匹配M，使得不等式Σe∊M g(e)w(e)≥OPTLP成立，且g(e) = |e| - 1 +1/|e|，其中OPTLP表示正则LP松弛的最优值。虽然猜想仍然开放，但最近由Brubach、Sankararaman、Srinivasan和Xu(2020)得出的最有力的结果——建立和加强了Bansal、Gupta、Li、Mestre、Nagarajan和Rudra(2012)的先前工作——表明上述不等式适用于g(e) = |e| + O(|e| exp(- |e|))。实际上，他们的方法适用于更一般的采样设置，其中，给定正则LP松弛的点x，任务是有效地对包含每条边e的匹配M进行采样，其概率至少为x(e)/g(e)。我们提出了更简单和易于分析的程序，从而改善结果。更准确地说，对于正则LP的任何解x，我们介绍了一个基于指数时钟的简单算法，用于Brubach等人的采样设置，实现g(e) = |e|- (|e|-1)x(e)。除了g的微小改进之外，我们的技术可能会开辟新的方法来攻击最初的猜想。此外，我们提供了一个简短且可以说是优雅的分析，表明对于猜想的原始设置的自然贪婪方法显示了相同g(e) = |e| - (|e| - 1)x(e)的不等式，即使对于更一般的超图b匹配问题也是如此。阅读更多信息:https://epubs.siam.org/doi/10.1137/1.9781611976496.22

非自适应组测试是指使用最小数量的同时合并测试从较大的总体中推断出稀疏缺陷集的问题。近年来无噪声群试验的积极成果促进了实际噪声模型的研究，其中最突出的是稀释噪声。在稀释噪声模型下，测试池中的项目具有被独立稀释的固定概率，这意味着它们对测试的贡献不会生效。在这种情况下，我们研究了相对于现有算法实现错误概率消失所需的测试次数，并提供了一个与算法无关的逆界。与其他噪声模型相比，我们还遇到了一个有趣的现象，即通过选择合适的噪声水平相关的伯努利试验设计，可以抵消最终测试结果上的稀释噪声，从而在高噪声环境下实现匹配的可达性和逆界。

20世纪40年代的经典哈德威格猜想指出，任何至少为r的半音数图都有r阶团作为小子。哈德威格猜想是一类经过充分研究的问题的一个例子，这类问题是在具有一定限制条件的图中可以保证有多大的小团。这种类型的一个问题是，在n个独立数为α (G)的顶点上，一个小团在不超过r的图上的最大尺寸是多少。如果成立，哈德威格猜想将暗示存在一个n/ α (G)阶的小团。Kuhn, Osthus, Krivelevich和Sudakov的结果表明，如果我们假设G对于某个二部图H是无H的，那么我们可以找到一个多项式大的小团。最近，Dvorak和Yepremyan在回答Norin的一个问题时，将其扩展到无三角形图。我们完成了图像，并表明对于任意图H也是如此，回答了Dvorak和Yepremyan的问题。特别地，我们证明了任何无ks的图都有阶为cs(n/alpha(G))1+110(s-2)的团小子，对于某些常数cs只依赖于s。这个结果中的指数紧紧于1s-2项前面的常数因子。

要覆盖给定r边彩色图G的所有顶点，需要多少个单色路径、循环或一般树?这些问题在20世纪60年代被提出，在过去的50年里被各种研究人员深入研究。在本文中，我们建立了这个问题与以下超图中自然的helly型问题之间的联系。粗略地说，这个问题要求覆盖超图H的所有边所需的最大顶点数，如果已知H的几条边的任何集合都有一个小的覆盖。我们获得了超图问题的相当精确的边界，并利用它们对Bal和DeBiasio、Kohayakawa、Mota和Schacht、Lang和Lo以及Cirao、Letzter和Sahasrabudhe提出和研究的几个关于用单色树覆盖图的问题给出了一些意想不到的答案。

Chung和Graham的一个著名定理指出，如果h≥4，那么一个比武T是准随机的，当且仅当T包含每个h顶点比武的“正确次数”作为一个子比武。本文研究了T的准随机性与T中单个H顶点竞赛H的计数之间的关系。我们考虑了两种类型的计数，全局计数和局部计数。我们首先观察到，如果T具有正确的H的全局计数并且H≥7，则只有当H是可传递的时，T的拟随机性才被强制。在研究准随机对象时，下一个自然的问题是，拥有正确的H的局部计数是否足以使t具有准随机性。如果竞赛H具有这种性质，则称它是局部强迫的。局部强迫问题的变体之前已经在图和超图设置中研究过。也许与我们的问题最相似的是Simonovits和Sós，他们研究了固定图H作为G的诱导子图的“正确计数”是否意味着G一定是准随机的，在适当的意义上。他们证明了当H是正则的时候确实是这样，并推测它对所有H都成立(除了3个顶点上的路径)。与Simonovits-Sós猜想相反，在比赛设置中，我们证明了恒定比例的所有比赛都不是局部强迫的。事实上，任何局部强制比赛本身都必须具有很强的准随机性。另一方面，与全局强迫情况不同，我们构造了无限个非传递局部强迫竞赛族。

对于图G，设f(G)表示G中最大切割的大小。将f(G)估计为G的顶点和边数的函数的问题有着悠久的历史，近五十年来得到了广泛的研究。本文提出了一种基于半定规划的证明f(G)下界的方法。我们使用这种方法在有很少三角形的图和无k -r图中找到大切口。

我们提出了一种适用于4圈数较少的图的稀疏图正则性方法，包括新的5圈数的计数引理和去除引理。通过删除o(n3/2)条边，可以使每个没有5个周期的n顶点图无三角形。对于r > 3，每个周长大于5的n个顶点r图有o(n3/2)条边。方程x1+x2+2x3=x4+3x5没有非平凡解的[n]的每个子集的大小都是o(n)。

给定一个大图H，二项随机图G(n, p)是否包含一个H的副本作为高概率的诱导子图?这个经典问题已经被广泛地研究了各种图H，可以追溯到Erdos和Bollobas以及Matula在1976年对G(n, p)的独立数的研究。在本文中，我们证明了诱导匹配的渐近最佳可能结果，证明了对于某个大常数C，如果C/n <= p <= 0.99，则G(n, p)包含阶约为2 log(q)(np)的诱导匹配，其中q = 1/1 - p。

我们考虑求解形式为min{cτx: Ax = b, x∈Z≥0}的整数规划的问题，其中A是一个多级随机矩阵，其意义如下:A的原始树深度以参数d为界，这意味着A的列可以被组织成深度不超过d的根森林，因此不受祖先/后代关系约束的列在同一行中没有非零项。我们给出了一种在固定参数时间f(d，∥A∥∞)·nlogO(2d) n内解决该问题的算法，其中f是一个可计算函数，n是A的行数。该算法适用于强模型，其中运行时间仅度量输入数的单位算术运算，而不依赖于输入数的位长。这是第一个在强意义上实现几乎线性运行时间的多级随机整数规划fpt算法。对于两阶段随机整数规划，我们的算法在时间2((r+s)∥A∥∞)O(r(r+s)·nlogO(rs) n内工作，这在多项式因子和对r和s的依赖性方面都优于之前的方法。事实上，当r = 1时，在指数时间假设下，对s的依赖性渐近几乎紧密。我们的算法也可以并行化:我们在PRAM模型中给出了一个实现，使用n个处理器实现了运行时间f(d，∥A∥∞)·logO(2d) n。我们的算法的主要概念成分是一个新的多阶段随机整数规划的接近结果。我们证明了如果我们考虑一个整数程序P，假设有一个约束矩阵a，那么对于P的线性松弛的每一个最优解，都存在一个P的最优(积分)解，在ℓ∞-范数内，在以∥a /∥∞函数和a的原始树深度为界的距离内。在实现这个结果的过程中，我们证明了Klein的结构结果的推广和相当大的改进。一旦建立了接近性结果，这就允许我们应用基于树深度的分支策略，该策略由线性松弛的最优解指导。

设A∈Zm×n是一个积分矩阵，且A, b, c∈Z满足A≥b≥c≥0。问题是识别A是否为{A, b, c}-模，即A的n×n子行列式集的绝对值是否为{A, b, c}。除非A具有一个重复关系，即A有非零的n × n子行列式k1和k2满足2·|k1|=|k2|，否则我们将在多项式时间内成功求解这个问题。这是著名的完全单模矩阵识别算法的一个扩展。作为我们分析的结果，我们提出了一个多项式时间算法，在{a, b, c}-模约束矩阵上求解任意常数a, b和c的标准形式的整数程序。

设A∈Zm×n是一个积分矩阵，且A, b, c∈Z满足A≥b≥c≥0。问题是识别A是否为{A, b, c}-模，即A的n × n个子行列式的绝对值集合是否为{A, b, c}。除非A具有一个重复关系，即A有非零的n×n子行列式k1和k2满足2·|k1| = |k2|，否则我们将在多项式时间内成功解决这个问题。这是著名的完全单模矩阵识别算法的一个扩展。作为我们分析的结果，我们提出了一个多项式时间算法，在{a, b, c}-模约束矩阵上求解任意常数a, b和c的标准形式的整数程序。

介绍了整数程序(IP)的完整性数。粗略地说，完整数是通过混合整数松弛(MIP)求解IP所需的最小整数约束数。这个数的一个显著性质是它在约束矩阵的单模变换下的不变性。考虑到约束矩阵的最大次要Delta，我们的分析允许我们做出如下形式的陈述:存在一个数字tau(Delta)，这样一个IP有n个变量和n+根号n/tau(Delta)个不等式约束，可以通过一个小于n个整数约束的MIP松弛来求解。从我们的结果可以得出，仅由n个约束定义的ip可以通过具有O(根Delta)多个整数约束的MIP松弛来求解。

布尔格2[n]是[n] ={1，的所有子集的族。， n}按包含顺序排列，链是由2[n]的成对可比较元素组成的族。令s = 2n/ (n.n/2.)，即最小链分解为2[n]时链的平均大小。我们证明了2[n]可以被分割成(n.n/2)个链，使得除最多o(1)个链外，所有链的大小都为s(1+ o(1))。这渐近地证明了1985年Furedi的一个猜想。我们的证明是基于概率的论证。为了分析我们的随机划分，我们开发了图容器方法的加权变体。利用这个结果，我们还回答了Das、Lamaison和Tran最近提出的一个kalai类型的问题。使最大亚族(2[n])中不包含任何一个亚族的大小不超过(n.n/2.)的禁止可比对的最小数目是多少?我们证明答案是(v.. 8 + o(1))2nv n. Finally, we discuss how these uniform chain decompositions can be used to optimize and simplify various results in extremal set theory.

弦图是平面上曲线的交图。我们证明了对于每一个e>0，如果G是一个有n个顶点的字符串图，使得G的边密度小于1/4−e，那么V(G)包含两个线性大小的子集a和B，它们之间没有边。常数1/4是这种现象的一个尖锐的阈值，因为有边密度小于1/4+e的字符串图，这样就有一条边连接任意两个对数大小的顶点子集。在足够稀疏的字符串图中存在线性大小的集合A和B，它们之间没有边，这是Lee关于分隔符的最近结果的直接结果。我们的主要定理找到了这个仍然成立的最大可能密度。在曲线为x单调的特殊情况下，Pach和本文作者也证明了同样的结果，他们还提出了一般情况下的猜想。

我们考虑容性循环覆盖问题:给定一个具有度量边长和顶点需求的无向完整图G，我们希望用顶点不相交的循环覆盖顶点，每个循环最多满足一个需求。目标是最小化总长度和循环数的线性组合。该问题与有能力车辆路径问题(CVRP)以及最小-最大循环覆盖和有界循环覆盖等循环覆盖问题密切相关。我们通过将解与聚阵松弛进行比较，证明了一个贪婪算法跟随一个后处理步骤，对这个问题产生(2 + 2/7)-逼近。我们还证明了我们的算法的分析是严密的，并提供了一个2+的放松下界。

我们引入了经典拉姆齐数的列表着色扩展。我们研究当两个拉姆齐数相等时，以及一般情况下，它们之间的距离可以有多远。我们找到两者相等且相距很远的图序列。对于(公式所示)-均匀团，我们证明了列表拉姆齐数受指数函数的限制，而众所周知，拉姆齐数对于均匀性至少为3是超指数的。这与图的情况形成了鲜明的对比在图的情况下，我们甚至不能确定小集团的相等问题。©2020 Wiley期刊有限责任公司。

Montanari和Richard(2015)提出，对于所有坐标i，自然半定规划(SDP)松弛是否可以有效地优化x⊤Wx /‖x‖=1且xi≥0，其中W∈ℝn×n是从高斯正交综(GOE)或标记矩阵模型中绘制的。在小型数值实验中，该SDP对于GOE似乎是紧的，产生了一个与最优向量x对齐的一级最优矩阵解。然而，我们证明，当n→∞时，SDP并不紧，并证明了该目标函数的上界渐近地不优于简单谱界λmax(W)。我们还使用最近文献中关于低次多项式假设检验的工具提供了证据，证明没有次指数时间证明算法可以改善这种行为。最后，我们提出了进一步的数值实验，估计在这种限制行为变得明显之前n需要多大，提供了一个警告性的例子，反对从sdp在小型“笔记本电脑规模”计算中的有效性推断高维sdp的渐近性。

我们证明了从极值组合学的不同领域选择的结果，包括一些开放问题的完全或部分解。这些主要来自极值图论和拉姆齐理论的结果被收集在一起，因为在每种情况下相关的证明都相当短。

假设一个图G具有属性urn:x-wiley:rsa:media:rsa20969:rsa20969-math-0001，如果它的最大匹配的大小等于最小顶点覆盖的顺序。我们研究了以下过程。设置urn:x-wiley:rsa:media:rsa20969:rsa20969-math-0002，设e1, e2，…eN为Kn边的均匀随机排序，n为偶数。设G0是n个顶点上的空图。当m≥0时，如果Gm∪{em + 1}具有属性urn:x-wiley:rsa:media:rsa20969:rsa20969-math-0003，则Gm + 1由Gm加边em + 1得到。我们分析了这个过程的行为，主要集中在两个问题上:关于GN的结构可以说什么，对于哪个m, Gm将包含一个完美匹配?©2020 Wiley期刊

1989年，罗塔提出了以下猜想。给定n维向量空间V中的n个碱基B1，…，Bn，总能找到V的n个不相交的碱基，每个碱基恰好包含每个Bi中的一个元素(我们称之为横向碱基)。尽管罗塔的基础猜想看起来很简单，而且许多研究人员都付出了努力(例如，该猜想最近成为了“博学者”合作项目的主题)，但它仍然具有很大的开放性。本文证明了总能找到(1/2−o(1))n个不相交的横向基底，改进了Ω(n/logn)的最佳界。我们的结果也适用于更一般的拟阵设置。

我们证明，如果W是从高斯正交系综中得到的N × N矩阵，那么在x(i)(2) -1 = 0(即x是{+/- 1}(N)的一个元素)约束下，4次平方和松弛极有可能不能证明目标N-1中心点x(垂直于)Wx上的上界渐近小于λ (max)(W)近似于2。通过提出一个近似的伪矩结构，我们还推测了一个证明技术，可以证明任何程度的平方和松弛常数为N ->无穷大的下界。

t游问题是TSP和路径TSP的自然推广。给定一个图G=(V,E)，边代价c:E→R≥0，以及一个偶基数集T⊆V，我们想计算一个连接G的所有顶点(可能包含平行边)的最小代价T连接。本文给出了T-tour问题的[公式]-近似，证明了标准LP松弛的完整比最大[公式]。尽管特殊情况下的路径TSP取得了很大的进展，但对于一般的t- tour，这是seb纵然对众多克里斯托弗算法中最优算法的分析的第一次改进(seb纵然，2013)。©2020爱思唯尔

令x(1)，…， x(n)是R-d的一个元素，是单位向量，使得任意三个向量中有一个正交对。n作为d的函数有多大，x(1)+…的长度有多大+ x(n)是?Erdos和Lovasz提出的这两个著名问题的答案与无三角形图的标准正交表示密切相关，特别是与他们的Lovasz相关。函数和最小半定秩。本文研究了一般无h图的这些参数。特别地，我们证明了对于某些二部图H，在所有无H图G上，H的图兰数与v((G) over bar)的最大值之间存在联系。

狄拉克定理的一个广为人知的推广是，如果一个图G在n≥4k个顶点上具有至少n/2的最小度，那么G包含一个恰好由k个循环组成的2因子。从最小度的界限来看，这很容易看出。然而，如果假设G是哈密顿量，则可以推测最小度的界限可以放宽。Sárközy确实证明了这一点。在随后的论文中，最小度界得到了改进，最近由DeBiasio、Ferrara和Morris改进为(2/5+ε)n。另一方面，没有接近这个的下界是已知的，所有关于这个主题的论文都询问最小度是否需要线性。我们通过证明大型哈密顿图具有由固定数量的循环组成的2因子所需的最小度在n中是次线性的来回答这个问题。©2020 Elsevier Inc.。版权所有。

我们引入了一种新的迭代舍入技术，使拟阵多面体中的一个点受到进一步的拟阵约束。这种技术在一个拟阵中返回一个独立的集合，并且有限地违反其他拟阵的约束。除了迭代松弛方法的经典步骤之外，我们还迭代地细化了涉及的拟阵约束。这导致了更具限制性的约束系统，其结构可以被利用来证明可以删除的约束的存在。因此，在整个迭代过程中，我们既收紧约束，又通过在特定条件下删除约束来放松约束。由于细化步骤，我们可以处理比现有迭代松弛和舍入方法更一般的约束类，这些方法通常涉及单个阵面多面体和额外的简单基数约束，这些约束不会重叠太多。我们证明了我们的舍入方法，结合一个阵面相交算法的应用，产生了第一个2-逼近，用于在3个阵面中寻找最大权值公共独立集。此外，我们的2-逼近是基于lp的，解决了问题自然松弛的完整性缺口。在我们的工作之前，已知的完整性差距的上界不大于3，这是由贪婪算法得出的。我们还讨论了我们的技术的各种其他应用，包括允许我们处理矩阵约束和背包约束的混合的扩展。 (© 2020 Springer).

最小割问题是组合优化中最经典的问题之一，被广泛应用。一些最著名的有效可解变体包括全局最小切、最小s-t切和无向图中的最小奇切。我们研究的一类问题可以被看作是上述变量的泛化，即寻找同余约束的最小切分，即，对于一些整数r和m，我们考虑的切分的顶点数与r模m相等。除了是奇数切分的自然泛化之外，同余约束最小切分与整数规划中一个长期存在的开放问题有一个有趣的联系，即由具有有界子行列式的整数约束矩阵描述的整数程序能否有效求解。我们开发了一种新的收缩技术，灵感来自Karger著名的最小切割收缩算法，该算法与进一步的深入研究一起，导致了一个多项式时间随机逼近方案，适用于任何常数模量m的一致性约束最小切割。我们没有收缩原始图的边，而是使用分离技术在较小的顶点集上创建一个辅助图，用于执行随机边收缩。这样，就得到了一个结构良好的候选顶点对的分布，其中涉及的顶点对通常不由边连接。作为副产品，我们的技术揭示了对近最小奇切的新结构见解，更普遍的是，近最小一致性约束切。

我们研究了有效地反驳图的k-可色性的问题，或等价地证明其色数的下界。我们给出了这个问题在稀疏随机正则图中的平均情况计算硬度的形式化证据，显示了一个简单谱证明的最优性。这种证据采取了一种计算安静种植的形式:我们构造了d正则图的分布，它的色数明显小于随机均匀绘制的典型正则图，同时提供了证据，证明这两种分布是由大量算法无法区分的。我们将我们的结果推广到更一般的问题，即证明最大k切割的上界。这种安静的种植是通过最小化种植结构(例如着色或切割)对图频谱的影响来实现的。具体而言，所种植的结构与邻接矩阵的特征向量完全对应。这避免了随机矩阵理论的推出效应，并延迟了种植在光谱或局部统计中可见的点。为了进一步说明这一点，我们对这个问题的高斯模拟给出了类似的结果:一个标记模型的安静版本，其中我们种植一个特征空间，而不是添加一个一般的低秩扰动。我们关于区分两个分布的计算难度的证据基于三个不同的启发式:信念传播的稳定性，局部统计层次结构和低程度似然比。独立的兴趣是，我们的结果包括多标记矩阵模型的低度似然比的通用边界，以及随机块模型的改进低度分析。

边色图的子图称为彩虹，如果它的所有边都有不同的颜色。寻找彩虹子图的问题可以追溯到欧拉在拉丁正方形截线上的工作，并从那时起被广泛研究。本文讨论了关于完全边色图和有向图的彩虹子图的两个相关问题。在第一部分中，我们证明了每个适当边色的完全有向图都包含一个长度为n - O(n(4/5))的有向彩虹循环。这是出于哈恩的一个老问题，并改进了Gyarfas和Sarkozy的结果。在第二部分中，我们证明了在最大度Delta(T) <= beta n/log n的n个顶点上的任何树T都有一个彩虹嵌入到适当的边色K-n中，前提是每种颜色最多出现an次，并且alpha, beta是足够小的常数。©2020 Elsevier Ltd.版权所有。

有向图是没有双向边的有向图，也就是说，如果xy是一条边，那么yx就不是一条边。拉姆齐的大小数量的有向图H,用(r)在右箭头(H),是存在一个有向图的最小m G和m边缘,这样每个2-colouring G的包含一个单色的副本H。在本文中,我们证明了面向尺寸拉姆齐n顶点上的直接路径数量满足(r)在右箭头((pn) /右箭头)=ω(n (2) o (log n))。这提高了Ben-Eliezer下界,Krivelevich Sudakov。它还匹配Bucic和作者的上界，从而在(r) /右箭头((P-n) /右箭头)上建立了渐近紧密的上界。我们还讨论了如何使用我们的方法来改进(r) /右箭头((P-n) /右箭头)的k色版本的最著名的下界。(C) 2020年Elsevier Ltd.版权所有。

在完全图k (n)的任意边序中，单调路径总能找到多长?这个吸引人的问题是Chvatal和Komlos在1971年首次提出的，此后吸引了许多研究人员的注意，激发了各种相关的问题。普遍的猜想是总能找到线性长度的单调路径，但到目前为止，最著名的下界是(2/3-o(1))。在本文中，我们几乎消除了这个差距，证明了完全图的任何边序都包含一个长度为(1-o(1))的单调路径。

我们推导了低信噪比条件下具有等协方差矩阵的高斯混合模型(GMMs)的对数似然的渐近展开。扩展揭示了两种类型的参数估计算法之间的密切联系:矩的方法和似然优化算法，如期望最大化(EM)。我们表明，在低信噪比条件下的似然优化简化为最小二乘优化问题序列，将估计的矩逐个匹配到地面真实矩。这种联系是在广泛的模型中分析EM和最大似然估计的垫脚石。低温电子显微镜数据是研究低信噪比混合物模型的一个激励应用，它可以被建模为对混合物中心施加代数约束的GMM。我们讨论了我们的扩展到代数约束GMMs的应用，以及其他感兴趣的例子模型。

我们考虑最大单调子模函数受基数约束的经典问题，由于其众多的应用，最近已在各种计算模型中研究。我们考虑了一种介于离线模型和流媒体模型之间的干净的多人模型，并从单向通信复杂性的角度对其进行了研究。我们的模型捕捉流设置(通过考虑大量的玩家)，此外，它的两个玩家近似结果转化为健壮的设置。我们为我们的模型提供了紧密的单向通信复杂性结果，由于上述连接，它在数据流和鲁棒设置中具有多重含义。即使只有两个参与者，先验信息理论的硬度结果表明，在我们的模型中，如果只允许对可行集(即尊重基数约束的集)进行查询，则不能达到1/2以上的近似因子。我们证明了查询不可行集的可能性实际上可以被利用来打破这个界限，通过给出一个紧密的2/3近似，花费指数时间，和一个有效的0.514近似。据我们所知，这是第一个在不可行集上查询子模块函数可以得到更好结果的例子。通过上述链接到鲁棒设置，这两个算法都改进了当前最先进的鲁棒子模块最大化，表明超过1/2的近似因子是可能的。此外，利用我们的模型与流的联系，我们通过提出一个紧密的1/2+ε硬度结果来解决流算法的近似值，基于一个新的覆盖函数族的构造。这改进了先前的1−1/e+ε硬度，并匹配，直到任意小的裕度，最著名的逼近算法。

n顶点图G中的1因子是n/2个顶点不相交边的集合，G的1因子分解是将其边划分为边缘不相交的1因子。显然，除非n是偶数且G是正则的(即所有顶点的度数都相同)，G的1-因式分解是不可能存在的。在图中寻找1-因式分解的问题可以追溯到Kirkman在1847年的一篇论文，并从那时起被广泛研究。判断一个图是否具有1因子分解通常是一个非常困难的问题。例如，Csaba, Kühn, Lo, Osthus和Treglown花了60多年的时间，证明了20世纪50年代狄拉克的一个古老猜想，该猜想说，在n个顶点上的每个d正则图都包含一个1-因式分解，前提是n是偶数(公式提出)。在这篇论文中，我们解决了估计F(n, d)的自然问题，即在偶数个顶点上的d正则图中1-因式分解的数量，前提是(公式所示)。在Ferber和Jain的最近结果的基础上改进，该结果本身也改进了20世纪70年代Cameron的结果，我们证明(公式所示)，它是渐近的最佳可能。©2020 János鲍耶数学会和斯普林格出版社。

边色图的子图称为彩虹，如果它的所有边都有不同的颜色。彩虹子图的研究可以追溯到两百多年前欧拉对拉丁平方的研究。从那时起，彩虹结构一直是广泛研究的焦点，并在图标记和分解领域找到了应用。如果每个顶点包含最多k条相同颜色的边，则边着色是局部k有界的。在本文中，我们证明了完整图K的任何这样的边着色，包含了每棵最多(1 - o(1))n/ K个顶点的树的彩虹副本。由于k- n的局部k-边界边着色可能只有(n - 1)/k种不同的颜色，这本质上是紧密的。作为这个结果的推论，我们得到了图论中两个长期存在猜想的渐近版本。首先，我们证明了1963年的Ringel猜想的一个渐近版本，表明任何n-边树都可以装入完整图K-2(n+o(n))中，以覆盖除o(n(2)外的所有边。其次，我们证明了所有的树都有一个几乎和谐的标签。格雷厄姆和斯隆在1980年推测了这种标签的存在。 We also discuss some additional applications.

我们研究了当中心的均值是稀疏的并且它们的维数可能远远大于样本容量时，聚类的统计和计算极限。对一种基于稀疏主成分分析的稀疏聚类算法进行了有限样本分析，结果表明该算法在‖θ‖→∞范围内实现了最优错聚率的极大极小值，且渐近匹配贝叶斯误差。我们的结果要求稀疏度的增长速度要慢于样本容量的平方根。使用最近的计算下界框架——低度似然比——我们提供了证据，证明这个条件是任何多项式时间聚类算法在BBP阈值以下成功的必要条件。这补充了基于约简和统计查询下界的现有证据。与这些现有的结果相比，我们涵盖了更广泛的参数范围，并对所需的运行时和可实现的错聚类错误提供了更精确的理解。我们还讨论了将结果扩展到两个以上的聚类。

我们研究了检测和估计对称随机高斯张量的秩一变形的统计极限。我们建立了临界信噪比的上界和下界，在种植向量的各种先验条件下:(i)均匀采样的单位向量，(ii) i.i.d±1个条目，以及(iii)一个稀疏向量，其中条目的常数分数ρ为i.i.d±1，其余为零。对于每一种情况，当张量的d阶变大时，我们的上界和下界匹配到1+o(1)因子。对于稀疏信号(iii)，对于任何固定的d(包括d=2的稀疏PCA)，我们的边界在稀疏极限ρ→0上也是渐近紧密的。(i)的上界展示了一种让人联想到Baik、Ben Arous和Péché的工作的现象:摄动张量的“特征值”在严格低于摄动本身超过总体时的信噪比下从主体中出现;我们量化了这种效应的大小。对于更大的一类先验，我们也提供了一些一般的结果。特别地，在离散先验问题和连续先验问题之间，阈值位置的大d渐近性是不同的。最后，对于先验(i)和(ii)，我们从统计物理中进行了副本预测，这被推测为任何固定d给出了精确的信息论阈值。独立感兴趣的是，我们引入了一种新的改进的第二矩方法用于邻近，我们的下界基于它。我们的技术避免了依赖于信号和噪声之间相互作用的罕见“坏”事件。 This enables us to close √2-factor gaps present in several previous works. © 2020 Association des Publications de l’Institut Henri Poincaré

最近，人们对将公平性方面纳入经典聚类问题的兴趣激增。最近引入的两种k-中心问题的变体是由Bandyapadhyay、Inamdar、Pai和Varadarajan介绍的彩色k-中心问题，以及由Harris、Pensyl、Srinivasan和Trinh介绍的公平稳健k-中心问题。为了解决公平性问题，与传统的k-Center相比，这些模型包含了额外的覆盖约束。这些模型的先验逼近结果需要放松一些通常的硬约束，如待打开中心的数量或涉及的覆盖约束，因此只能得到常因子伪逼近。在本文中，我们介绍了一种新的方法来处理这种覆盖约束，导致(真)逼近，包括彩色k-中心的4-逼近(解决了Bandyapadhyay, Inamdar, Pai和varadarajan提出的一个开放问题)和公平稳健k-中心的4-逼近，其中(真)常数因子逼近的存在也是开放的。我们补充了我们的结果，表明如果允许无限数量的颜色，那么彩色k-Center不承认具有有限近似保证的近似算法，假设P≠NP。此外，在指数时间假设下，如果颜色的数量在地面集的大小上增长得比对数快，那么问题是不可逼近的。

给定一个从高斯正交系综(GOE)中抽取的随机n×n对称矩阵W，我们考虑在约束集S Rn中证明二次形式x⊤Wx对所有向量x的最大值的上界问题。对于某类归一化约束集S，我们证明，在某些复杂性理论假设的条件下，没有多项式时间算法证明比w的最大特征值更好的上界。我们的结果中包括一个值得注意的特殊情况是超立方体S={±1/n−−√}n，它对应于统计物理中Sherrington-Kirkpatrick自旋玻璃模型的哈密顿量的上界证明问题。我们的证明分为两步。首先，我们将负尖头Wishart模型中的检测问题简化为上述认证问题。然后，我们给出了证据，证明这个Wishart检测问题在经典谱阈值以下是难以计算的，通过表明没有低次多项式可以(在期望中)区分有刺和无刺模型。这种识别计算阈值的方法是在最近一系列关于平方和层次结构的工作中提出的，并且被认为是正确的，适用于一大批问题。我们的证明可以被看作是在对称矩阵上构造一个分布，它在计算上似乎与GOE难以区分，但在x∈S上的最大二次形式远大于GOE矩阵的最大二次形式的矩阵上得到支持。

松弛和舍入方法成为约束子模函数最大化的标准和极其通用的工具。在此上下文中，最常见的舍入技术之一是争用解决方案。这种方案首先舍入每个坐标，然后去掉一些元素，以达到一个可行的集合。第二步，也就是删除元素的步骤，通常是随机化的。这导致了过程中随机化的额外来源，这可能使分析复杂化。我们提出了一种不同的多面体观点来设计争用解决方案，从而避免了在第二步中显式地处理随机化。这是通过关注删除过程的边缘来实现的。除了避免一个随机来源，我们的观点允许使用多面体技术。两者都可以极大地简化争用解决方案的构造和分析。我们展示了如何通过我们的框架，可以获得二部匹配的最优单调竞争解决方案，其平衡度为0.4762。 So far, only very few results are known about optimality of monotone contention resolution schemes. Our contention resolution scheme for the bipartite case also improves the lower bound on the correlation gap for bipartite matchings. Furthermore, we derive a monotone contention resolution scheme for matchings that significantly improves over the previously best one. More precisely, we obtain a balancedness of 0.4326, improving on a prior 0.1997-balanced scheme. At the same time, our scheme implies that the currently best lower bound on the correlation gap for matchings is not tight. Our results lead to improved approximation factors for various constrained submodular function maximization problems over a combination of matching constraints with further constraints.

Mantel的一个著名的结果表明，在n个顶点上具有左垂线(2)/4个右垂线+ 1条边的图必须包含一个三角形。由Rademacher给出的这个结果的一个可靠版本说，事实上，在任何这样的图中，至少有左垂线/2个右垂线三角形。另一个加强，由于许多作者从ErdOs开始的共同努力，说任何这样的图必须有一条边，至少包含在n/6个三角形中。在Mubayi之后，我们研究了这两个结果之间的相互作用，即在这样的图中三角形的数量和它们的书号之间，共享一条边的三角形的最大数量。在其他结果中，Mubayi表明，对于任何1/6 <= beta < 1/4，存在gamma > 0，这样任何在n个顶点上的至少有左垂线(2)/4右垂线+ 1条边和书号最多beta n的图包含至少(gamma - o(1))n(3)个三角形。他还要求从beta的角度对gamma进行更精确的估计。我们对这个相关性做了一个猜想，并证明了beta = 1/6和0.2495 <= beta < 1/4时的这个猜想，从而在这些范围内回答了Mubayi的问题。

在子集选择中，我们寻找涉及一小部分变量的最佳线性预测器。从计算复杂度的角度来看，子集选择是np困难的，并且很少有已知的类可以在多项式时间内求解。主要利用离散几何中的工具，我们证明了原始数据矩阵上的一些稀疏条件允许我们在多项式时间内解决问题。

我们把整数程序的最优解与其线性松弛之间的距离称为接近度。2018年，Eisenbrand和Weismantel证明了接近性与标准形式的程序的维度无关。我们利用整数解的稀疏性结果改进了它们的边界。我们首先用约束矩阵中任何全维小子的最大绝对值来限制接近性，并且这个限制紧到约束数的多项式因子。在有效地将程序转换为等效的程序之后，我们还根据约束矩阵中最大的绝对项给出了改进的边界。我们的结果是根据一般的稀疏性边界表述的，因此任何新的稀疏性结果都会立即改进我们的工作。还讨论了混合整数程序的推广。

在这篇短文中，我们研究了关于超立方体Q(n)具有某些性质的子图的存在性的两个问题。第一个问题，由于erdos - hamburg - pippert - weakley，问是否存在Q(n)的有界度子图，其直径为n。我们通过给出这样一个最大度不超过120的子图的显式构造来回答这个问题。第二个问题是关于超立方体的k个可加扳手的性质，即Q(n)的子图，其中任意两个顶点之间的距离最多比Q(n)大k。用Delta(k，无穷大)(n)表示Q(n)的k-加法式的最小可能最大度，arizulu - hamburg - kostochka表明n/ln ne (-4k) <= Delta(2k，无穷大)(n) <= 20 n/ln n ln ln n。我们通过表明Delta(2k，无穷大)(n) <= 10(4k) n/ln n ln((k+1)) n来改进它们的上界，其中最后一项表示k+1倍的迭代对数。

我们考虑了度量最优IP解的最小支持度的整数规划(IP)稀疏函数的渐近分布，以及度量最优IP解与线性规划(LP)解之间距离的IP到线性规划(LP)距离函数的渐近分布。我们创建了一个框架来研究与整数优化相关的一般函数的渐近分布。已经有大量的研究集中在这些函数可以达到的极值上。然而，人们对它们的典型价值知之甚少。每个函数都定义为一个固定的约束矩阵和目标向量，而右边被视为输入。我们表明，这些函数的典型值小于已知的最坏情况边界，通过提供一个控制其总体渐近分布的似概率结果的频谱。©2020工业与应用数学学会。

无格梯度多面体是混合整数凸最小化模型的最优性证明。我们考虑如何为两个整数变量的无约束模型构造这些多面体。Bell, Doignon和Scarf的一个经典结果表明，存在一个无格梯度多面体，最多有四个面。我们展示了如何构造一个序列(不一定是无格的)梯度多面体，其中每个最多有四个面，有限地收敛到一个无格的梯度多面体。每次更新都需要不断地进行许多梯度计算(通过梯度计算，我们指的是使用梯度的内积计算。对于我们的更新，我们需要最多18个梯度评估。)这个更新过程模仿了梯度下降算法，因此，对于两个整数变量的问题，它产生了一个梯度下降类型的算法。一个悬而未决的问题是如何提高收敛速度以获得最小集或无格集。

我们以不等式的形式介绍了整数程序的完整数。粗略地说，完整数是通过混合整数松弛(MIP)求解IP所需的最小整数约束数。这个数的一个显著性质是它在约束矩阵的单模变换下的不变性。考虑约束矩阵中最大的子Δ，我们的分析允许我们做出如下形式的陈述:存在数字τ(Δ)和κ(Δ)，使得具有n≥τ(Δ)多个变量和n+κ(Δ)⋅n−√多个不等式约束的IP可以通过小于n个整数约束的MIP松弛来求解。我们的结果的一个特殊实例表明，仅由n个约束定义的ip可以通过O(Δ−−√)个整数约束的MIP松弛来求解。

给定一副图G和H,拉姆塞数R (G, H)是最小的N,这样每一个红蓝颜色的完全图k - N的边缘包含G或蓝色的红色副本副本H .如果图G是连接,众所周知,容易显示,R (G, H) > =(竖线G竖线- 1)(chi (H) - 1) +σ(H),其中气(H)是彩色的H和σ(H)是最小的大小颜色类的chi (H)着色图G是称为H-good如果R (G,H) =(竖条G竖条- 1)(chi(H) - 1) + (H)。拉姆齐善的概念是由Burr和Erdos在1983年提出的，从那时起就被广泛研究。本文证明了如果n >= 10(60)竖条H竖条且sigma(H) >= chi(H)(22)，则n顶点循环C-n是H-好的。对于具有高chi(H)和sigma(H)的图H，这以强烈的形式证明了Allen, Brightwell和Skokan的猜想。©2020工业与应用数学学会。

弱子模性是收益递减性质的一种自然松弛，相当于子模性。弱子模性已被用来证明，在可证明的保证下，实践中出现的许多(单调)函数可以有效地最大化。在这项工作中，我们介绍了非单调函数弱子模性的两个自然推广。我们证明了一个有效的随机贪婪算法具有可证明的近似保证最大化这些函数受基数约束。然后，我们提供了一个更精细的分析，考虑到弱子模块化参数在整个算法执行过程中可能会改变(有时会改善)。这导致在某些情况下改进的近似保证。我们将我们的结果应用于单调和非单调最大化问题。

我们提出了从旅行商问题(路径TSP)的路径版本到经典旅行版本(TSP)的黑盒约简。更精确地说，我们证明，给定TSP的α-近似算法，那么，对于任何柱柱的柱柱，对于更一般的路径TSP，都有一个(α+柱柱的柱柱)近似算法。这种简化意味着路径TSP的近似值与TSP的近似值相同，直到有一个任意小的误差。这避免了这两个问题的最著名的近似因子之间的未来差异，因为它们直到最近才存在。TSP的一个被充分研究的特例，图TSP，要求在单位权图中进行巡回。我们的约简表明，图TSP的任何α-逼近算法都意味着其路径版本的(α+绕柱)逼近算法。通过将我们的约简应用于SebA'和Vygen的图TSP的1.4近似算法，我们得到了图路径TSP的多项式-时间(1.4+柱绕)近似算法，改进了Traub和Vygen最近的1.497近似算法。我们通过各种新技术来获得我们的结果，包括一种建立递归动态程序来猜测最优解的重要部分的新方法。在我们的动态程序的核心，我们处理(Path) TSP的新泛化实例，它结合了奇偶约束和某些连接需求。这个问题，我们称之为φ-TSP，它有一个常因子近似算法，在某些情况下，当动态程序不能取得足够的进展时，可以简化为TSP。 © 2020 ACM.

图论中许多极值问题的一个共同主题是图的局部性质和全局性质之间的关系。这种类型最著名的结果之一是Ruzsa-Szemerédi三角形去除引理，它指出，如果一个图ε-远不是无三角形的，那么大小为C(ε)的顶点的大多数子集都不是无三角形的。不幸的是，已知的C(ε)的上界是由塔型函数给出的，并且已知C(ε)不是ε−1的多项式。三角形去除引理已推广到许多其他的图性质，其中一些对应的函数C(ε)是多项式。这就提出了一个自然的问题，由Goldreich在2005年提出，最近由Alon和Fox提出，如何用多项式边界来证明去化引理的性质。本文的主要结果是新的充要条件，以保证一个图性质承认一个具有多项式界的去化引理。虽然两者都是简单的组合标准，但它们暗示了几乎所有这种类型的阳性和阴性结果。此外，我们的新充分条件允许我们获得许多性质的多项式有界去除引理，其先前已知的边界是塔型的。特别地，我们证明了每一个半代数图性质都承认一个多项式有界的去化引理。这证实了阿隆的猜想。

1973年Brown, Erdos和Sós的猜想指出，对于任何k≥3，如果有n个顶点的3-一致超图H不包含一个由k +3个顶点组成的集合，该集合至少跨越k条边，那么它有o(n2)条边。这个猜想的k = 3的情况是著名的(6,3)定理Ruzsa和Szemerédi，它暗示了Roth关于密集整数集中3项等差级数的定理。Solymosi观察到，为了证明猜想，我们可以假设H由某个有限准群Γ的三元组(a, b, ab)组成。由于这个问题对于所有k≥4的情况都是开放的，他进一步提出研究来自有限群的三重系统。在这种情况下，他证明了猜想也适用于k = 4。在这里，我们完全解决了所有有限群和k值的Brown-Erdos-Sós猜想。此外，我们证明了来自群的超图包含横跨k条边的大小集。这是最好的可能，远远超出了猜想。©2019剑桥哲学学会。

我们证明了，在n个顶点上的随机竞赛的每一个2边着色中，都有一个O(n/ log n)阶有向树的单色副本。这推广了第一、第三和第四作者的结果，他们证明了路径的相同陈述，并且紧于常数因子。

给定一个图G和一个双射f: E(G)→{1,2，…，E(G)}，我们说G中的一条轨迹/路径是f-递增的，如果这条轨迹/路径的连续边的标签形成一个递增序列。40多年前，Chvátal和Komlós提出了在Kn的所有边序上提供最长递增轨迹/路径长度的最坏估计的问题。一条路径的情况已经被Graham和Kleitman解决了，他们证明了答案是n-1，而一条路径的情况仍然很大。最近，Lavrov和Loh提议研究这个问题的平均情况版本，其中边的顺序是均匀随机选择的。他们推测(马丁森后来证明了)，这种高概率排序(w.h.p.)包含一条递增的哈密顿路径。本文讨论了边序均匀随机选择的随机图G = Gn,p。在此设置中，我们确定了最长递增轨迹中边数的渐近性。特别地，我们证明了Graham和Kleitman结果的平均情况版本，表明Kn的随机边排序具有w.h.p.长度递增的轨迹(1-o(1))en，并且这是紧的。对于p = o(1)的随机erddigs - renyi图，我们也得到了最长递增路径长度的渐近紧性结果。

神经网络提供了一类丰富的高维非凸优化问题。尽管它们是非凸的，梯度下降方法经常成功地优化这些模型。这激发了最近的研究，试图表征他们的损失表面的性质，可能解释这种成功。在本文中，我们通过研究损失的一个关键拓扑性质来解决这一现象:存在或不存在伪谷，定义为不包括全局最小值的子水平集的连通分量。聚焦于一类由平滑(但通常是非线性)激活函数定义的单隐藏层神经网络，我们确定了一个内禀维的概念，并表明它为假谷的不存在提供了必要和充分条件。更具体地说，有限的内在维保证了对于充分超参数化的模型，不存在与数据分布无关的伪谷。相反，无限的内在维意味着某些数据分布确实存在假谷，与模型过度参数化无关。除了这些积极和消极的结果之外，我们还表明，尽管假谷可能普遍存在，但它们仅限于低风险水平，并且在超参数化模型中以高概率避免。

等角紧框架(ETFs)可用来构造平方和(SOS)优化中出现的半定方案的可行点示例。我们展示了如何在作者最近的一项工作中推广计算，该工作探索了这种联系，也产生了(真实和复杂)etf稀疏性的新边界。一个推论表明，对应于有限投影平面的Steiner ETFs在实现矩阵不等式的紧密性方面是最佳稀疏的，该矩阵不等式控制合成矩阵的不同行的稀疏模式之间的重叠。我们还提出了几个关于进一步推广我们的技术的自然开放问题。

关于各种组合对象相交族的最大可能大小的极值问题得到了广泛的研究。在本文中，我们研究了过饱和扩展，在这种情况下，要求在大于极值阈值的族中必须出现的不相交对的最小数目。我们研究了排列族和k-一致集族中不相交对的最小数目，并确定了最优族的结构。我们的主要工具是不相交对的消去引理。当n≥2sk+38s4时，我们还确定了不存在s大小匹配的k-一致集族的典型结构，并证明了当n≥(2+o(1))k时，顶点集[n]上几乎所有的k-一致相交族都是平凡的。

二部图H的k色二部拉姆齐数是每个k边色完全二部图K-N,K-N包含H的单色副本的最小整数N。对二部拉姆齐数的研究在40多年前由Faudree和Schelp发起，由Gyarfas和Lehel独立发起，他们确定了2色二部路径的拉姆齐数。最近，三色拉姆齐路径数和(偶数)循环也基本确定了。本文改进了DeBiasio, Gyarfas, Krueger, ruszynko和Sarkozy的结果，渐近地确定了四色路径和循环的二部Ramsey数。我们还提供了路径和循环的k色二部拉姆齐数的新的上界，这些上界接近于紧。

我们研究了在Wigner或Wishart标记模型中，在随机矩阵中种植一个单位范数稀疏主成分x∈ℝn的计算成本(观察W+λxx⊤，W来自高斯正交系集中，或n个独立样本来自(0,in +βxx⊤))。之前的工作表明，当信噪比(λ或βN/n)为一个小常数，且已植入的矢量中非零项的比例为‖x‖0/n=ρ时，如果ρ≲1/n√，则有可能在多项式时间内恢复x。虽然在较弱的条件下，ρ≪1有可能在指数时间内恢复x，但认为不可能在多项式时间内恢复，除非ρ≲1/n‾√。我们通过探索亚指数时间算法(即，对于某些常数δ∈(0,1)，在时间exp(nδ)中运行的算法)，来研究在“可能但困难”状态下恢复所需的精确时间量1/n之谜√ρ≪1。对于任何1/n‾√≪ρ≪1，我们给出了运行时间大致为exp(ρ2n)的恢复算法，展示了稀疏性和运行时间之间的平稳权衡。我们的算法家族在两个现有算法之间平滑地插值:多项式时间对角阈值算法和exp(ρn)时间穷极搜索算法。此外，通过分析低阶似然比，我们给出了严格的证据，表明我们的算法实现的权衡是最优的。

理论计算机科学中的各种关键问题可以表示为布尔超立方体上的多项式优化问题。证明这类问题的复杂性界限的一种特别成功的方法是基于平方和(SOS)作为非负性证明。在本文中，我们通过最近的一种称为非负电路多项式和(SONC)的替代证明来启动对布尔超立方体的优化。我们证明了基于SOS的证明的关键结果仍然有效:首先，对于具有d次约束的n-变量布尔超立方体上的非负多项式存在一个最多n+d次的SONC证明。其次，如果对于布尔超立方体上的非负多项式存在一个d次的SONC证明，那么也存在一个短的d次SONC证明，其中包含最多n^O(d)个非负电路多项式。最后，我们证明了SOS和SONC锥之间的某些差异:我们证明了，与SOS相比，SONC锥在对变量进行仿射变换时是不封闭的，并且对于SONC不存在与Putinar的Positivestellensatz等价的。我们从代数和优化的角度讨论了这些结果。

秘书问题因其在在线机制设计中的大量应用而成为最突出的在线选拔问题之一。任务是在给定的约束条件下选择元素的最大权重子集，其中元素以随机顺序一个接一个地到达，到达时显示权重。是否选择一个元素必须在它到达后立即做出决定。映射到秘书问题的不同应用要求处理不同的约束族。最突出的是类阵约束，它既能捕获许多相关设置，又能承认极具竞争力的秘书算法。然而，处理更多涉及的约束被证明是更加困难的，并且强大的算法只适用于少数特定的设置。在这篇论文中，我们提出了一个一般的框架来处理几个拟阵相交上的秘书问题。这个框架允许我们结合和利用文献中已知的最大的类阵秘书算法集。作为一个结果，我们在任意常数个数的拟阵的交集上得到了常竞争的拟阵秘书算法，其对应的(单)拟阵秘书问题目前已知具有常竞争的算法。此外，我们表明，我们的结果扩展到子模块目标。

许多现实生活中的规划问题需要在问题的所有参数被揭示之前做出先验决策。这类问题的一个重要特殊情况出现在调度和转运问题中，需要将一组作业分配给可用的机器或人员(资源)集，以一种所有作业都分配了资源的方式，并且没有两个作业共享相同的资源。在其名义形式下，由此产生的计算问题变成了分配问题。本文讨论了鲁棒分配问题(RAP)，它模拟了某些分配是脆弱的，并且在选择解决方案后可能变得不可用的情况。目标是选择最小代价的分配集合(对应的二部图中的边)，这样如果任何易受攻击的边变得不可用，解决方案的其余部分包含所有作业的分配。我们开发了RAP的算法和硬度结果，并从匹配理论、稳健优化、基于lp的技术及其组合中建立了一些与知名概念的联系。

分集最大化是信息检索、计算几何和运筹学中的一个重要概念。通常，它是以下问题的一种变体:给定一个基础集、约束和一个度量子集多样性的函数f，任务是选择一个可行的子集S，使f(S)最大化。和-分散函数f(S)是S中成对距离的和，在这种情况下是一个突出的多样化措施。相应的分集最大化是“max-sum”或“sum-sum”分集。在拟阵约束下，涉及和-色散函数的多样化问题的常因子近似算法设计得到了许多最新的研究成果。在这篇文章中，我们给出了在距离d(.，.)为负类型的矩阵约束下的最大和分集问题的一个PTAS。例如，负类型的距离是源于l2和l1规范的度量距离，以及余弦或球面距离，或Jaccard距离，这些都是web和图像搜索中流行的相似度量。我们的算法基于几何算法中开发的技术，如度量嵌入和凸优化。我们证明，我们可以计算一个分数解的通常非凸松弛的问题，它产生了最优整数解的上界。从这个分数解开始，我们采用确定性舍入方法，在目标方面只产生很小的损失，从而得到PTAS。 This technique can be applied to other previously studied variants of the max-sum dispersion function, including combinations of diversity with linear-score maximization, improving over the previous constant-factor approximation algorithms.

稳健优化是指在从解决方案中移除有限数量的资源时仍然可行的解决方案。迄今为止，大多数关于稳健组合优化的研究都假设每种资源都是同样脆弱的，并且场景集隐含地由单一预算约束给出。本文研究了另一种鲁棒性模型。我们关注的是最近引入的bulk -鲁棒性模型(Adjiashvili, Stiller, Zenklusen 2015)，该模型用于解决对系统中不均匀故障模式建模的需求。我们显著地扩展了Adjiashvili等人所使用的技术，以设计平面图中体积-鲁棒网络设计问题的逼近算法。我们的技术使用一个增强框架，结合线性规划(LP)舍入，依赖于输入图的平面嵌入。建立了圆图中切割覆盖问题与支配集问题的联系。我们的方法很少使用批量鲁棒优化的细节，因此可以想象，它们可以适用于解决其他鲁棒网络设计问题。

给定n维频率向量f的流，我们用n、精度和向量f的l1长度来描述近似频率负矩Fp所必需的空间，其中p<0。为了实现这一点，我们实际上证明了一个更一般的结果。给定任何非负的非递增函数g，我们描述了任何流算法输出(1 +/- eps)近似到g变换的向量f的坐标的和所需要的空间。所需的存储以一个相对简单的非线性优化问题的解的形式表示，并且该算法适用于(1 +/- eps)近似到任何这样的和，其中应用函数是非负的，非递增的，并且具有与g相同或更小的空间复杂性。这部分回答了Nelson的一个悬而未决的问题(IITK Workshop Kanpur, 2009)。

稠密图的极限的概念被发明出来，其中一个原因是为了解决极值图论中的问题。用图的极限来定义阶型的极限是很简单的，本文讨论了如何适应这种设定，研究稠密图极限的两种方法。我们首先考虑标志代数，它被用来打开图上的各种问题，通过半定规划进行机械求解。我们定义了阶型的标志代数，并利用它们通过半定方法得到了任意点集中凸位置的5元组或6元组密度的新下界，以及表示阶型均匀抽样难度的一些不等式。我们接下来考虑图元，稠密图的极限的表示，使他们能够通过连续概率或分析方法进行研究。我们研究平面测度如何作为阶类型极限的图元的候选类似物。我们证明了将测度发送到其相关极限的映射是连续的，如果限制在紧凸集上的一致测度，则映射是同胚的。然而，我们证明这张图不是满射的。最后，我们研究了与组合几何中的经典结构(Erdos-Szekeres, Horton…)相似的阶型的极限，并表明它不能用任何正则测度来表示;我们通过类似于Sylvester关于k个随机点处于凸位置的概率问题来分析这个例子。

我们介绍了具有各种应用的包装问题的时间扩展版本的一般模型。我们以两种自然变化的方式引入了时间扩展封装的概念，它要求元素在几个连续的时间步骤中成为解决方案的一部分。尽管事实上，大多数组合优化问题的时间扩展对应物在计算上变得难以解决，但我们根据所考虑的变量，分别为一般依赖系统和拟阵提出了强近似算法。更准确地说，对于我们介绍的两种时间扩展封装的概念，我们获得的近似保证最多是一个小的常数因子，比非时间扩展版本的潜在问题的最佳近似算法更差。

我们研究了有界度图Δ = O(1)的邻接标记方案。特别地，我们提出了有界度树的最优(到一个附加常数)logn + O(1)邻接标记方案。后一种格式源自有界度外平面的标记格式。我们的结果补充了最近获得的有界深度树的类似边界[Fraigniaud和Korman, SODA 2010]，并可能为弥合树木中长期存在的相邻差距提供新的见解[Alstrup和Rauhe, FOCS 2002]。我们还提供了有界度平面的改进标记方案。最后，我们利用组合数系统提出了一种改进的邻接标记方案，用于具有\((e+1)\√{n} < \Delta \leq n/5\)的有界度图Δ。

在这项工作中，我们得到了非线性函数的凸包络的显式描述，它在变量的一个子集上是分量上凹的，而在其他变量上是凸的。这些函数占公共基准库中所有非线性函数的30%以上。为了克服由函数的分量凹部分给出的凸包络描述的组合困难，我们考虑了一个基于Sherali和Adams (SIAM J离散数学3(3):411 - 430,1990)引入的重拟-线性化技术的凸包络的扩展公式。计算结果表明，扩展公式策略是全局优化的有效工具。

，表示两个相邻节点不能属于一个稳定集的简单条件。我们研究了分数稳定集多面体，即由边的线性松弛式定义的多面体。即使该多面体是稳定集多面体的弱近似，其简单的几何结构提供了深刻的理论见解以及有趣的算法机会。利用基的图形特征，我们首先根据简单的图形操作重新定义枢轴，将给定的基转换为相邻的基。这些结果使我们证明了分数稳定集多面体的组合直径最多等于给定图的节点数。作为推论，赫希界适用于这类多面体。

给定一个有h个面，其内部不包含积分点的多面体L和一个多面体P，最近的整数规划工作集中在刻画P的凸包减去L的内部。我们表明，要得到这样的刻画，充分考虑定义P的不等式中P的所有至多为n(h−1)的松弛。这扩展了Andersen, Cornuéjols和Li的结果。

我们提出了一种全对最短路径算法，其在n个顶点上的完全有向图上的运行时间为O(n2)，这些顶点的边权是从[0,1]开始独立均匀随机选择的，且具有期望和高概率。这解决了一个长期悬而未决的问题。该算法是Demetrescu和Italiano[2006]的动态全对最短路径算法的变体。该分析依赖于这样的随机加权图中局部最短路径的数量为O(n2)，在期望中且具有高概率的证明。我们还提出了一个动态版本的算法，在O(log2n)的预期时间内随机边缘更新后重新计算所有最短路径。

细胞信号网络的逻辑模型最近引起了广泛的兴趣:它们能够在不同的生物水平上整合定性信息，从受体-配体相互作用到基因调控网络，这对于理解复杂的信号行为是至关重要的。我们提出了布尔建模范式的概述，并详细讨论了一种基于因果逻辑交互的方法，该方法产生描述性和预测性信号网络模型。我们的方法提供了一个数学上定义良好的概念，提高了分析工具的效率，以满足大规模数据集的需求，并且可以扩展到各个方向，包括定时信息以及组件的多个离散值。

化学突触是高度特化的细胞-细胞接触，用于中枢神经系统中神经元之间的通信，其特征是突触膜上复杂而动态的蛋白质网络。活跃区(CAZ)的细胞突组织装置调节突触前递质的释放。在突触后端，突触后密度构成了检测、整合和传递信号转导的机制。突触前和突触后的蛋白质网络都是突触可塑性的分子基质。它们的功能可以通过调节其组成和对其成分的翻译后修饰来改变。为了全面了解突触网络，必须考虑整个突触蛋白集合。为了支持这一点，我们建立了一个综合的突触连接蛋白数据库(SynProt数据库)，主要基于从抗洗涤剂突触连接生化制剂中获得的蛋白质组学数据。该数据库目前包含2788个非冗余的大鼠、小鼠和一些人类蛋白质条目，这些蛋白质主要是从12个蛋白质组学研究中手工提取的，并注释了突触亚细胞定位。每个数据集都包括手动添加的信息，包括蛋白质分类器，以及从公共数据库(UniProt和PubMed)自动检索和更新的信息。我们希望该数据库将被用于支持突触蛋白网络的建模和合理的实验设计。

T细胞协调适应性免疫反应，使它们成为免疫治疗的目标。虽然免疫抑制疗法可以防止疾病进展，但也会使患者容易受到机会性感染。为了确定新的药物靶点，我们建立了一个描述t细胞受体(TCR)信号的逻辑模型。然而，为了有一个能够预测新的治疗方法的模型，当前的药物靶点必须包括在内。因此，下一步我们生成了白细胞介素-2受体(IL-2R)信号网络，并开发了一种合并逻辑模型的工具。对于IL-2R信号，我们发现STAT激活独立于Src-和pi3激酶，而ERK激活依赖于这两种激酶，并且还需要新的pkc。此外，我们的合并模型正确地预测了tcr诱导的STAT激活。结合的网络还允许信息从一个受体转移到另一个受体，从而预测LAT在IL-2R信号通路中介导JNK激活。总之，合并模型不仅使我们能够解开潜在的串扰，而且还提出了新的实验设计，并为设计策略重编程T细胞提供了关键的一步。

对于生物和细胞过程的研究，数学建模和分析已经成为实验研究的重要补充。然而，这些过程的结构和定量知识通常是有限的，测量经常受到固有的和可能很大的不确定性的影响。这导致相互竞争的模型假设，其动力学参数可能无法通过实验确定。区分这些备选方案并估计其动力学参数对于提高对所考虑的过程的理解至关重要，并从手头的分析工具中受益。在这项工作中，我们提出了一个基于集合的框架，允许区分相互竞争的模型假设，并提供与(可能稀疏和不确定的)实验测量一致的模型参数的有保证的外部估计。这是通过利用生物化学反应网络的多项式/合理结构的模型无效的精确证明来获得的，并通过使用有效的策略来平衡求解精度和计算工作量。两个案例研究说明了我们方法的实用性。第一项研究表明，我们的方法可以最终排除错误的模型假设。第二项研究着重于参数估计，并表明所提出的方法允许评估测量稀疏性，不确定性和先验知识对参数估计的整体影响。这有助于设计进一步的实验，从而改进参数估计。