A new proof of Delahan's induced-universality result
本文通过引入生成索引集的概念，为 Delahan 关于每个 阶简单图均可作为具有 个顶点的 Steinhaus 图的诱导子图这一结论，提供了一个简短且自包含的新证明。
💻 Category
cs.DM
48 篇论文
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
该论文研究了排列匹配拼图问题，完全刻画了基于行列升降约束的网格填数谜题的可解性条件（即约束图无环或标签切换不超过一次），给出了可解情况下的解数钩长公式及不可解情况下的最小修复算法，并证明了当约束推广为任意排列时，寻找最小修复方案是 NP 完全的。
WELLDOC property for words generated by morphisms
本文研究了无限词上的“良好分布出现”（WELLDOC）性质，并给出了由态射生成的无限词具有该性质的判定准则。
A characterization of interval nest digraphs
本文通过引入“巢序”（nest orderings）这一顶点线性排序概念及其禁止模式，给出了区间巢有向图（interval nest digraphs）的完整刻画，从而补全了区间有向图主要子类在顶点排序刻画方面的理论图景。
A note on approximating the average degree of bounded arboricity graphs
本文旨在完整呈现并优化 Eden 等人提出的算法，使其能在有界树宽图中以 的查询复杂度实现平均度的 近似，从而避免了原论文中因参数搜索导致的对数因子损失。
Digraph Branchings and Matrix Determinants
本文提出了一种通过添加根节点来处理非零列和的有向图矩阵树定理推广形式，证明了其与矩阵森林定理（全主子式定理）的等价性，并将其应用于离散状态系统的演化计算及行列式求解策略。
Models of random spanning trees
本文针对随机最小生成树（MST）数学性质研究不足的问题，开发了定量分析工具，并研究了边权服从独立同分布及更一般的乘积测度下的随机 MST 模型。
Linear colorings of graphs
本文研究了线性色数的性质，并在多个图类中改进了其与树深之间的界限，从而对 Kun 等人提出的树深不超过线性色数两倍的猜想提供了更深入的探讨。
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
本文从理论上证明了-DRESS 框架不仅能无条件区分所有 CFI图对，还在特定结构猜想下被证明其区分能力至少等同于-WL 层次结构，从而确立了该框架在图同构判别中的强大理论地位。
Binomial Random Matroids
本文研究了二项随机拟阵的相变现象，确定了其成为拟阵的概率阈值，证明了在满足条件时该随机结构几乎必然是稀疏铺砌拟阵，并利用相关算法改进了对拟阵、铺砌拟阵及稀疏铺砌拟阵数量估计的结果，使其适用于秩 随 缓慢增长的情形。
Additive Subtraction Games
本文针对《Winning Ways》中提出的加法减法博弈问题，在原始二次情形下给出了基于有理模贝蒂型括号表达式的 P-位置闭式公式的完整证明，并确立了每个尼姆值序列均位于经典 P-位置的线性平移之上。
M-Polynomial of Product Graphs
本文针对顶点集为因子笛卡尔积的多种图乘积（包括直积、笛卡尔积、强积、字典积、对称差积、析取积和谢尔宾斯基积），推导出了计算 M-多项式的显式公式，从而为度基拓扑指数提供了统一的结构性描述框架。
Mean-based incomplete pairwise comparisons method with the reference values
本文提出了一种基于参考值的不完整成对比较均值计算方法，通过扩展算术和几何启发式估计（HRE）方法，证明了新几何方法的优化性与解的存在性，并给出了算术变体解存在的充分条件。
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
该论文提出了一种固定参数可解（FPT）算法，不仅解决了判定图能否被少于 条顶点不相交路径覆盖的长期未决问题，还首次证明了在独立数有界的情况下哈密顿路径判定问题是多项式时间可解的，从而推广了经典的 Gallai-Milgram 定理。
Block-Separated Overpartitions: Fibonacci Structure and Euler Factorization
本文引入并研究了块分离过划分这一受约束的过划分族，揭示了其内部装饰遵循斐波那契型组合规律，从而导出生成函数的对称函数展开、多种递推与行列式表示，并证明了其渐近增长速率与普通划分具有相同的指数尺度但修正了次指数常数。
Induced Minors and Coarse Tree Decompositions
本文证明了关于排除完全二部图和网格诱导子图之图的树分解猜想的一个弱化版本，即存在一种树分解，其每个包的特定距离独立数具有对数多项式上界。
Homomorphisms of (n,m)-graphs with respect to generalised switch
本文通过提出一种囊括所有已知情形的广义切换操作，以公理化方式系统研究了-图的同态性质，解决了多个长期未决的开放问题，构建了具有反直觉顶点规模的范畴积，并利用群论确定了森林类图的广义切换色数。
The Complexity of Distance- Dominating Set Reconfiguration
本文研究了距离-支配集重配置问题，证明了在分裂图中当时该问题属于类（与时的-完全性形成复杂度二分），并给出了树图上的线性时间算法，同时扩展了平面图、二分图和弦图上的-完全性结果。
On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
本文研究了带有正析取约束的最短路径问题的参数化复杂性，针对解大小和图 H 的结构性质等参数，提出了多项式核化算法并证明了固定参数可解性。
Block encoding the 3D heterogeneous Poisson equation with application to fracture flow
本文研究了量子线性系统算法在求解三维非均质泊松方程（应用于地质裂隙流动）中的可行性，通过显式构建块编码实现了优于经典算法的时间复杂度并显著节省内存，但也指出分别对系统矩阵和预条件子进行块编码无法改善主导运行时间的有效条件数，揭示了该领域实现量子优势的关键障碍。