如果一个三维凸体的副本可以通过该体内的直孔，则称其具有鲁珀特性。在这项工作中，我们构造了一个可证明不是鲁珀特的多面体，从而反驳了2017年的一个猜想。我们还发现了一个是鲁珀特但不是局部鲁珀特的多面体。
计算机和算法在图论中获得新结果方面发挥着日益重要的作用。在本综述中，我们介绍了计算机辅助图论中使用的广泛技术，包括在给定类别内详尽生成所有两两非同构图、使用包含图和不变量的可搜索数据库以及其他已建立和新兴的算法范式。我们涵盖了基于混合整数线性规划、半定规划、动态规划、SAT求解、元启发式和机器学习的方法。这些技术通过涵盖图论多个重要子领域的详细结果进行说明，如极值图论、图着色、结构图论、谱图论、正则图、拓扑图论、图中的特殊集合、代数图论和化学图论。我们还展示了一些较小的新结果，这些结果证明了在开发出适当工具后，计算机辅助图论方法可以多么容易地应用。
我们考虑处理图中支配问题的两个不同问题族。一方面，我们关注支配序列。在这样的序列中，每个顶点支配图中某个未被序列中任何先前顶点支配的顶点。寻找最长支配序列的问题被称为𝖦𝗋𝗎𝗇𝖽𝗒 𝖣𝗈𝗆𝗂𝗇𝖺𝗍𝗂𝗈𝗇。根据使用闭邻域还是开邻域进行支配，该问题还有另外三个版本。我们证明，当以解的大小为参数时，所有四个问题变体都是𝖶[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)。 这种约束是紧密的,并且节省了先前已知的关系的一个因子。
一条连接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) )期望时间内测试其是否满足递增弦性质。这是更高维度中的第一个次二次算法。
字符串图是平面曲线的交叉图。 Kratochvíl之前展示了无限多的障碍:不是字符串图形的图形,但任何边缘收缩或顶点删除都会产生字符串图形。 Kratochvíl的障碍包含任意大集团,因此它们具有三级和无界度。 我们通过研究限制腰围和/或学位图之间的障碍来扩展这一行工作。 我们构建了一个无限大的障碍家族;此外,我们的构造是无K_2,3子图和近平面(平面加一个边缘)。 此外,我们证明有子咪咪三的子咀嚼障碍,并且没有高腰的亚立方障碍。 我们将子咀嚼字符串图描述为具有匹配,其收缩产生平面图,并且基于此表征,我们找到了用于识别边界树幅子崎弦图的线性时间算法。
我们研究了一个覆盖问题的大家族图形,其定义依赖于距离,用于边界环流数的图形(即需要从图形中删除以破坏所有周期的最小边缘数)。 这些问题包括(但不限于)三个问题家族:(i)度量维度的变体,其中人们想要选择图形的一个小集S顶点,以便每个顶点都由其有序的距离向量到S的顶点决定;(ii)大地测量组的变体,其中想要选择一个小的一组顶点,以便任何顶点位于两个顶点之间的一个最短路径。属于其中一条路。 我们概括和/或改进该区域先前的结果,这些结果表明,这些问题的最佳值可以通过环流数的线性函数和图的1度垂直。 为此,我们开发并增强了最近在[C.中引入的技术。 卢, Q 。 叶,C。 朱。 算法方面在最小(加权)双倍解决图集设置问题,Journal of Combinatorial Optimization 44:2029-2039,2022],并在几种情况下给出近乎最优的界限。 这解决了(在某些情况下完全,在某些情况下部分)一些猜想和开放的问题从文献。 该方法基于广度优先搜索,具有算法性质,因此可以在线性时间计算所有结构。 我们的结果也意味着计算最优解决方案的算法结果:对于一些问题,它们可以在有界环相数的图形的多项式时间计算。
遗传图类的k-Coloring问题在过去十年中一直是一个深入研究的问题。 遗传图类的特点是(可能是无限)最小禁止诱导子图列表。 我们说一个图形是 (H_1,H_2,...)- 免费的,如果它不包含任何 H_1,H_2,... 作为诱导子图。 即使限制由少数禁止诱导子图定义的病例 k=4 和类,问题的复杂性情况仍然不清楚。 虽然最近只有一个禁止诱导子图的案例已经完全解决了,但考虑两个禁止诱导子图时的复杂性仍然有几个未知的案例。 特别是,4-Coloring on (P_6,C_3)-free graphs 是多项式,而它是 NP-hard on (P_22,C_3)-free 图形。 我们提供减少显示19≤ t≤ 21的4-Coloring(P_t,C_3)-free图形的NP完整性,从而缩小了复杂性仍然未知的案例的差距。 我们的证明包括计算机搜索,确保通过减少获得的图形家族确实不含P_19。
考虑为随机到达(X_i)_i ∈ [T],其中时间视界满足T = Θ(n),X_i是i.i.d uniform d-sparse n-dimensional binary vectors,有2≤ d ≤ (loglog n)^2/loglogn n。 我们表明,对于这个参数范围,每个在线算法都会产生至少Ω(loglog n)的差异,并且有一个高效的算法实现了O(loglog n) w.h.p的匹配差异边界。 这在平均案例Beck-Fiala问题的线上和线下版本之间建立了存在和算法的渐近差距。 引人注目的是,在考虑的设置中,最佳的在线差异是顺序日志 n,独立于 d 和向量 (X_i)_i 的规范。 我们对d的假设几乎是最优的,因为当d=ω((loglog n)^2)时,这种独立性就会停止。
我们的工作应用强化学习来构建有关图的拉普拉斯矩阵光谱半径的猜想边界的反例。 我们扩展了Stevanovic等人重新实施Wagner的方法,能够同时训练众多独特的模型,并对动作空间进行新的重新定义,以调整当前局部最佳对学习过程的影响。
本文显示,在高概率的情况下,随机在多项式大小的字段上戳破的Reed-Solomon代码实现了列表解码能力。 更具体地说,我们证明,对于任何 ε>0 和 R∈ (0,1),具有高概率,随机刺破的块长度 n 和速率 R 的 Reed-Solomon 代码是 (1-R-ε, O(1/ε)) 列表可破,超过至少 2^poly(1/ε)n^2 的大小字母。 这扩展了Brakensiek,Gopi和Makam(STOC 2023)最近的突破,这些突破随机刺破Reed-Solomon代码在指数大小的领域达到了Shangguan和Tamo(STOC 2020)的广义Singleton绑定。
一个长期和众所周知的猜想(见例如: 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]的结果中提高了线性的指数边界,并在强烈的意义上建立了他们的猜想。
我们使用新颖的分解来创建简洁的数据结构 - 在恒定时间支持静态树的广泛操作 - 用于各种树类,扩展了Munro,Nicholson,Benkner和Wild的结果。 在AVL树类的激励下,我们进一步导出信息-理论下界对存储树类所需的位数的渐近,这些树类的生成函数满足某些功能方程。 特别是,我们证明AVL树每个节点需要大约0.938位才能编码。
对于一组有限锦标赛的F,无F方向问题是决定给定的有限无方向图是否可以以这样的方式进行定向的问题,即生成的定向图不包含F的任何成员。 使用平滑近似理论,我们给出了一个新的较短的证明,为Bodirsky和Guzmán-Pro最近获得的此类问题的复杂性二分法。 事实上,我们的方法为相当大类的计算问题产生了复杂性二分法,其中给定了一个无方向图以及允许方向的额外局部约束。 此外,可处理和硬问题之间的边界也由可判定的代数条件描述。
影响基是闭包空间及其闭合格子的著名代表。 不过,这种表示并不是独一无二的,并且闭包空间通常允许多个碱基。 其中,规范基础,规范直接基础以及D基因其结构和算法特性而引起了大量关注。 最近,从自由格图的研究中出现了一个新的基础:E-base。 它是对D基的改进,与前面提到的暗示基础不同,并不总是准确地代表其相关的闭合空间。 这就引出了一个有趣的问题:对于哪些类别的(闭包)格子有有效的E-base? 低边界的格子已知形成这样的类。 在本文中,我们证明对于半分布式格,E基系既有效又最小。 我们还描述了具有有效E基数的模块化和几何晶格。 最后,我们证明任何格子都是具有有效E基的晶格的子格子。
我们分析了信仰传播引导决定(一种物理启发的消息传递算法)在随机k-XORSAT问题上的表现。 具体来说,我们得出一个明确的阈值,算法以我们显式计算的严格正概率Ω(1)成功,但超出该算法的高概率算法未能找到一个令人满意的赋值。 此外,我们分析了一个称为毁灭过程的思想实验,我们确定(非)重建和冷凝阶段过渡。 本工作的主要结果证实了物理学的预测[RTS:J。 统计。 机甲。 2009年]将毁灭过程的相变与算法的性能联系起来,并改进了最近一篇文章[Yung:Proc]的部分结果。 2024年国际( CALP )。
图 G 的一组等位路径是“v 根”,其中 v 是 G 的顶点,如果 v 是 S 中所有等分量路径的端点之一。 用ipcoG表示的图G的等距路径复杂度是最小整数k,因此存在一个顶点v∈V(G)满足以下属性:G的任何单个等距路径P的顶点都可以被k许多v根等距路径覆盖。 首先,我们提供了一个 O(n^2 m)-time 算法来计算具有 n 顶点和 m 边缘的图形的等距路径复杂性。 然后我们证明,在三个看似不相关的图形类别中,即双曲线图形,(theta,棱镜,金字塔)自由图和外弦图形的等距路径复杂度仍然为图形。 具有小的等距路径复杂性的直接算法结果。 具体来说,我们表明,如果图形G的等距路径复杂度受一个常数的约束,那么存在一个ISOMETRIC PATH COVER的多项式时间常数因子近似算法,其目标是覆盖具有最小等分路径数的图形的所有顶点。 这适用于上述所有图形类。
自20世纪80年代斯莱特和拉尔引入定位主导代码以来,已经进行了广泛的研究。 在本文中,我们专注于必须属于图形中所有最小定位占主导地位的顶点。 我们称他们为min-forced顶点。 我们显示,连接的顺序 n 的不平凡图中的 min-forced 顶点数由 2/3(n -γ^LD(G)) 限制在上面,其中 γ^LD(G) 表示最小定位占域代码的基数。 这意味着最小强制顶点数与连接的非平凡图的顺序之间的最大比率最多为2/5。 而且,这两个界限都可以达到。 我们还确定所有路径中不同最小定位占主导地位代码的数量。 此外,我们表明,决定顶点是否为min-forced是共同NP-hard。
当 n 是 1, 2, 或 4 的倍数时,则可猜想为 1 的 Hadamard 矩阵存在;对于斜面 Hadamard 矩阵也存在类似的猜想。 我们提供涵盖所有已知Hadamard和SageMath中所有已知Hadamard矩阵的1208个订单。 这使我们能够验证文献中给出的结果的正确性。 在这个范围内,只有一个订单,292,一个倾斜的 Hadamard 矩阵声称有一个已知的结构,需要一个修复。 我们还制作了最新的表,为n ≤ 2999(sew case的resp. n≤ 999),最小指数m,使得已知顺序2^m n的(斜)Hadamard矩阵,在先前发布的源中改进了100多个条目。 我们解释了表的条目如何与 Riesel 数相关。 作为后者的副产品,我们表明(skew-)Hadamard矩阵的Paley结构不为订单2^m 509203工作,对于任何m。
纸折叠序列在字母表{-1,1 }上形成了一个数数的无限序列,描述了一张纸的迭代折叠产生的折叠序列,然后是展开。 在这个说明中,我们观察到这样的序列中的运行长度序列,以及n'th run的起始和结束位置,是2同步的,因此可以通过有限自动机计算。 作为一个特定的结果,我们通过不同的方法获得了Bunder,Bates和Arnold的最新结果,更广泛地说。 我们还证明了这些运行长度序列的关键指数和子词复杂性的结果。
单词w的子序列是指通过删除w中的某些字母同时保持剩余字母的相对顺序而得到的单词u，例如，𝚕𝚊𝚕𝚊是𝚊𝚕𝚏𝚊𝚕𝚏𝚊的子序列。在某个字母表Σ上，包含Σ上所有长度为ι的可能单词作为子序列的单词称为ι-通用的，满足此条件的最大ι称为w的通用性指数，记为ι(w)。此外，不是w的子序列的单词称为w的缺失子序列（AS），对其研究始于（Kosche等人，2022）。在本文中，我们给出了在所有具有相同通用性指数ι的单词中，给定长度k的AS数量的紧界。对于下界和上界，我们分别构造了具有相应长度k的缺失子序列数量最小和最大的单词，并且在下界的情况下，我们以闭式形式提供了缺失子序列的确切数量。最后，我们提出了单词给定长度子序列集合的高效枚举算法：我们给出了一种新颖的最优枚举算法，该算法具有输出线性延迟，预处理时间为O(|w|)，并进一步改进为具有O(1)延迟的增量枚举算法，预处理时间为O(|w|)。
任何Littlestone类,或称稳定图,都有有限集,其功能为“虚拟元素”:这些可以从学习方面视为表示的假设,这些假设可以表达为类中假设的加权多数意见,以及从模型-理论方面作为实现类型的近似有限版本。 我们介绍并研究 Littlestone 类的 epsilon-saturation,或 stable graph,它本质上是在归纳添加所有这些虚拟元素下的类的闭包。 我们表征了这种闭包,并证明在参数的合理选择下,它仍然是Littlestone(或稳定),但并不总是相同的Littlestone维度。 这突出了一些令人惊讶的现象,这些现象与epsilon的政权以及Littlestone/Stable和VC维度之间的关系有关。
众所周知,同一n叶上的任何两棵树都可以由具有n-2网点的网络显示,并且有两棵树不能由网点较少的网显示。 但是需要多少个网点来显示多棵树呢? 对于 n 叶子上的任何一组 t 树,有一个带有 (t - 1)n 的 reticulations 的琐碎网络,显示它们。 为了做得更好,我们必须利用树的共同结构,将不同树的非平凡的子树嵌入到网络的同一部分。 在本文中,我们表明,对于t ∈ o(√(n)),有一组t树,几乎没有共同的结构可以利用。 更准确地说,我们显示任何 t∈ o(√(n)),都有 t 树,因此显示它们的任何网络都有 (t-1)n - o(n) 重调。 对于 t ∈ o(n),我们得到一个稍微弱的绑定。 我们还证明,对于任何常量 c > 0 的 t 树,已经有一组 t 树不能由具有 o(n n) 重调的网络连接显示,与已知 O(n n) 的上界数匹配到常量因子足以显示所有有 n 叶子的树。 这些结果基于简单的计数参数,并扩展到未根的网络和树。
