离散数学研究快报
用 AI 跟踪日新月异的离散数学领域进展
计算机辅助图论：综述
计算机和算法在图论中获得新结果方面发挥着日益重要的作用。在本综述中，我们介绍了计算机辅助图论中使用的广泛技术，包括在给定类别内详尽生成所有两两非同构图、使用包含图和不变量的可搜索数据库以及其他已建立和新兴的算法范式。我们涵盖了基于混合整数线性规划、半定规划、动态规划、SAT求解、元启发式和机器学习的方法。这些技术通过涵盖图论多个重要子领域的详细结果进行说明，如极值图论、图着色、结构图论、谱图论、正则图、拓扑图论、图中的特殊集合、代数图论和化学图论。我们还展示了一些较小的新结果，这些结果证明了在开发出适当工具后，计算机辅助图论方法可以多么容易地应用。
倾斜的生长形式
瓷砖的生长形式(或日冕极限)是其协调壳的极限形式,即其位于与一些瓷砖的固定距离的一组瓷砖。 我们概述了当前的结果,关于增长形式的猜想和开放问题,包括周期性,多网格,替换和帽子瓷砖。
关于Grundy支配和Zero Forcing问题的参数化复杂度
我们考虑处理图中支配问题的两个不同问题族。一方面，我们关注支配序列。在这样的序列中，每个顶点支配图中某个未被序列中任何先前顶点支配的顶点。寻找最长支配序列的问题被称为𝖦𝗋𝗎𝗇𝖽𝗒 𝖣𝗈𝗆𝗂𝗇𝖺𝗍𝗂𝗈𝗇。根据使用闭邻域还是开邻域进行支配，该问题还有另外三个版本。我们证明，当以解的大小为参数时，所有四个问题变体都是𝖶[1]-难的。另一方面，我们考虑Zero Forcing问题族，它们构成了Grundy支配问题的参数化对偶。在这些问题中，我们寻找最小的初始着蓝色的顶点集合，使得某些颜色变化规则能够将所有其他顶点着蓝色。Bhyravarapu等人[IWOCA 2025]表明，其中一个称为𝖹𝖾𝗋𝗈 𝖥𝗈𝗋𝖼𝗂𝗇𝗀 𝖲𝖾𝗍的问题，在以树宽或解的大小为参数时属于𝖥𝖯𝖳。我们将他们的树宽结果扩展到其他三个Zero Forcing变体及其各自的Grundy支配问题。我们的算法还意味着，当以不在支配序列中的顶点数量为参数时，𝖦𝗋𝗎𝗇𝖽𝗒 𝖣𝗈𝗆𝗂𝗇𝖺𝗍𝗂𝗈𝗇存在𝖥𝖯𝖳算法。
奇异值与定向和无导向图形中的扩展
我们把欧勒联定向图的标准化邻接矩阵的非平凡的奇异值 σ_2,...,σ_n 关联到图扩展的组合度量: 1. 我们引入了一个新的定向电导率 φ_dir 的模拟,并证明了一个类似 Cheeger 的不等式,表明 φ_dir 被绑定到 0 iff σ_2 之外。 在无方向图中,这可被视为标准Cheeger Inequality和Trevisan的Cheeger Inequality的统一,以获得最小的特征值。 2. 我们证明了高阶 Cheeger 不平等的奇数值类似物,给出了 σ_k 脱离 1 时的组合表征。 3. 我们收紧了σ_2和顶点扩展之间的关系,证明如果一个d-regular图G与属性的所有设置S的大小在最多n/2有至少(1+δ)·|S|外邻,那么1-σ_2=Ω(δ^2/d)。 这种约束是紧密的,并且节省了先前已知的关系的一个因子。
大型平衡独立套装的锐利在线硬度
我们研究在密集的随机双体图中找到大γ平衡独立集合的算法问题;如果其顶点的γ比例位于双分区的一侧,则独立集合是γ平衡的。 在稀疏的系统中,Perkins和Wang在低度多项式(LDP)框架中建立了紧密界限,通过为稳定算法量身定制的重叠差距Gap Property(OGP)框架显示了因子1/(1-γ)统计计算差距。 然而,这些技术似乎并没有延伸到密集的设置。 对于密集的随机图中相关的大型独立集合问题,最著名的算法是一个天生不稳定的在线贪婪程序,即使在贪婪成功的“简单”制度中,LDP算法也会被推测失败。 我们表明,在密集的随机双方图中最大的γ平衡独立集合具有大小 α:=log_b n/γ(1-γ) whp,其中n是每个双分区的大小,p是边缘概率,b=1/(1-p)。 我们设计了一个在线算法,可以为任何 ε>0 实现(1-ε)1-γ)α whp。 我们用尖锐的下界来补充这一点,表明没有在线算法能够以不可忽略的概率实现(1+ε)(1-γ)α。 我们的研究结果表明,在密集的环境中也存在相同的因子-1/(1-γ)间隙,支持其推测的普遍性。 虽然G(n,p)上的经典贪婪程序很简单,但我们的算法更加复杂:它分为两个阶段,包括停止时间和适当的截断,以确保γ平衡 - 一个全局约束 - 尽管操作信息有限。 我们的下界使用OGP框架;我们基于最近对在线模型框架的改进,并将其扩展到双部分设置。
相关分类
最新研究
𝐖_p 图独立多项式的对数凹性
令G为n阶图。对于正整数p，如果n≥p且G的任意p个两两不相交的独立集都包含在p个两两不相交的最大独立集中，则称G为𝐖_p图。本文中，我们证明每个连通的𝐖_p图G是p-拟可正则化的当且仅当n≥(p+1)·α，其中α是G的独立数且p≠2。这一发现确保了当(p+1)·α≤n≤p·α+2√(p·α+p)且α²/4(α+1)≤p，或p·α+2√(p·α+p)<n≤(α²+1)·p+(α-1)²/α-1且α(α-1)/α+1≤p时，连通𝐖_p图G的独立多项式是对数凹的。此外，团冠图G∘K_p是𝐖_p图类的一个例子。我们进一步证明，对于足够大的p，G∘K_p的独立多项式总是对数凹的。关键词：极优覆盖图；拟可正则化图；冠图；𝐖_p图；独立多项式；对数凹性。
线性算子的下界
我们考虑在cell-probe模型下计算线性算子的静态数据结构问题。给定一个线性算子 M ∈ 𝔽_2^m × n，目标是将向量 X ∈ 𝔽_2^n 预处理成一个大小为 s 的数据结构，以在时间 t 内回答任何查询 ⟨ M_i , X ⟩。我们证明，对于一个随机算子 M，任何这样的数据结构需要满足：t ≥ Ω( min{ log(m/s) , n / log s } )。这一结果通过使用随机线性算子，克服了静态数据结构中著名的对数障碍 [MNSW98, Sie04, PD06, PTW08, Pat11, DGW19]。此外，它首次在确认一个数十年来的民间猜想方面取得显著进展：非线性预处理在计算大多数线性算子时没有实质性帮助。我们证明的一个直接修改还产生了对于深度-d 电路（具有任意门）计算特定线性算子 M ∈ 𝔽_2^O(n) × n 的线界下界 Ω(n · log^1/d(n))，即使相对于随机猜测只有小的常数优势。这一下界即使对于只有小常数优势的电路也成立，改进了长期以来的结果 [RS03, Che08a, Che08b, GHK+13] 对于一个随机算子。最后，我们的工作部分解决了 Multiphase Conjecture [Pat10] 的通信形式，并在 Jukna-Schnitger's Conjecture [JS11, Juk12] 上取得进展。我们通过考虑当查询数 m 是超多项式（例如，2^n^1/3）且总更新时间是 m^0.99 时的内积（模 2）问题（而不是集合不相交问题）来处理前者。我们对后者的结果也适用于具有超多项式 m 的情况。
约束排序
在这项工作中,我们研究广义排序问题,其中我们被赋予一组要排序的n个元素,但只允许所有可能的成对元素比较的子集。 我们从“禁止”对形成的图形的角度看待问题,我们使用这个图的斜数和色度数对算法进行参数化。 我们还将这些结果扩展到输入图不一定可排序的问题类别,并且只对发现部分顺序感兴趣。 我们使用我们的结果来开发一个简单的算法,该算法始终确定 O(n^3/2log n) 探针中的潜在部分顺序,当输入图是 Erdős-Rényi 图时。
Z^2中数字图片的同源性
我们研究数字同源在数字图片(X,κ,κ̅)上下文中的属性,其中X⊊Z^n是一个有限集,κ是X上的相邻关系,是X的补充 κ̅ 的相邻关系。 特别是,我们专注于Z^2中数字图片之间的同源等效性。 我们为 Z^2 的数字图片定义了一个数值同源类型不变,称为外周,这是区分数字图片类型的基本工具。 当数字图片没有孔时,我们显示它是同源的,相当于它的rc-convex船体,通过“填补任何行或列的空白”来获得。 我们表明,数字图片(X,c_i,c_j)仅相当于有限的许多其他数字图片(Y,c_i,c_j)。 在论文的结尾,我们在数字图片的行列凸轮上提出了一个猜想。
非字格的线条图并不总是非字可字的
图形据说是单词表示,如果在其顶点上存在一个单词,那么任何两个顶点都是相邻的,只有当它们在这个单词中交替时。 如果没有这样的词,该图是不可字表示的。 在文献中,有非字代表图的例子,其线图是不可字表示的。 然而,确定非字表示图的线图是否总是非字表示不成文的,这是一个开放性的问题? 在这项工作中,我们通过考虑一类非字表示图来解决开放性问题,即Mycielski长度至少为5的奇数周期图,并显示它们的线图是可字表示的。
Row 公正 终点
我们介绍了Row Impartial Terminus(RIT),这是一个在整数分区上玩的公正组合游戏。 我们表明,RIT中的任何位置都可以独特地分解成核心和残余。 我们的核心结果是,任何RIT位置的Conway对 - 在正常和misère play下确定结果 - 与由残余物定义的Nim游戏中的Conway对相同位置相同。 这一发现为RIT的两种变体提供了完整的获胜策略,将其分析减少到了Nim的很好理解的框架。 因此,我们在Conway-Gurvich-Ho层次结构中分类RIT,显示它是被迫和悲惨的,但不是宠物。
KKL定理对一组变量的影响
考虑 n 维度超立方上的布尔函数 f,以及一组变量(索引) S ⊂{1,2,...,n}。 变量 S 对函数 f 的联盟影响是,在随机分配不在 S 中的变量后,f 的值未确定的概率。 在本文中,我们研究了一个互补的概念,我们称之为联合影响:在随机分配不在S中的变量后,f的值取决于S中的所有变量的概率。 我们表明,对于任意固定的 d, n 变量上的每一个 Boolean 函数 f 都承认一个 d 组的联合影响至少 110 W^≥ d(f)(log n/n)^d,其中 W^≥ d(f) 是 f 的傅里叶重量至少 d。 这个结果是Kahn-Kalai-Linial定理的直接概括。 此外,我们举一个例子,展示了上述界限的基本清晰度。 在我们研究联合影响时,我们考虑了Tal最近引入的另一种多位影响的概念。
字表示共反图形的表示数
图 G = (V, E) 是表示的,如果在字母表 V 上存在一个字 w,那么对于任何两个不同的字母 x, y ∈ V,字母 x 和 y 在 w 中交替,如果 xy ∈ E 。 图形是共二联的,如果它的补充是双方的。 因此,共体图形的顶点集可以分为两个不连接的子集X和Y,以便X和Y诱导的子图是斜体。 图形类的单词可表示的概念近年来得到了极大的关注。 谢尔盖·基塔耶夫(Sergey Kitaev)和瓦迪姆·洛津(Vadim Lozin)的《文字与图形》(Words and Graphs)一书展示了不代表文字的共同双份图的例子。 众所周知,如果图形承认半瞬态取向,则具有字表示。 虽然已经建立了在共体图形中存在半瞬态取向的必要和充分条件,但基于顶点排序的表征仍然开放。 在本文中,我们提出了必要和足够的条件,使一个共体图在其顶点排序方面具有字表示。 此外,基于这个顶点排序,我们提供了一个算法来构建一个3个均匀的单词表示,用于任何可表示的共体图形。 使用此结果,我们证明除了排列图外,所有其他可表示的共聚图的表示数为3。
图论中的硬核模型
一个独立的集合可能不包含一个顶点和它的一个邻居。 这个基本事实使得独立集合的均匀分布相当特别。 我们考虑的是硬核模型,这是统一分布对独立集合的基本概括。 我们展示了其本地分析如何对主机图中独立集合的全球结构产生显着的见解,例如,Ramsey数字,图形着色和球体包装。
填写不完整的配对比较矩阵的图案设计:(准)直径最小的规则图形
多标准决策问题对个人和群体都很重要。 配对比较在偏好建模和量化的理论和实践中已经流行起来。 我们专注于决策问题,其中可以选择成对比较的集合,即不先验。 本文的目标是根据其图形表示,为填写不完整的成对比较矩阵(PCM)的模式提供建议。 规律性意味着每个项目以相同的次数与其他项目进行比较,从而产生一种对称性。 奇数顶点上的图形称为准正则,如果每个顶点的度数相同,则每个顶点的度数都相同,但一个顶点的度比较大的一个。 如果有一对项目,使得它们的最短连接路径很长,那么这两个项之间的比较依赖于许多中间比较,并且可能因其所有错误而存在偏差。 以前发现过这样的例子,其中乒乓球运动员比赛产生的图表包括两个顶点(球员)之间的一条长最短的路径,计算的结果似乎具有误导性。 如果比较图的直径尽可能低(在相同边缘数的图形中),我们可以避免,或者至少减少这样的累积误差。 我们研究的目的是在常规和准常规的图形中寻找直径最小的图形。 理论家和从业者都可以使用附录中几种格式的结果:图形,相邻矩阵,边缘列表。
差距平面图的扩展
图形是k-gap-planar,如果它在平面上有一张图纸,这样每个过境点都可以充电到涉及的两个边缘之一,以便大多数k个交叉口都向每个边缘充电。 我们展示了这类图形具有线性扩展。 特别是,k-gap-planar 图的每个 r-shallow 都有密度 O(rk)。 证明这一结果的几个扩展:对于拓扑未成年人,对于k-cover-planar图形,对于k-gap-cover-planar图形,对于任何表面上的图纸。 介绍了图形着色的应用。
On 支持多目标组合优化
本文讨论了在多目标组合问题(MOCO)中支持的非主导点的各种定义不一致。 众所周知,MOCO问题包含受支持且不支持的非主导点,后者通常超过前者。 支持的点,一般来说,更容易确定,可以作为表示,并用于两阶段的方法来生成整个非主导点集。 尽管它们很重要,但在文献中使用了几种不同的特征来支持有效的解决方案(和支持的非主导点)。 虽然这些定义相当于多目标线性问题,但它们可以为MOCO问题产生不同的支持非主导点。 我们以一个例子表明,这些定义对于MOCO或一般多目标优化问题并不等同。 此外,我们分析了生成的一组支持的非主导点的结构和计算属性。 这些考虑促使我们总结支持的有效解决方案的等效定义和特征,并区分受支持的有效解决方案和弱支持的有效解决方案。
现实世界大图上的1中位数问题的快速近似算法
无定向加权图上的1中位数问题(1MP)旨在找到一个设施位置,最大限度地减少与所有客户节点的总加权距离。 虽然1MP可以通过计算每个客户节点的单源最短路径来准确解决,但在具有数百万个节点的大型图形上,这种方法在计算上变得昂贵。 在许多现实世界的应用中,例如基于大规模知识图谱的推荐系统,节点的数量(即潜在的设施位置)是巨大的,而客户节点的数量相对较小,在空间上集中。 在这种情况下,详尽的图形探索不仅效率低下,而且没有必要。 利用这一观察,我们提出了三种近似算法,通过早期终止Dijkstra的算法来减少计算。 我们提供理论分析,表明其中一个算法保证近似比为2,而另外两个算法将这个比率提高到1.618。 我们通过呈现特定实例证明近似比的下限为1.2。 此外,我们表明,当客户节点数量小于或等于三个时,所有提出的算法都会返回最优解决方案。 广泛的实验表明,我们的算法在运行时显著优于基线精确方法,同时在所有测试的图形类型中保持近乎最佳的准确性。 值得注意的是,在拥有1000万个节点的网格图上,我们的算法在1毫秒内获得所有最佳解决方案,而基线精确方法平均需要超过70秒。
具有加性偏差的构造性 l2-差异最小化
ℓ_2 范数中的符号序列问题询问，给定一组向量 v_1,…,v_n∈𝐑^d，其 ℓ_2 范数至多为单位范数，是否总是存在一个 ±1 符号的序列 (ε_i)_i∈ [n]，使得对于所有 i∈ [n]，max_i∈ [n]∑_j=1^i ε_i v_i_2 = O(√(d))。Banaszczyk [2012, Rand. Struct. Alg.] 的结果表明，存在符号 ε_i∈{-1,1}, i∈ [n]，使得 max_i∈ [n]∑_j=1^i ε_i v_i_2 = O(√(d+log n))。目前已知的最佳构造性界限是 O(√(dlog n))，由 Bansal and Garg [2017, STOC., 2019, SIAM J. Comput.] 给出。我们提出一个多项式时间随机化算法来找到符号 x(i) ∈{-1,1}, i∈ [n]，使得 max_i∈ [n]∑_j=1^i x(i)v_i_2 = O(√(d + log^2 n)) = O(√(d)+log n)。通过 Harvey and Samadi [COLT, 2014] 的构造性约简，这也为 ℓ_2 范数中的 Steinitz 问题产生了一个 O(√(d)+log n) 的构造性界限。因此，当 d ≥log^2n 时，我们的结果解决了这两个猜想。我们的算法基于 Bansal and Garg 的框架，并结合了一个新的分析，涉及 (i) 在构建随机游走步骤的协方差矩阵期间添加线性和谱正交约束，这允许我们控制差异增量向量的线性以及二次分量的二次变分，以及 (ii) 一个“Freedman-like”版本的 Hanson-Wright 集中不等式，用于过滤依赖的子高斯混沌和。
𝐑^d中具有递增弦的弧
一条连接s和t的曲线γ具有递增弦性质，如果当a、b、c、d按顺序位于γ上时，满足|bc| ≤ |ad|。对于平面曲线，已知此类曲线的长度最多为2π/3 · |st|。本文从算法角度研究更高维度中的这一问题，并展示以下结果：(I) 在𝐑^d中，对于每个d ≥ 3，任何具有递增弦的s-t曲线的长度最多为2 ·( e/2 · (d+4) )^d-1· |st|。这是更高维度中的第一个界限。(II) 给定𝐑^d中的一个多边形链P=(p_1, p_2, …, p_n)，其中d ≥ 4，k =⌊ d/2 ⌋，可以在O(n^2-1/(k+1) polylog (n) )期望时间内测试其是否满足递增弦性质。这是更高维度中的第一个次二次算法。
Ferber-Krivelevich和Gallai定理在诱导子图中均等的学位均等
一个长期和众所周知的猜想(见例如: Caro, Discrete Math, 1994)指出,每个没有孤立顶点的n-vertex图G都包含一个引子图,其中所有顶点都有奇度,其顺序在n中是线性的。 Ferber 和 Krivelevich (Adv 。 数学,2022年)证实了这一猜想。 在本短文中,我们通过考虑标记为0或1的顶点的G来概括这一结果,并要求在G的诱导子图中,0标记的顶点是均匀度的,1标记的顶点是奇度的。 我们证明,如果 G 没有孤立的顶点,它包含 n 中这样的顺序线性的子图。 著名的加莱定理指出,每个图的顶点可以分为两个部分,使得两个部分诱导的子图中的所有顶点都有均匀度。 如果我们要求其中一个引子图中所有顶点的度是偶数,另一个引子图中所有顶点的度数也是奇数,那么结果也成立。 加莱定理的自然概括为digraphs的超度不成立,我们表征了它确实持有的所有digraphs。 我们的表征是线性代数。
树木分解,宽度小,分布,顺序和程度
图形的树分解在结构和算法图论中具有根本的重要性。 tree-decompositions的主要属性是宽度(一个袋子-1的最大大小)。 我们显示每个图形都有树分解,宽度接近最佳,加上几个额外的属性。 特别是每个树宽最多k的图形G都有树分解,宽度最多为72k+1,其中每个顶点v出现在大多数deg_G(v)+1袋中,袋的数量最多 max{|V(G)|/2k,1},并且分解的树索引最多12个。 这在丁和奥波罗夫斯基[1995]的结果中提高了线性的指数边界,并在强烈的意义上建立了他们的猜想。
高长和有边界度的弦乐图形障碍
字符串图是平面曲线的交叉图。 Kratochvíl之前展示了无限多的障碍:不是字符串图形的图形,但任何边缘收缩或顶点删除都会产生字符串图形。 Kratochvíl的障碍包含任意大集团,因此它们具有三级和无界度。 我们通过研究限制腰围和/或学位图之间的障碍来扩展这一行工作。 我们构建了一个无限大的障碍家族;此外,我们的构造是无K_2,3子图和近平面(平面加一个边缘)。 此外,我们证明有子咪咪三的子咀嚼障碍,并且没有高腰的亚立方障碍。 我们将子咀嚼字符串图描述为具有匹配,其收缩产生平面图,并且基于此表征,我们找到了用于识别边界树幅子崎弦图的线性时间算法。
属于每个最小定位支配代码的顶点新结果
自20世纪80年代斯莱特和拉尔引入定位主导代码以来,已经进行了广泛的研究。 在本文中,我们专注于必须属于图形中所有最小定位占主导地位的顶点。 我们称他们为min-forced顶点。 我们显示,连接的顺序 n 的不平凡图中的 min-forced 顶点数由 2/3(n -γ^LD(G)) 限制在上面,其中 γ^LD(G) 表示最小定位占域代码的基数。 这意味着最小强制顶点数与连接的非平凡图的顺序之间的最大比率最多为2/5。 而且,这两个界限都可以达到。 我们还确定所有路径中不同最小定位占主导地位代码的数量。 此外,我们表明,决定顶点是否为min-forced是共同NP-hard。
基于距离(和基于路径)的覆盖给定环流数图形的问题
我们研究了一个覆盖问题的大家族图形,其定义依赖于距离,用于边界环流数的图形(即需要从图形中删除以破坏所有周期的最小边缘数)。 这些问题包括(但不限于)三个问题家族:(i)度量维度的变体,其中人们想要选择图形的一个小集S顶点,以便每个顶点都由其有序的距离向量到S的顶点决定;(ii)大地测量组的变体,其中想要选择一个小的一组顶点,以便任何顶点位于两个顶点之间的一个最短路径。属于其中一条路。 我们概括和/或改进该区域先前的结果,这些结果表明,这些问题的最佳值可以通过环流数的线性函数和图的1度垂直。 为此,我们开发并增强了最近在[C.中引入的技术。 卢, Q 。 叶,C。 朱。 算法方面在最小(加权)双倍解决图集设置问题,Journal of Combinatorial Optimization 44:2029-2039,2022],并在几种情况下给出近乎最优的界限。 这解决了(在某些情况下完全,在某些情况下部分)一些猜想和开放的问题从文献。 该方法基于广度优先搜索,具有算法性质,因此可以在线性时间计算所有结构。 我们的结果也意味着计算最优解决方案的算法结果:对于一些问题,它们可以在有界环相数的图形的多项式时间计算。