可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）535-544www.elsevier.com/locate/entcs具有给定顶点数和边数的稀疏k-边连通超图的Carlos Hoppen卡洛斯·霍彭1，2巴西南里奥格兰德州阿雷格里港联邦大学纯数学与应用数学系吉列姆岛Mota3ABC地区圣安德雷罗伯托·F Parente4巴西巴伊亚萨尔瓦多联邦大学计算机科学系克里斯蒂安·M 佐藤5ABC地区圣安德雷摘要本文给出了n阶k-边连通r-一致超图的个数的一个渐近公式，其中r≥3，k≥2是固定常数，m=O（nlogn）保留字：超图，计数，概率方法，连通性https://doi.org/10.1016/j.entcs.2019.08.0471571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。536C. Hoppen et al. /Electronic Notes in Theoretical Computer Science 346（2019）535R1介绍寻找具有所需性质的组合结构个数的封闭公式是组合数学中的一个基本问题。它有很长的历史，有趣的结果和各种各样的技术已被应用于它。连通性）已经用生成函数、代数工具、概率方法等来处理（参见[9，6，8，7]）。概率方法已被用于获得极大的成功，因为许多枚举问题都与计算概率在一个合适的随机模型。例如，一些作者使用概率方法研究了一些类图的计数问题[14，15，11]。Pittel和Wormald[14]研究了给定顶点数和边数的最小度至少为k的在随机模型中，当度序列仅限于一组这可以用来说明所得到的公式也是给定顶点数和边数的k-连通图的个数的渐近公式。有趣的是，对于k= 2，情况并非如此，因为在稀疏方案中，即使所有度至少为2，随机图也几乎肯定渐近地孤立循环（我们由a.a.s.从现在起）。第四作者与Kemkes和Wormald[10]在一篇论文中讨论了这种情况。然后很自然地解决超图的同样的计数问题。直觉上，人们会期望问题会变得更加困难，因为当推广到超图时，许多图问题都是这种情况。对于给定顶点数和边数的连通r-一致超图的个数求渐近公式的问题，也是如此（见[5，1，4，3]）。本文研究了具有给定顶点数和边数的k-边连通r-一致超图的计数问题，其中k≥2，r≥3是固定常数.我们还将包括r= 2和k≥3的完全性证明。我们使用Pittel和Wormald [14]和L-uczak[12]使用的类似技术。 我们使用了Pittel和Wormald提供的大量事实[14]。结果r-一致超图是指一对H=（V，E），其中V是有限集，E是有限集. VR（在哪里。V是大小为r的V的子集的集合。1克的O. Mota得到了FAPESP（2018/04876-1）和CNPq（304733/2017-2，428385/2018- 4）的部分支持。C.Hoppen感谢CNPq（308054/2018-0）的支持。C. M. Sato感谢CNPq（423833/2018-9）的支持。 FAPESP是圣保罗研究基金会。 CNPq是巴西国家科学技术发展委 员会 。2电子邮件：choppen@ufrgs.br3电子邮件：g. ufabc.edu.br4电子邮件：roberto. ufba.br5电子邮件：c. ufabc.edu.brC. Hoppen et al. /Electronic Notes in Theoretical Computer Science 346（2019）535537CCΣηl−1. .ΣΣR224J一个r-一致超图H=（V，E）是连通的，如果不存在不与S和V\S相交的真非空S∈V.我们说H是k-边连通的，如果不存在集合F ∈ E，|F |0，但我们选择λ，使其最大化P[m]. 还请注意，如果Y具有泊松分布（λ，k），则E Y = λf k−1（λ）。fk（λ）设c=rm/n，定义λc为方程的根λf k−1（λ）= c. fk（λ）它的存在性和许多性质已经由Pittel和Wormald证明[14]。让η= λcfk−2（λc）。（五）fk−1（λc）n=P[Y=d]U（d）C. Hoppen et al. /Electronic Notes in Theoretical Computer Science 346（2019）535543i=12我−CΣηΣη[U（Y）|[1]=（1 +o（1））exp−C4CRRCC回想一下，η（d）=（1/m）<$n。是的。 不难证明E[η（Y）]=ηc。然后，我们可以定义DrJ，k（n，m），使得η（Y）为零。Forε∈（0，1/2），定义DrJ，k（n，m）=.d∈Dr，k（n，m）：maxdi≤6C logn，|η（d）−ηc| ≤n−1/2+ε。（6）那么不难证明，P[Y/∈DrJ，k（n，m）]≤X-ray（Θ（logn）3）P[m].（七）对d∈DRJ， k（ n，m）， 设定理1.2 ，我们有一个U （ d） <$exp （ −（r−1）ηc/r−1r=2η2/4），其中当r = 2时，1r=2 = 1，否则，1r=2 =0.对于d/∈Drj， k（n，m），由于U（d）≤1是一个概率，我们使用U（d）≤1. 我们，E. （r−1）ηcη2π。exp（−Θ（logn）3）P[]exp（−Θ（logn）3）P[]为了完成证明，我们使用Pittel和Wormald的以下结果来计算P[k]（在我们的场景中陈述）：定理3.1（Pittel和Wormald [14]，定理4）设R = rm-kn。 如果R→ ∞，则P1+O（R−1）如果R=O（n2/5），则[π] =π2 πnc（1 + η−c）。P[R]=（1+O（R5/2n−1））e−RRR.R！因此，P[Ω]= Ω（1/R），因此E [U（Y）]|[1] =（1 + o（1））exp=（1+o（1））exp.−（r−1）ηc.−（r−1）ηc2-1r=242-1r=24R-1r=21−+.544C. Hoppen et al. /Electronic Notes in Theoretical Computer Science 346（2019）535ΣηRC+ exp（−Θ（logn）3）.因此Cr，k（n，m）rm！休息一下！MQr，k（n，m）exp.−（r−1）ηc2-1r=24，它通过在Qr，k（n，m）中代入P[k]的值（在定理3.1中得到）C. Hoppen et al. /Electronic Notes in Theoretical Computer Science 346（2019）5355454定理1.2的证明我们将遵循L-uczak[12]在图的情况下使用的相同策略。我们会证明，不存在大小为k−1的边集合来断开随机多重图。两个主要引理如下：第一个限制了小顶点集合中诱导边的数量，第二个限制了一个大集合有少于k条边交叉到其补集的概率。引理4.1设ε > 0和D > 0是固定常数。 尽快，没有固定S∈ [n]，大小r ≤ s ≤ D log n，至少有（1 + ε）s/（r − 1）条诱导边。引理4.2设DJ> 0为固定常数。尽快， 没有一个集合S [n]的大小DJlog n ≤ s ≤ n − DJlog n且少于k条边与S和[n]\S相交。现在我们来证明定理1.2。 它表明，A.A.S.，不存在非空的真子集S∈[n]使得存在一个大小为R的边集|k使得R是S的极小边割（也就是说，R是极小集合，使得通过移除R，集合S变得与[ n ] \ S不连通）。|< k such that R is a minimal edge-cut for S (that is, R is aminimal set such that by removing R the set S becomes disconnected from [n]\S).注意，对于|r，这直接从顶点的最小度至少为k的事实得出。|< r, this follows immediatelyfrom the fact that the minimum degree of a vertex is at least k.每一条边都有顶点，|S|至少有一个顶点在S之外，所以至少有k条这样的边。如果|S|>D log n，我们的主张直接由引理4.2得出。注意，对于r = 2且|S| =2，因为最小度至少是k，我们有至少有2 k − 1 ≥ k条边在S的边割中。假设r≤|S| ≤D log n（r≥ 3），并假设r + 1 ≤|S| ≤D log n（r = 2）。设SJ=S∈Re.设R是S的极小边割。 则R中的每条边都必须与S及其补数[n]相交。设T表示数字R中的点与S外的点相匹配。 然后，|≤ |不|≤（r − 1）（k − 1）且|SJ|≤|S|+的|不|.|.（8）则由Sj诱导的边的数目至少为（k|S|+的|不|）/r.它是直的-向前，通过计算导数，证明，对于ε= 1/（5r），K|S|+的|不|≥（1 + ε）|SJ|、（九）r r−1这与引理4.1相矛盾。因此，没有这样的Ra.a.s.，所以定理1.2成立我们给出了引理4.1的证明，省略了引理4.2的证明，因为它们的证明遵循相同的策略。4.1引理4.1的证明设S为[n]，其中s：= |S|.设VS是对应于S中的顶点的顶点仓中的点的集合，并且回想V是顶点仓中的所有点的集合。令P S= |VS|和P = |V|. 注意，P≥kn，因为每个顶点仓具有至少k个点，并且PS≤Δs。546C. Hoppen et al. /Electronic Notes in Theoretical Computer Science 346（2019）535=警！.（1）（logn）P−iLRL（kn/r）rl−l， 因为m≥kn/r102s+lΣr≤s≤DlognSL使用并界，它至少诱导l=l（s）：=（1 +ε）s/（r−1）条边的概率至多.我很抱歉。PS（rl）！（P−rl）！LRL. mrl−1PS−iLi=0.我很抱歉。PSrlLP. 我很抱歉。ΔsrlLRM其中. M是包含诱导边缘的波形的数目。P.S.是Number的方式选择点在S匹配这些诱导边缘，（rl）！是这些选定点之间的匹配数，（P-rl）！是剩余点与P之间的匹配数！是匹配的总数;对于最后一个不等式，我们使用P=rm和PS≤Δs。在所有大小在r和Dlogn之间的子集S上对该值求和，存在一组大小s引起l（s）条边的概率至多为- 是 的n. 我很抱歉。Δsrlr≤s≤DlognSLRM- 是 的嗯。嗯。Δ s rlr≤s≤DlognSLRM- 是的嗯。el（Δ s/r）rlr≤s≤DlognSLmrl−l- 是的嗯。el（Δ s/r）rles+ lslΔs+ l。Δ srl−s−l=r≤s≤DlognΣkrl−lrln2s +l . Δsrl−s−l≤r≤s≤Dlogn（Θ（1）（logn）），kn（logn）时间复杂度：O（logn）2rl−s−l=（Θ（1）（logn））r≤s≤Dlogn=r≤s≤Dlogn（Θ（1）（logn）2）（r+ε）s/（r−1）n. Θ（1）（log n）2εsn≤r≤s≤Dlogn （Θ（1）（logn）4）s. Θ（1）（log n）2εsn≤（Dlogn）. Θ（1）（logn）2+4/εεrn≤、≤≤≤C. Hoppen et al. /Electronic Notes in Theoretical Computer Science 346（2019）535547=o（1），这就完成了引理4.1的证明。548C. Hoppen et al. /Electronic Notes in Theoretical Computer Science 346（2019）535引用[1] M. Berherisch， A. 科亚-奥格兰 和 M. 康连通d-一致超图的渐近数。Combinatorics，Probability and Computing，23（3）：367[2] Blinovsky和C.格林希尔给定度稀疏一致超图的渐近计数。European Journal of Combinatorics，51，092014。[3] B. Bollo b'as和O. 赖尔登用概率方法计算连通图。Combinatorics，Probability and Computing，25（1）：21[4] B. Bollob'as和O. 赖尔登 用概率方法计算稠密连通图。随机结构算法，53（2）：185[5] A. Coja-Oghlan角Moore，and V. Sanwalani.用概率方法计数连通图和超图。Random StructuresAlgorithms，31（3）：288[6] P. Flajolet和R.塞奇威克分析组合学剑桥大学出版社，2009年。[7] O. Gimenez和M.诺伊平面图的渐近计数与极限律。 J Amer Math Soc，22，02 2005.[8] F. Harary和E.M. 帕尔默图形枚举。Elsevier Science，2014.[9] M. Isaev和B. D.麦凯复鞅与渐近计数。随机结构算法，52（4）：617[10] G. 凯姆克斯角M. Sato和N.蠕虫 稀疏2-连通图的渐近计数Random Structures Algorithms，43（3）：354[11] L. Lu和L. Sz 'e kel y. 在随机注入空间中使用l ov′aszl ocal引理。 El ectr. J. 梳子2007年9月14日。[12] T. 卢-乌扎克。 具有给定度序列的稀疏随机图。InProceedingsoftheSymposiumonRandom Graphs，Poznan，pages 165[13] B.D.麦凯具有指定行和的对称0-1矩阵的渐近性。Ars Combinatoria，19A：15[14] B. Pittel和N. C.蠕虫具有最小度约束的稀疏图的渐近计数。Journal of Combinatorial Theory，SeriesA，101（2）：249[15] B. Pittel和N. C.蠕虫从里到外计算连通图。Journal of Combinatorial Theory，Series B，93（2）：127
