HYGENE: A Diffusion-based Hypergraph Generation Method
本文提出了 HYGENE，这是一种基于扩散模型的超图生成方法，它通过在超图二分表示上采用渐进式局部扩展策略，首次利用深度学习成功实现了能够生成具有真实多样性的复杂超图。
💻 Category
cs.DM
48 篇论文
Rigidity of polytopes with edge length and coplanarity constraints
本文研究了在保持边长和面共面性但允许面形状改变的条件下多面体的刚性问题，证明了三维凸多面体在此设定下是通用刚性的，并指出灵活性仅为特例。
There is no prime functional digraph: Seifert's proof revisited
本文旨在用现代术语和简化的步骤，重新呈现拉尔夫·塞弗特（Ralph Seifert）于 1971 年证明的“不存在素函数有向图”这一结论，从而澄清该结果早已被发现但被遗忘的历史事实。
Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
该论文提出了一种针对带时间窗旅行商问题（TSPTW）的高效精确算法，证明了经典基准实例因结构可被利用而不再具备代表性，无法有效评估算法性能或作为机器学习训练集。
Erd\H{o}s Matching (Conjecture) Theorem
本文证明了组合数学中长期悬而未决的著名难题——埃尔德什匹配猜想，该猜想断言不含个两两不相交元子集的集合族的最大基数由两个特定构造的上界中的较大者决定。
Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers
该论文证明了有限域上几乎所有向量函数的扩展仿射稳定子均为平凡群，从而确立了扩展仿射等价类的渐近数量等于函数总数除以扩展仿射群大小的精确公式，并表明随机采样策略在密码原语设计中是有效的。
On the Multi-Commodity Flow with convex objective function: Column-Generation approaches
本文提出了一种基于列生成技术的算法优化框架，用于解决具有凸性链路成本函数的多商品流问题（包括可拆分和不可拆分两种变体），旨在通过优化流量分布来提升电信网络资源利用效率并应对带宽受限导致的性能下降。
Circular chromatic index of small graphs
该论文通过系统确定最大度为 4、5、6 的小规模图及多重图的循环色指数并构造特定无穷族图，否定了关于循环色指数在 下方不存在图的边连通性变体“上间隙猜想”。
Domination polynomial of co-maximal graphs of integer modulo ring
本文研究了整数模 环的互素图 的支配多项式，推导了特定情形下的显式公式并证明了其单峰性与对数凹性，同时给出了通解的结构表达式以及支配根模的界限。
Hierarchical threshold structure in Max-Cut with geometric edge weights
本文研究了边权按字典序几何递减的完全图最大割问题，证明了在中间参数区间内孤立割的层级阈值结构，并 conjecture 当 时孤立割即为全局最优解。
Degree-Based Weighted Adjacency Matrices: Spectra, Integrality, and Edge Deletion Effects
本文研究了基于度数的加权邻接矩阵的谱、整数性及其在边删除下的影响，通过计算完全多部图和冠部多部图的加权谱、修正先前关于完全图边删除后谱半径与能量变化的结论，并解决多部图能量变化的开放问题，从而完善了相关理论。
Some polynomial classes for the acyclic orientation with parity constraint problem
本文研究了带奇偶性约束的无环定向问题，通过定义并刻画满足特定必要条件的多项式图类（包括笛卡尔积路径与循环），建立了这些图类之间的包含层次关系，并给出了所有可解实例的构造性多项式时间算法。
On Supports for graphs of bounded genus
本文证明了若宿主图具有有界亏格且子图族满足无交叉条件，则其定义的交集超图存在同样具有有界亏格的支撑图，该结果推广了 Raman 和 Ray 关于非穿刺区域的平面支撑构造工作，并为有界亏格曲面上的超图打包、覆盖及着色问题提供了统一的分析框架。
Edge densities of drawings of graphs with one forbidden cell
本文系统研究了禁止特定单元类型的图绘制（-free drawings）的边密度问题，针对不同的绘图风格、图类型及单元类型给出了紧致的上下界，证明了除一种特殊情况外边密度均为线性或超线性，并完整刻画了不含特定无交叉单元类型的简单图类，同时改进了拟平面绘制的边密度下界。
Localization: A Framework to Generalize Extremal Graph Problems
本文利用局部化框架改进了关于有界度数和路径长度图中团数上界的现有结果，并给出了达到这些最优界极值图的结构刻画。
When Many Trees Go to War: On Sets of Phylogenetic Trees With Almost No Common Structure
本文通过简单的计数论证证明了，对于数量少于 的任意一组系统发育树，若它们之间几乎不存在可被利用的共同结构，则展示这些树所需的网络杂化数将接近 ，而当树的数量达到 时，所需杂化数则与展示所有可能树所需的 上界相匹配。
Complexity of Linear Subsequences of -Automatic Sequences
该论文通过构建识别基本关系的-自动机并分析其状态复杂度，建立了-自动序列内部序列的子词复杂度与线性子序列状态复杂度之间的联系，解决了 Zantema 和 Bosma 关于最高位优先格式下线性子序列的未决问题，并探讨了利用 Büchi 算术构造相关自动机及执行序列操作时的状态与时间复杂度。
An Upper Bound for the Double Domination Number in Maximal Outerplanar Graphs
本文针对最大外平面图，通过提供完整的证明，确立了其双控制数 的上界为 （其中 为外圈上距离至少为 3 的连续顶点对数），从而完善了 Abd Aziz 等人此前提出的但证明不完整的结论。
Explicit Formulas and Unimodality Phenomena for General Position Polynomials
本文通过给出完全多部图的一般位置多项式显式公式，证明了部分大小 时平衡完全多部图多项式的对数凹性与单峰性（而 时不成立），并证实了冠图 在多种自然图类中保留了单峰性，从而深化了对一般位置多项式性质的理解。
The Unit Gap: How Sharing Works in Boolean Circuits
该论文证明了在允许自由反演的与 - 非门基下，布尔电路与公式的最小规模之差恒为 0 或 1（单位间隙定理），并揭示了共享机制仅在变量数达到特定阈值时生效，且当差值为 1 时仅由单个扇出为 2 的门通过特定复用方式产生。