局部引理及其在(r，s)-SAT问题中的应用

一般说来,寻找满足一定结构性质的对象结构是困难的。概率方法提供了解决此类问题的途径:证明满足一定结构性质的对象的概率大于零。在概率方法中,局部引理是一个关键技术。本文介绍了局部引理的基本原理和使用方法,并将其应用到估计(k,s)-SAT问题中临界函数的下界。

洛瓦兹局部引理的新变种及其应用

洛瓦兹局部引理是组合数学和概率论中的重要工具,其最主要的用途之一是证明当约束之间"弱相关"时,满足复杂约束的组合对象存在.自从1975年Erdos和Lovasz提出洛瓦兹局部引理以来,局部引理在组合数学、理论计算机和物理学等领域已经有了很多应用.近年来,为了扩展局部引理的应用范围,人们提出了很多新版的局部引理,尤其是在构造版本局部引理上取得了重大的突破.本文将综述局部引理近年来最新的研究进展,包括几种最主要的局部引理变种以及它们在计算机科学和物理学中的应用.特别的,我们将给出抽象版本、Lopsided版本、变量版本和量子版本局部引理紧的条件,并讨论抽象版本紧的条件同统计物理、量子版本紧的条件同量子物理之间的联系.同时,我们还将以布尔可满足性问题和量子可满足性问题为例,说明局部引理在证明问题有解、找到问题的解以及对问题的解进行计数和采样等方面的应用.

图的邻点可区别Ⅵ-全色数的一个上界

根据图的邻点可区别Ⅵ-全染色的定义,用概率方法研究了一般图的邻点可区别的Ⅵ-全色数的一个上界.如果δ150√ln,则χviat(G)(G)+1+2√ln,这里δ(G)表示图G的最小度,(G)表示图G的最大度.

图的邻点可区别全色数的一个上界

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同.本文用概率方法得到了邻点可区别全色数的一个上界.

图的Smarandachely邻点星边染色

提出了图的Smarandachely邻点星边染色的概念,讨论了圈、轮、扇的Smarandachely邻点星边染色.并运用概率方法得到了图G的Smarandachely邻点星边色数的一个上界,其中G为无孤立边的图.

点可区别全色数的一个上界

设G是简单图,f是从V(G)∪E(G)到{1,2,,k}的一个映射.对每个u∈V(G),令C(u)={f(u)}∪{f(uv)|v∈V(G),uv∈E(G)}.如果f是k-正常全染色,且对任意u,v∈V(G)(u≠v),有C(u)≠C(v),那么称f为图G的k-点可区别全染色(简记为k-VDTC).数χvt(G)=min{kG有k-VDTC}称为图G的点可区别全色数.通过应用概率方法,证明了对任意最大度Δ≥2的图G,χvt(G)≤32(Δ+1).

图的2-强边色数的上界(英文)

本文研究了图的2-强边色数的上界.利用图染色的概率方法中的一般局部引理,得到了3≤Δ≤730时,χs(G,2)≤2Δ+1,推广了参考文献[11。

图的星边星-全色数的一个上界

提出图的星边星-全染色的概念,图G的一个正常全染色被称为星边星-全染色,如果对G中点进行星染色,边进行星边染色.并定义图的星边星-全色数,记为χsTs(G).用构造染色的方法给出一些特殊图(路,圈,轮,扇,完全图)的星边星-全色数.同时运用概率方法给出满足一定条件的图G的星边星-全色数的一个上界,即若图G的最大度Δ(G)≥30,则χsTs(G)≤24(Δ-1)3/2.

一类有向图的星边弧染色

提出了有向图的星边弧染色的概念,并定义了有向图D的星边弧色数,记为χ珗s′(D).运用Lovsz局部引理证明了若有向图D=(V,A)的最大出度Δ+与最大入度Δ-满足线性关系Δ+=kΔ-(Δ(D)≥7,k>0),则χs′(D)≤161+k21+kΔ[]32,这里[.]*表示上取整.

图的星边色数的一个新的上界

图的着色问题是图论中的一个重要问题,图论领域的诸多学者研究了图的各种着色.运用Lovsz局部引理,研究了图的星边着色(图G的星边着色是G的一个正常的边着色,并且使得G中无长为4的路是2-边着色的;图G的星边色数是G的所有星边着色中所使用的最小颜色数,记为χ'se(G)),并证明了最大度为Δ(Δ≥2)的简单无向图G的星边色数新的上界为χ'se(G)≤「9(Δ-1)3/2?.

图的D(2)-点可区别边色数的一个上界

用图的概率方法中的赋权局部引理得到最大度不小于5的图的D(2)-点可区别边色数的一个上界是4(2d4-d3-4d2+5d-1)d-1,这里d是图G的最大度.

概率方法讨论图的点可区别边色数的上界

图的点可区别边染色是一个满足任意顶点色集合不相同的正常边染色,将所用的最少颜色数称为图的点可区别边色数.应用第一矩量原理和Lovász局部引理给出了图的点可区别边色数的两个上界.

图的无圈全色数的一个上界

图G一个正常全染色f被称为无圈全染色,若G中无2-色圈.图G的无圈全色数,标记为χaet'(G),是图G的无圈全染色中所用的最少颜色数.在这篇论文中,证明了若G是一个Δ≥3的图,那么χaet'(G)≤32Δ,这里Δ是G的最大度.

图的邻点可区别无圈边染色

提出了邻点可区别无圈边染色的概念及其相关猜想,并证明了对于一个没有孤立边的图G,如果它的邻点可区别边染色数χ′as(G)=ε,那么存在一个常数r,如果围长g(G)≥rΔlogΔ,那么G的邻点可区别无圈边染色数至多为ε+1.

图的邻点可区别无圈边染色的渐近性质

对无孤立边的简单图G,和G的一个k-正常边染色法,使得G中任意的圈上的边至少出现三种不同颜色且G中任意两相邻的点所关联的边的色集合不同时,称为G的k-邻点可区别无圈边染色法;G中k-邻点可区别无圈边染色法中最小的k,称为邻点可区别无圈边色数。本文使用Lova′sz局部引理,得到了邻点可区别无圈边色数的一个上界。

图的邻点可区别无圈边染色

对无孤立边的简单图G,设G是一个正常边染色,如果G中任何两种颜色导出的子图是森林,即G中没有双色圈,且相邻点所关联的色集合不同,则称之为图G的邻点可区别无圈边染色。本文应用Lovász局部引理,即概率的方法确定了图G的一个邻点可区别无圈边染色的上界。

图的邻点可区别Ⅴ-全色数的一个上界

用概率方法中的Lovász局部引理证明了当δ≥75(ΔlnΔ)^(1/2)时,图的邻点可区别Ⅴ-全色数的上界是Δ+2+(ΔlnΔ)^(1/2).

点可区别边色数的一个上界

设G是简单图,f是从V(G)∪E(G)到{1,2,…,k}的一个映射.对每个u∈V(G),令C(u)={f(uv)|v∈V(G),uv∈E(G)}.如果f是k-正常边染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别边染色(简称为k-VDEC).数′s(G)=min{k|G有k-VDEC}称为图G的点可区别边色数.本文通过应用概率方法,证明了对任意最大度△≥2的图G,s′(G)≤16△.

图的邻点可区别正常边染色

图的邻点可区别正常边染色是指图G的一个正常边染色f使得任意相邻两点的着色集合不同.针对染色色数的上界进行研究,通过Vizing定理以及Lovasz一般局部引理,用概率方法得到了邻点可区别正常边染色色数的一个较好的上界Δ+4.

图的2-强点可区别全色数的上界

图的2-强点可区别全染色是满足2-距离以内的点可区别的正常全染色,其中色集合为点及其关联元素所染颜色构成的集合.图的2-强点可区别全色数是满足2-强点可区别全染色所用的最小颜色数.应用Lovász局部引理得到了图G的2-强点可区别全色数的上界.确切地,对不含孤立边的简单图G都有χ2-svdt(G)≤35d^2,其中d为G的最大度.