Embedding spanning subgraphs into large dense graphs
Embedding spanning subgraphs into large dense graphs
复制标题
将跨越子图嵌入到大型密集图中
DOI：
10.7282/t3mc8zsd
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Asif Jamshed
中科院分区：
文献类型：
--
作者：
E. Szemerédi;Asif Jamshed
在这篇论文中，我们将给出一些关于在大稠密图中嵌入生成子图的结果。
生成树。Bollobas证明了：若G是n阶图，δ（G）≥（1/2 + e）n，其中e > 0，T是n阶有界度树，则T是G的子图.这个问题是解决了肯定的Komlos，萨科齐和Szemeredi大型图。然后他们加强了他们的结果，证明了T的最大度不必是有界的：存在一个常数c使得当Δ（T）≤ cn/logn，δ（G）≥（1/2 + e）n且n较大时，T是G的子图.这两个证明都是基于正则引理-爆破引理方法。最近，使用其他方法，它表明，有界度树嵌入到图的最小度n/2+ Clog n，其中C是一个常数依赖于最大程度的T。这里我们证明了一般情况下n/2 + O（Δ（T）· log n）对于任何Δ（T）≤ cn/ log n是充分的.我们还证明了当m = C和m = cn/ log n时，这个界对于m的两个极值是紧的.
哈密顿圈的幂1962年，Posa证明了如果δ（G）≥ fn，则G包含一个Hamilton圈的平方。1974年，Seymour推广了这个猜想：如果δ（G）≥（k-1 k）n，则G包含一个Hamilton圈的（k - 1）次方。1998年，Komlos、Sarkozy和Szemeredi利用正则引理证明了这个猜想。我们提出了一个“deregurarised”证明的Posa-Seymour猜想的结果在一个低得多的阈值为n，该猜想是真的图的大小。我们希望在这个证明中使用的工具将把n的阈值降低到100左右，在这一点上，我们将能够验证每个n的猜想。
In this thesis we are going to present some results on embedding spanning subgraphs into large dense graphs.
Spanning Trees. Bollobas conjectured that if G is a graph on n vertices, δ(G) ≥ (1/2 + e)n for some e > 0, and T is a bounded degree tree on n vertices, then T is a subgraph of G. The problem was solved in the affirmative by Komlos, Sarkozy and Szemeredi for large graphs. They then strengthened their result, and showed that the maximum degree of T need not be bounded: there exists a constant c such that T is a subgraph of G if Δ( T) ≤ cn/ log n, δ( G) ≥ (1/2 + e)n and n is large. Both proofs are based on the Regularity Lemma-Blow-up Lemma Method. Recently, using other methods, it was shown that bounded degree trees embed into graphs with minimum degree n/2+C log n, where C is a constant depending on the maximum degree of T. Here we show that in general n/2 + O(Δ(T) · log n) is sufficient for every Δ(T) ≤ cn/ log n. We also show that this bound is tight for the two extreme values of m i.e. when m = C and when m = cn/ log n.
Powers of Hamiltonian Cycles. In 1962 Posa conjectured that if δ(G) ≥ fn then G contains the square of a Hamiltonian cycle. Later, in 1974, Seymour generalized this conjecture: if δ(G) ≥ ( k-1k )n then G contains the ( k – 1)th power of a Hamiltonian cycle. In 1998 the conjecture was proved by Komlos, Sarkozy and Szemeredi for large graphs using the Regularity Lemma. We present a “deregularised” proof of the Posa-Seymour conjecture which results in a much lower threshold value for n, the size of the graph for which the conjecture is true. We hope that the tools used in this proof will push down the threshold value for n to around 100 at which point we will be able to verify the conjecture for every n.