The size-Ramsey number of trees
The size-Ramsey number of trees
复制标题
树的大小-拉姆齐数
DOI：
10.1007/bf02808204
复制
发表时间：
1995
影响因子：
1
通讯作者：
Y. Kohayakawa
中科院分区：
文献类型：
--
作者：
P. Haxell;Y. Kohayakawa
如果G和H是图，则记G →（H）2，如果G的边的任意2-着色中包含H的单色副本。图H的size-Ramsey数（H）是当G →（H）2时，图G可能具有的最小边数。假设T是一棵有序树|不|≥2，且Δ 0，t1是二部图T的顶点类的基数，Δ（T）是T的最大度。此外，设Δ0、Δ1是各个顶点类中的顶点的度的最大值，并且设β（T）=T0Δ0+t1Δ1。Beck [7]证明了β（T）/4≤re（T）=O{β（T）（log|不|）12}，改进了他[6]之前的结果，即thatre（T）≤Δ（T）|不|（日志|不|）12.在[6]中，Beck证明了T =O{Δ（T）|不|在[7]中，他提出了一个更强的猜想：β（T）=O{β（T）}。在这里，我们证明了第一个命题，并通过证明threshold（T）=O{β（T）logΔ（T）}来非常接近于证明第二个命题。
IfG andH are graphs, let us writeG→(H)2 ifG contains a monochromatic copy ofH in any 2-colouring of the edges ofG. Thesize-Ramsey numberre(H) of a graphH is the smallest possible number of edges a graphG may have ifG→(H)2. SupposeT is a tree of order |T|≥2, and lett0,t1 be the cardinalities of the vertex classes ofT as a bipartite graph, and let Δ(T) be the maximal degree ofT. Moreover, let Δ0, Δ1 be the maxima of the degrees of the vertices in the respective vertex classes, and letβ(T)=T0Δ0+t1Δ1. Beck [7] proved thatβ(T)/4≤re(T)=O{β(T)(log|T|)12}, improving on a previous result of his [6] stating thatre(T)≤Δ(T)|T|(log|T|)12. In [6], Beck conjectures thatre(T)=O{Δ(T)|T|}, and in [7] he puts forward the stronger conjecture thatre(T)=O{β(T)}. Here, we prove the first of these conjectures, and come quite close to proving the second by showing thatre(T)=O{β(T)logΔ(T)}.