Spanning subgraphs of dense graphs and a combinatorial problem on strings
Spanning subgraphs of dense graphs and a combinatorial problem on strings
复制标题
密集图的生成子图和字符串组合问题
DOI：
10.2307/3616324
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
E. Szemerédi
中科院分区：
文献类型：
--
作者：
Sarmad Abbasi;E. Szemerédi
本论文由两部分组成。本文第一部分研究稠密图的支撑子图。具体地说，我们提出了以下结果：
(1)证明了对于每一个Δ0和γ>；0，都有一个α>；0使得下面的命题成立：如果G是一个最小度至少为n2+gn的n点图，则G包含所有满足dh≤D 0和b H≤an的n点二部图H。这里b(H)是H的带宽，是使得H的顶点可以排序为v1，L，vn的最小数b，使得vi，vj∈EH蕴含i-j≤b。这解决了当k=2时Bollobas和Komlos的嵌入猜想。
(2)回答了E.Szmeredi的一个问题，我们证明了这个猜想是紧的，如果g→0，则→0。更准确地说，我们证明了对于任何g≤1100，都有一个Δ0使得aD0，g≤4G。
(3)Ei-Zahar的一个猜想断言：如果H是由r个长为n1，n2，L，nr且满足n1+n2+c+nr=n的点不交圈组成的图，且G是任意n个最小度至少为n12+n22+c+ni2的图，则H是G的一个子图。
(4)我们证明了一个一般定理，我们称之为分解定理。利用这个定理，可以很容易地得到许多已知的结果。作为该定理的应用，我们给出了如何得到Alon-Yuster猜想的一个证明。Alon-Yuster猜想指出，对于h个顶点上的每个图H，都有一个常数C(H)使得如果G是n=NH个顶点上的任意一个最小度为1-1cHn+CH的图，则G包含H的顶点不相交的副本。这个猜想最先由Komlos，Sarkozy和Szmeredi解决。
在论文的第二部分中，我们考虑了一个关于弦的组合问题。这个问题产生于分子生物学，并具有实际应用。
设Σ是一个有限字母表，x∈Sn。一个串y∈Sm称为k-不同于x，如果x的k长子串不等于y的任何k长子串.我们给出了一个Onlogn算法，它在输入x∈Sn和一个整数m≤n上输出一个整数k和y∈Sm使得：(1)y k-不同于x.(2)不存在k-1不同于x的长度m的串z.
该算法是实用的，并已被分子生物学家用于设计某些实验的DNA。
This thesis consists of two parts. Part I of the thesis deals with spanning subgraphs of dense graphs. In particular, we present the following results:
(1) We show that for every Δ0 and γ > 0 there is an α > 0 such that the following statement holds: If G is an n vertex graph with minimum degree at least n2+gn then G contains all n vertex bipartite graphs, H, satisfying DH≤D 0andb H≤an. Here b(H), the bandwidth of H, is the least number b such that the vertices of H can be ordered as v1,l,vn such that vi,vj ∈EH implies i-j≤b. This settles the embedding conjecture of Bollobas and Komlos for k = 2.
(2) Answering a question of E. Szemeredi we show that this conjecture is tight in the sense that if g→0 then a→0. More precisely, we show that for any g≤1100 there is a Δ0 such that aD0,g ≤4g.
(3) A conjecture of EI-Zahar asserts the following: If H is a graph consisting of r vertex disjoint cycles of length n1,n2,l,nr satisfying n1+n2+c+nr=n and G is any graph on n vertices with minimum degree at least n12 +n22 +c+ni2 , then H is a subgraph of G. We prove this conjecture for all sufficiently large n.
(4) We prove a general theorem which we call the Decomposition theorem. Using this theorem one can obtain many known results quite easily. As application of this theorem we show how to obtain a proof of the Alon-Yuster conjecture. The Alon-Yuster conjecture states that for every graph, H, on h vertices there is a constant C( H) such that if G is any graph on n = Nh vertices with minimum degree 1-1cH n+C H then G contains vertex disjoint copies of H. This conjecture was first solved by Komlos, Sarkozy and Szemeredi.
In the Part II of the thesis we consider a combinatorial problem on strings. This problem arises in Molecular Biology and has practical applications.
Let Σ be a finite alphabet and x∈Sn. A string y∈Sm is said to be k-dissimilar to x, if no k length substring of x is equal to any k length substring of y. We present an Onlogn algorithm which on input x∈Sn and an integer m≤n outputs an integer k and y∈Sm such that: (1) y is k-dissimilar to x. (2) There does not exist a string z of length m which is k-1 dissimilar to x.
The algorithm is practical and has been used by molecular biologist to design DNA for certain experiments.