论文标题
1-2-3的猜想适用于足够大的图形
The 1-2-3 Conjecture holds for graphs with large enough minimum degree
论文作者
论文摘要
一个简单的图通常不包含相等程度的相邻顶点。这尤其适用于常规图中所有邻居的所有对，而可以预期会有很多这样的对，例如在许多随机模型中。是否有通用常数$ k $，例如$ k = 3 $，以便通过将其选定的边缘吹入最多$ k $并行边缘，从任何给定的连接图中始终从任何给定连接的图形上处理此类对？这个问题首先是由Karoński，üuczak和Thomason提出的，他们等同地询问是否可以将重量分配给每个此类图的边缘1,2,3 $ $ 1,2,3 $，以便相邻的顶点获得不同的权重学位 - 事件重量的总和。这个基本问题通常被称为当今的1-2-3猜想，并且已在多个论文中解决。到目前为止，重量$ 1,2,3,4,5 $就足够了[J.组合。理论ser。 B 100（2010）347-349]。我们表明，如果只有图形的最低度$δ$足够大，即$δ=ω（\logδ）$，则该猜想才能保持，其中$δ$表示图的最大程度。我们的概率证明背后的主要思想依赖于将随机变量与特殊且精心设计的分布与给定图的大多数顶点相关联，然后根据确定性或随机方式为这些变量的值选择重量的重量。
A simple graph more often than not contains adjacent vertices with equal degrees. This in particular holds for all pairs of neighbours in regular graphs, while a lot such pairs can be expected e.g. in many random models. Is there a universal constant $K$, say $K=3$, such that one may always dispose of such pairs from any given connected graph with at least three vertices by blowing its selected edges into at most $K$ parallel edges? This question was first posed in 2004 by Karoński, Łuczak and Thomason, who equivalently asked if one may assign weights $1,2,3$ to the edges of every such graph so that adjacent vertices receive distinct weighted degrees - the sums of their incident weights. This basic problem is commonly referred to as the 1-2-3 Conjecture nowadays, and has been addressed in multiple papers. Thus far it is known that weights $1,2,3,4,5$ are sufficient [J. Combin. Theory Ser. B 100 (2010) 347-349]. We show that this conjecture holds if only the minimum degree $δ$ of a graph is large enough, i.e. when $δ= Ω(\logΔ)$, where $Δ$ denotes the maximum degree of the graph. The principle idea behind our probabilistic proof relies on associating random variables with a special and carefully designed distribution to most of the vertices of a given graph, and then choosing weights for major part of the edges depending on the values of these variables in a deterministic or random manner.
