稠密有向图生成树的研究及结果总结

≥G可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）645-654www.elsevier.com/locate/entcs稠密有向图的生成树Richard Mycroft1 Tásio Naia2，3英国伯明翰大学数学学院摘要在90年代，Komlós，Sárközy和Szemerédi证实了Bollobás的一个猜想，证明了对于每个正的α，Δ和足够大的n，每个最小度为（1/2+ α）n的图包含每个n阶树和最大度不超过Δ。我们得到了一个有向图类似的结果，其中最小度被最小半度（这是所有在所有顶点）并且最大度被底层图的最大度替换（即，我们通过忽略边的方向获得的图的最大度实际上，我们证明了一个更强的结果，即一棵n阶树包含在每一个最小半度为（1/2+ α）n的n阶有向图中的充分条件. 这一结果表明，对于所有最小半度为（1/2+α） n的n阶有向图包含几乎所有n阶 的 生成树T。保留字：图论生成树有向图1介绍设F和G是n阶图。δ（G）必须有多大才能保证G包含F的一个拷贝？(We记δ（G）表示G的最小度）。也许是图论中最著名的结果之一，狄拉克我们对有向图（有向图）的一个Dirac型问题感兴趣，用有向图G的最小半度δ0（G）代替最小度的概念，δ 0（G）是G的所有顶点的入度和出度的最小值，即，δ0（G）：=minv∈ V（ G）min. deg−（v），deg+（v），1 电子邮件：r. bham.ac.uk2电子邮件地址：tnaia@member.fsf.org3由CNPq资助的研究201114/2014-3。https://doi.org/10.1016/j.entcs.2019.08.0561571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。646R. Mycroft，T.Naia/理论计算机科学电子笔记346（2019）645≥≥≥F→···→→···→→≥F[|−KKKKKKKKKKKKKk−1KK图1.一、 Cai [5]（左）和DeBiasio和Molla [8]（右）提出的两个n阶半度n/ 2的有向图不含反向Hamilton圈.在图中，Kp表示p阶有向图，其中每对顶点由两条边连接，每个方向一条边，箭头线表示所有可能的边（在相应的方向上）都存在。其中deg−（v）是v的入度，deg+（v）是v的出度。定向G G图是从无向图通过选择方向获得的有向图，每一个边缘。问题1.1设F是一个n阶定向树族（例如，所有n阶定向路的集合）。使得半度为δ 0（G）≥ δ n，F的n阶有向图G包含F中的每棵树的最小整数δ n，F是多少？问题1.1已经解决了所有succiently 大值的n时，只包含方向的道路。Ghouila-Houri [9]证明了：若δ0（G）n/2，则G包含有向Hamilton圈（即，生成循环v1vnv1），并且因此包含生成有向路径（即，生成路径v1vn ） 。DeBiasio、Kühn、Molla、Osthus和Taylor [7]对此进行了扩展，他们证明了如果δ0（G）n/2（且n足够大），则G包含Hamilton圈的所有可能的定向，可能除了反向的一个;存在反向Hamilton圈的已知阈值是δ0（G）n/2+1（同样，对于足够大的n），并由DeBiasio和Molla [8]建立（见图1）。在δn，F的值被精确确定的意义上，这些关于路径的结果是尖锐的实际上，如果δ0（G）=[n/2| −1则G甚至可能不连通（见图2），所以δn ，Fn/2无论何时不为空（参见图1）。因此如果G具有至少n/2半度，则G包含Hamilton路的每个方向（考虑一个n阶圈，它不是反向的，但包含一个n顶点路的给定方向），如上所述，这个界是最好的可能界。据我们所知，关于一般的有向图G具有给定的半度，如果没有其他条件强加给G（虽然，例如，更多的是已知的存在性的Hamilton圈在G中，如果G是一个定向图[10]或如果G是强连通[17]）。图形设置中的情况非常不同（参见，例如：[15、16]）。关于-图二、阶数为n，半度为 n/2 1的有向图，其中不包含Hamilton圈的任何定向. 在图中，K k表示k阶有向图，其中每对顶点由两条边连接，每个方向一条边。左：K k的两个不相交副本，因此n = 2 k。右：K k的两个不相交的副本和一个顶点连接（在两个方向上）到每个副本中的每个顶点，因此n = 2 k +1。R. Mycroft，T.Naia/理论计算机科学电子笔记346（2019）645647.Σ2.Σ≥2≥G≤∈G∈ G∈\Komlós，Sárközy和Szemerédi [11]的一个经典定理指出，如果δ（G）≥1/2+o（1）n，则G包含每一个有界度的树。定理1.2[11]对任意正整数Δ，任意实0<α1/2和任意大整数n，任意 n阶最小度至少为1+α n的包含每个最大度不超过Δ的生成树T。Komlós，Sárközy和Szemerédi后来加强了定理1.2，用cn/logn代替常数界Δ，其中c是依赖于α的常数[12]。存在定理1.2的几个其他变型和扩展（参见，例如，[2、3、4、6、18]）。2我们的贡献我们研究了定理1.2的有向图类似物，其中主有向图具有高半度。定理2.1对所有的正实α，Δ存在n0使得对所有的nn0下列成立。 若G是n阶有向图，且最小半度至少为（1+α）n，则G包含每一个n阶（生成）树，使得Δ（T）≤Δ.我们通过建立一个更强的结果来证明定理2.1。设n，α是所有n阶有向图G的集合，δ0（G）（1/2+α）n. 设C >0，T是n阶有向树，其中n是极大的，T有最大度Δ（T）（logn）C（其中T的最大度是忽略边的方向而由T得到 我们给出了T包含在每个G中的一个充分条件n，α，用它来证明，几乎所有n阶有向树都包含在每个Gn，α中。定理2.1成立，因为每一个（足够大的）有界度的定向树都满足这个条件（这一点在本节的最后得到了证明）。在我们陈述主要结果之前，我们引入一些定义。 路径P在一个有向图T是裸图，如果每条边e E（T）E（P）不与P相交，或者与P相交于它的一个端点（即P中的顶点与P中的一个邻居）。我们使用符号xy来表示对于每个正的y都存在一个正数x0，使得对于每个00，我们可以选择足够大的n，使得Tn不满足定理2.2的条件（i）或（ii）。另一方面，几乎所有的标记树都有次对数最大度，如Moon所证明的。定理2.3[19，推论1和2]对于每个ε > 0，如果T是一致选择的随 机 地从n个顶点上的所有标号树的集合中，然后渐近几乎必然地lognlogn（1− ε）log log n ≤ Δ（T）≤（1 + ε）log log n。由于均匀随机标记树的均匀随机方向产生一致随机标号有向树，定理2.3仍然成立，如果我们用此外，我们可以证明（通过二阶矩方法的简单应用）几乎每棵树都满足定理2.2的情形（ii）。 这一事实，结合由定理2.3直接得出几乎每棵树都包含在每一个高半度有向图中。定理2.4设Tn是n阶标号定向树的集合。对所有正的α，ε，存在n0使得对所有n ≥ n0下列成立. 存在一个族FTn，|F|≥（1−ε）|Tn|使得若G是阶 为n≥n0且δ0（G）≥（1/2+α）n的图，则G包含每棵树T∈ F。我们结束本节描述我们如何从定理2.2推导定理2.1。我们首先介绍几个定义和一个引理。树T的路径分解是T的边不相交子路径的集合，使得T的每条边T恰好包含在一条;我们说，如果每一条路都是空的，是光秃秃的。换句话说，在一棵树的裸路分解中，两条路只允许在它们的端点相交我们写p（T）为T的裸路分解的最小尺寸，l（T）为T的叶数。特别地，如果T是路径，则p（T）= 1，并且如果T是星，则p（T）=l（T）。证明下面的引理并不困难。引理2.5如果T是一棵树，但不是一条路，则l（T）≤ p（T）≤2 l（T）− 3。我们现在可以利用定理2.2和引理2.5导出定理2.1。证据 [定理2.1的证明]设T是n阶有向树，Δ（T）≤ Δ设G是有向图，δ0（G）≥（1/2 +α）n. 我们引入新的常数λR. Mycroft，T.Naia/理论计算机科学电子笔记346（2019）645649[2014 -05-23]∈PPSS- −≥⊆⊆..t−1=t−s。-<ελJ与1/nλλJα，Δ。若T至少包含λJn个叶，则T至少包含λJn/Δ> λn个边不相交的叶边，因此G包含T的一个拷贝，定理2.2（i）证明了这一点. 否则，根据引理2.5，T包含至多2λjn路的裸路分解。注意，T中的任何裸路都是某个P的子路，并且如果P具有长度x（即，x个边），则P至少包含x/t个边不相交的（T的）长度为t（且阶为t+1）的裸路。设x1，...，xs是P中路径的长度，所以x1+···+xs=n−1。然后，对于每个正整数t，我们有中长度为t的边不相交裸路的个数xi，i=1不-是的Xii=1乌斯季-1选择t=8，则T至少包含（n1）/82λJNN/10条 长度为8（阶为9）的边不相交裸路.因此，T至少包含n/10个7阶点不相交的裸路，所以G包含T的一个副本，定理2.2（ii）。Q3定理2.2的证明大纲在这一节中，我们简要地说明定理2.2的证明。详细的论证包含在第二作者的博士论文中定理2.2的证明建立在Kühn，Mycroft和Osthus [13，14]的结果以及作者[20]的前一篇文章的基础上。 这些结果所共有的一个重要成分是正则性方法Szemerédi [22，23]，我们在下一节中简要介绍。（有向图的Szemerédi正则性引理的一个版本3.1关于规律性的粗略地说，正则引理表明，如果G是一个有许多顶点的（di）图，则存在一个均分V1，. V（G）的Vk分成有界数目的集合（通常称为簇），使得几乎所有对（Vi，Vj）之间的边的分布都是类随机的.更准确地说，对于所有的X Vi和所有的Y Vj，我们写eG（X，Y）来表示G中从X指向Y的边的数量;我们说（Vi，Vj）是ε-正则对（非正式地，类随机对），如果eG（X，Y） eG（Vi，Vj）. |X||Y||VJ||.|.对于所有X<$Vi和所有Y<$Vj，|X| ≥ε|Vi|和|Y| ≥ε|VJ|.“约化图”是其顶点对应于G的其边缘对应于以这种类似随机的方式连接并且明显“密集”的簇对形式上，G的约化图R = R（d）（具有参数d并且关于给定的顶点划分V1，.，V（k）的定义如下。使d固定为d1，设R是有顶点集的图<<{1 ， .， k} ， 使 得 对 所 有 i ， j∈Rwe hvei→ j 当 且 仅 当 eG （ Vi ， Vj ） /（|Vi||VJ|）>.T≥≥650R. Mycroft，T.Naia/理论计算机科学电子笔记346（2019）645DR. Mycroft，T.Naia/理论计算机科学电子笔记346（2019）645651∈||||| |→ →···→→3.2校样大纲回想定理2.2的陈述对于T的结构有两种情况。每种情况下的 为了为了简单起见，下面我们假设T属于定理2.2的情况（i）。我们在有向图G中寻找生成树T的策略包括三个步骤：作为初步步骤，我们从T中删除边，得到森林TJ;删除的边被仔细选择，以便它们相距很远，并且TJ的一个分量很大。前两步（分配和嵌入）的目标是在G中找到TJ的副本。最后一步（扩展）添加缺少的匹配。我们的大部分证明包括描述如何嵌入TJG的方式，可以进行扩展步骤。在我们的证明的核心在于两个算法：一个随机分配算法和贪婪算法嵌入TJ。设R是G的约化图（注意R是有向图），设k：=V（R）且n=V（G）.则R的每个顶点对应于G的一个约n/k个顶点的集合，R的边对应于我们可以假定1/n1/k α，并且利用G具有高半度的事实，我们可以证明R包含一个扩张的生成正则子图RJ，并且（必要时重新标记簇）我们可以假定RJ具有一个有向Hamilton圈12k1。（有向图D是扩张图，如果对于V（D）的每个非空真子集S，S在D中的内邻域和外邻域都严格大于S。非正式地，TJ到G的分配是从TJ到RJ的同态。这个同态是由分配算法构造的（事实上，我们在某个阶段改变了一些顶点的分配，使得映射到每个簇Vi的顶点数等于Vi）。我们注意到，在分配阶段，G一旦TJ被分配，我们使用（确定性和贪婪的）嵌入算法将TJ嵌入到G中，该算法通过依次将每个顶点x TJ嵌入到集群中的顶点，依赖于R的边对应于正则对的事实，在G中找到T我们特别注意，而嵌入，以确保顶点事件的边缘在删除匹配的T被映射到“好”的顶点。更准确地说，令M是在开始时从T移除的边（即，TJ：=T−E（M））。 嵌入是这样的，对于M的顶点写Mi对于Mi的图像，嵌入到聚类Vi和ViJ，以下成立。（一）|Mi|为|M|/k;(ii) 要么(a) 对于每个x∈Mi，x在Mi中的邻居被嵌入到ViJ+1，对于所有i ∈ {1，.，k}，其中加法是模k;或(b) 对于每个x∈Mi，x在Mi中的邻居被嵌入到ViJ1，对于所有i ∈ {1，.，k}，其中减法是模k）;-(iii) （ViJ，ViJ+1）和（ViJ，ViJ1）是正则对，使得ViJ中的每个顶点具有多个外邻在VJ−，内邻在VJ−。一期+1i−1652R. Mycroft，T.Naia/理论计算机科学电子笔记346（2019）645PPP∪PPP∈P PP上面的条件确保我们可以找到M的一个副本，它将TJ的嵌入扩展到T在G中的嵌入。3.3分配分配中的主要挑战是确保我们生成的同态将T的正确数量的顶点映射到每个簇。这是通过仔细分配裸路径的T（或顶点不相交的边缘事件的叶T分别），并通过使用随机分配算法，产生（具有高概率）一个几乎均匀分布的顶点的一棵大树，一个小的定期扩展。(The分配算法在本节末尾描述。）下面是我们如何进行。我们将T划分为两个大的边不相交的子树T1和T2;这可以这样做，|V（T1）| ≤ |V（T2）|所以T1包含许多空路径。我们固定T1中两个不相交的成对顶点不相交裸路族P1，P2，并收缩P1<$P2中的所有路径，得到一棵树T<$。设T1J是我们通过这种压缩从T1我们使用随机分配来分配T1J算法，并以不同的方式分配1和2随机算法产生树T到有向图R的同态;我们可以证明，如果R包含一个生成正则，则该算法以高概率产生T的顶点到R的顶点的几乎均匀分布。满足某些扩张性质的子（di）图RJ，如果T具有最大度有界（如定理2.2的假设）。由该算法产生的T1J的分配，连同12中的路径可能不是非常均匀（由于1和2）。我们恢复几乎均匀分配T2使用加权版本的分配算法。因此，T的分配结果几乎是均匀的。收缩路径的家庭服务于不同的目的。1中的路径是allo- 这样它们具有多于一个的有效分配（即，使得它们的一些顶点可以被分配给至少两个簇中的任一个，同时仍然产生同态）。换句话说，我们在选择这些顶点的分配时具有一定的灵活性，我们使用它来将T1T2的几乎均匀的分配细化为与每个簇的大小相匹配的精确分配。另一方面，图2中的路径用于嵌入阶段的最后一步：扩展。粗略地说，2中的路径被映射，以确保沿着R的某些边分配许多特定方向的边;这在找到所需的匹配M时很有用。分配算法。设r是T1和T2的交点处的唯一顶点，并认为T的根为r。我们建立一个从T到RJ的同态，每次一个顶点，从r开始，这样没有顶点在其父顶点之前被处理，所以在每一步我们将顶点v V（T）映射到RJ的顶点。 (The顶点v的父节点是v在从v到r的路径中的邻居）。当分配任何顶点x（除了根）时，T中x的父节点p是x唯一定义了x的邻居。设Cp是p的子族。我们一次为Cp中的所有顶点定义a，如下：首先在RJ中选择a（p）的内邻v-和外邻v+R. Mycroft，T.Naia/理论计算机科学电子笔记346（2019）645653≤||P⊆∈v∈ V（ G）GG均匀随机，选择独立于算法中的所有其他选择;然后将p的每个近邻映射到v-，将p的每个近邻映射到v+。我们注意到，对于直径较小的树，例如，如果T是一个星，那么T的中心是映射到R的某个顶点的唯一顶点。然而，通过定理2.2的假设，T的最大次数永远不会太高，我们避免了这个问题。事实上，证明中的一个重要步骤是证明如果Δ（T≠）（logT）C，其中1/n1/C，则T的大多数顶点（明显地）彼此远离。3.4嵌入大多数嵌入由下面的算法确定。更准确地说，我们将嵌入算法应用于T的子树，该子树是通过收缩属于2中的路径的一些边而获得的（我们在这样做时很小心，以便对收缩树的分配的限制仍然是同态）。此外，我们没有将嵌入算法应用于整个G，而是应用于子图GJG（我们在每个簇中保留一些顶点集用于最后的匹配）。我们证明了嵌入算法的成功，它产生的嵌入可以扩展到一个完整的副本T在G中的扩展阶段。我们以嵌入算法的概述来结束本节。我们注意到下面的描述非常简单，因为驱动算法的一个关键属性，在[21]中表示为（β，γ，β，m）-goodness，有点技术性，因此在本文中省略了。嵌入算法类似于分配算法，我们认为我们希望嵌入的树T是有根的;我们嵌入T的顶点，这样兄弟节点在同一步嵌入，每个顶点都嵌入在它的父节点之后。(The算法的精确描述是相当技术性的，因此我们省略它。简而言之，对于每个xT，我们将x嵌入到聚类（x）中，并且当我们这样做时，我们还为x的子节点保留了一组顶点。这里的一个重要问题是，保留集中不能有太多的顶点：这可以通过仔细选择顶点处理的顺序来确保。4结论我们的定理2.1，2.2和2.4描述了每一个高半度有向图的一个大的生成树族;事实证明，这是几乎每一棵树的一个性质，也是每一个最大度由一个常数限制的极大树的一个性质。这回答了问题1.1的许多例子。让我们注意两种非常自然的方式来概括这个问题。一个方向是考虑较弱的度概念，例如总度δtot（G），定义为δtot（ G）：= min. deg−（V）+deg+（v）<$。654R. Mycroft，T.Naia/理论计算机科学电子笔记346（2019）645问题4.1定理2.1，2.2和2.4如果我们替换δ0（ G）δ tot（G）/2？考虑更一般的生成子有向图类也是很自然的（就像对无向图所做的那样），寻找定理1.2的推广的有向图类似物。问题4.2在每一个高半度图中必须包含哪些生成子有向图？通常情况下，（无向）图问题的有向版本需要实质上不同的方法来解决。我们相信，我们介绍的问题1.1的一些工具可以适用于获得对问题4.1和4.2的结果。引用[1] Alon，N.和A. Shapira，有向图中的测试子图，计算机与系统科学69（2004），pp. 354-382.[2] Balogh，J.，B. Csaba和W. Samotij，Local resilience of almost spanning trees in random graphs，Random Structures Algorithms38（2011），pp.121-139[3] Böttcher，J.，J. Hàn，Y.科哈亚卡瓦河Montgomery，O. Parczyk和Y. Person，Universality for boundeddegree spanning trees in randomly perturbed graphs，ArXiv e-prints（2018）。[4] Böttcher，J.，M. Schacht和A. Taraz，Bollobás和Komlós带宽猜想的证明，Mathematische Annalen343（2009），pp.175-205[5] 蔡，M.C.的方法，格兰特猜想的一个反例，离散数学44（1983），p.111.[6] Clemens，D.，A.费伯河Glebov，D. Hefetz和A. Liebenau，Building spanning trees quickly in maker-breaker games，SIAM Journal on Discrete Mathematics29（2015），pp.1683-1705年。[7] 德比亚西奥湖，D. Kühn，T. Molla，D. Osthus和A. Taylor，Arbitrary orientations of Hamiltoncycles in degraphs，SIAM Journal on Discrete Mathematics29（2015），pp.1553-1584年。[8] 德比亚西奥湖和T. Molla，Semi-degree threshold for anti-directed Hamilton cycles，Electronic Journalof Combinatorics22（2015）。[9] Houri，G.，Une condition su suspensante495-497[10] Keevash，P.，D. Kühn和D. Osthus，An exact minimum degree condition for Hamilton cycles inoriented graphs，Journal of the London Mathematical Society79（2009），pp.144-166[11] Komlós，J.，G. N. Sárközy和E. Szemerédi，Bollobás的一个填充猜想的证明，Combinatorics，Probability，and Computing4（1995），pp. 241-255[12] Komlós，J.，G. N. Sárközy和E. Szemerédi，Spanning trees in dense graphs，Combinatorics，Probability，and Computing10（2001），pp. 397-416[13] Kühn，D.，R. Mycroft和D. Osthus，A proof of Sumner731-766[14] Kühn，D.，R. Mycroft和D. Osthus，Sumner's universal tournament conjecture的近似版本。Journal of Combinatorial Theory，Series B101（2011），pp.415-447[15] Kühn，D.和D.Osthus，137比167R. Mycroft，T.Naia/理论计算机科学电子笔记346（2019）645655[16] Kühn，D.和D. Osthus，Hamilton cycles in graphs and hypergraphs：an extremal perspective，in：Proceedings of the International Congress of Mathematicians （ Seoul ， Korea ） ， ICMC 20144 4 ，2014，pp. 381-406.[17] Kühn，D.，D. Osthus和T. Townsend，竞赛图划分猜想的证明及其应用到1-因子与规定的周期长度，Combinatorica 36（2016），pp. 451-169.[18] Michael Krivelevich，B.美国，关文龙，随机扰动图中的有界度生成树，北京大学出版社。离散数学31（2017），pp.155-171[19] 穆恩，J.W.，“Counting labelled trees,” Number 1 in Canadian Mathematical Monographs, CanadianMathematical Congress,[20]迈克罗夫特河和T.Naia，Unavoiting trees in tournaments，Random Structures Algorithms53（2018），pp. 352-385.[21] Naia，T.， 论文，伯明翰大学（2018）。[22]Szemerédi，E.，关于算术级数中不含k元素的整数集，Acta Arith。27（1975），pp. 1999 -245，收集的文章在记忆中的尤里·弗拉基米尔o维奥里奥·林尼克。[23] Szemerédi ， E. ， Regular partitions of graphs， in： Problèmes combinatoires et théorie des graphes（Colloq. Internat. CNRS，Univ. Orsay，Orsay，1976），CNRS，Paris，1978 pp. 399-401