与大图相关的随机单项式理想的概率

《Journal of Algebra》：Probabilities of random monomial ideals associated to large graphs

　　

摘要 受Erd?s–Rényi模型的启发，我们提出了一种新的模型，用于研究由图的边和覆盖生成的无平方因子随机单理想。该模型使我们能够研究正规性的条件，并得出渐近结果。此外，我们还对其他不变量（如Krull维数——我们获得了其阈值函数）的渐近结果进行了阐述，包括正规化和v数。

引言 在数学中，理解复杂对象的一种方法是将随机性作为工具，以研究该对象的平均行为。概率论中已有大量文献证明了对复杂对象研究的有效性。例如，概率方法已被应用于大型结构 [1], [6]，以及对大型随机矩阵的研究以理解其特征值分布 [3], [7], [19], [20], [22], [24], [30]。在代数中，概率也被用于研究随机群中的随机游走 [5], [16], [32] 和随机排列 [2], [21] 等对象。在组合学中，概率被用于研究大型随机图 [12], [13]。此外，还有较少的文献关于随机单理想的研究 [4], [9], [23], [25]。

单理想是交换代数中研究最广泛的理想类之一，不仅因为其固有的代数丰富性，还因为其与组合学、几何学和优化论之间深刻而富有成果的联系。通过组合数据研究代数不变量已成为核心主题。特别是，Herzog–Hibi [17] 和 R. H. Villarreal [28] 等人的经典著作强调了在研究单理想时，诸如深度、维数、正规化和正规性等不变量常常可以被纯组合或多面体术语所解释。

在此框架下，给定图（或更一般地，clutter）存在两类重要的单理想：边理想和覆盖理想。它们是连接无平方因子单理想与图论的两个基本构造。给定一个简单图，其边理想由对应于图边的所有二次无平方因子单项式生成，而覆盖理想则由对应于其极小顶点覆盖的单项式生成。这些理想构成了两个对偶且深度互连的类，已被广泛研究，因为它们明确反映了底层图的组合结构。这种视角产生了丰富的文献，将代数性质（如正规性、无混合性、正规化以及符号幂和普通幂的行为）与经典图论不变量联系起来。关于单理想的一般理论，特别是边理想和覆盖理想，也有着日益增长的文献 [11], [17], [28]。

受De Loera等人 [9] 的工作和Erd?s–Rényi模型的启发，我们提出了一种新的模型，用于研究由图的边和覆盖生成的随机单理想。在前一种情况下，我们获得由二次单项式生成的理想；而在后一种情况下，生成元可以有任意次数。特别是，在前一种设置中，我们能够研究理想的正规性。重要的是要注意，这此前尚未被研究过。这可能是因为对于任意单理想缺乏一般的正规性判据；然而，在由图的边生成的无平方因子单理想的设置中，正规性判据已被广泛研究 [10], [15]。除了正规性之外，我们还研究理想的Krull维数。在我们的模型中，Krull维数与图的独立数重合。图的独立数是最大独立顶点集的大小，即不包含边的顶点集。得益于这一事实，我们的代数问题变成了随机图问题。我们确定了Erd?s–Rényi图具有以t个顶点构成的空图作为诱导子图这一性质的阈值函数。这使我们能够找到Krull维数大于或等于t这一性质的阈值函数。这里t是任意正整数。最后，我们利用主要定理推导出关于理想的正规化和v数的渐近结果。

模型和结果 让我们首先介绍我们的模型。设K为一个域，S = K[x?,…,x?]为n个变量的多项式环。我们考虑随机图?? = (V, E)，其顶点由变量索引V = {x?,…,x?}，每条边{x?,x?}以概率p被选取（对于i ≠ j）。随机图??的每个实现G = (V, E)诱导两个理想：I(G)和I_c(G)，分别称为边理想和覆盖理想，定义如下。
(1) I(G)是由单项式x?x?生成的无平方因子单理想（i,j ∈ V，{x?,x?} ∈ E）

单理想 设S = K[x?,…,x?]为域K上的多项式环，??为一个顶点集为V(??) = {x?,…,x?}的clutter，即??是V(??)的一个子集族，称为边，其中没有任何一个包含另一个。??的边集记为E(??)。clutter的标准例子是一个简单图G。S的单项式记为x? := x?^a??x?^a?，a = (a?,…,a?)。

V(??)的子集A被称为独立或稳定的，如果对任何e ∈ E(??)都有e ? A。稳定顶点集的对偶概念是顶点覆盖，即一个

Erd?s–Rényi图和阈值函数 在本节中，我们介绍Erd?s–Rényi随机图模型。进一步，我们研究Erd?s–Rényi图某些性质的阈值函数。

我们首先简要介绍本文关于图的定义和符号。一个图是一个对G = (V, E)，其中V是顶点集，每条边e ∈ E是V中由两个不同顶点{x?,x?}组成的子集。给定图G = (V, E)和V的子集V' ? V，我们令G_{V'}为G在V'上的限制，定义为

主要结果的证明 本节致力于提供我们所有结果的证明。让我们回顾一下，我们的想法是利用第4节的内容，为所需概率找到上界和下界。

定理2.3的证明 根据[18, Theorem 5.8]，我们有以下事件的等式 {I(??) 不是正规的} = {?? 具有Hochster构型}。首先，我们证明如果p = o(1/n)，则 P({?? 具有Hochster构型}) → 0。这可以很容易地从以下事实得出：0 ≤ P({?? 具有Hochster构型}) ≤ P({?? 具有圈})，其中右端

未引用参考文献 [26] [31]

致谢 我们要感谢Fiona Skerman教授关于随机图的在线笔记，我们的部分证明灵感来源于此。

Daniel Munoz George | Humberto Mu?oz-George | Kevin Mu?oz George