Lovász条件下LLL算法最简复Givens矩阵形式的研究

为了解决复数域下基于QR分解的LLL(A.K.Lenstra,H.W.Lenstra and L.Lovász)算法中复Givens旋转矩形式不统一的问题,文章从复数域下原始LLL算法中Gram-Schmidt系数与QR分解的上三角矩阵R中元素之间的关系出发,证明了上三角矩阵R的元素与Gram-Schmidt系数以及Lovász条件之间的等价的关系;从复数的指数形式出发,推导出2种适合LLL算法的复Givens旋转矩阵形式,并证明只有其中一种符合Lovász条件下复Givens旋转矩阵形式。仿真结果表明,采用基于QR分解的复数域LLL算法的MIMO系统相比采用基于Gram-Schmidt正交化LLL算法的MIMO系统具有更好的误比特率性能。

关于外平面图的Lovász猜想

1968年,Lovász提出了如下猜想:若G不是完全图,并且x(G)=m+n-1(其中m≥2,n≥2),则存在G的不相交子图G_1和G_2,使得x(G_1)=m和x(G_2)=n. 本文证明了对于x(G)=3且y》4的外平面图G,Lovisz猜想成立.

Lovász延拓权值下的伪泊松混合分布的风险期望模型

本文在风险损失量为自然数且服从泊松分布的条件下,将泊松分布进行截断和均化的处理生成伪泊松分布,然后根据有限可数混合分布的表达式,利用从集函数转换而来的多线性形式的Pseudo-Boolean函数的Lovász延拓得到新的权值并构建伪泊松混合分布,最后根据期望的定义和性质得到相应的伪泊松混合分布的风险期望模型.该模型为今后研究混合分布在风险分析中的应用提供了依据.

在线社交网络中点阻塞策略下虚假信息关注度

在线社交网络中的信息影响着人们的观点或看法,混杂在其中的虚假信息必然对人们的判断和决策产生误导.人们对虚假信息的关注度越高就越容易受到虚假信息的误导,从而做出非理性甚至激进的行为.为构建和谐的网络生态环境,本文探索了点阻塞策略下虚假信息关注度最小化问题以及最小化用户被虚假信息激活时对虚假信息的总关注度.首先,考虑用户对虚假信息的关注度构建一个关注度级联模型,并借助库伦定律来刻画虚假信息扩散过程中用户对虚假信息关注度的演化.其次,证明了点阻塞策略下虚假信息关注度最小化问题的复杂性以及该问题目标集函数的非次模性和非超模性.然后,将关注度最小化问题转化为关注度下降最大化问题,借助离散函数的连续化技术以及集函数的凹闭合函数设计了一种近似投影次梯度算法.最后,在三个真实的数据集中验证了本文构造算法和模型的有效性,实验模拟结果表明了本文开发的算法优于现存的启发式算法,并且得出用户对虚假信息的关注度是影响虚假信息治理的重要因素.

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

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

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

提出图的星边星-全染色的概念,图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,这里[.]*表示上取整.

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

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

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

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

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

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

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

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

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

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

距离限制下的点可区别全色数的一个上界

图G的一个正常全染色被称作D(β)-点可区别全染色,如果G中距离不超过β的任意两点有不同的色集,其中,每个点的色集由该点和其邻边的颜色所组成.本文得到了图G的一个D(β)-点可区别全色数的新上界.

图的Smarandachely邻点无圈边色数的一个上界

提出了图的Smarandachely邻点无圈边染色的概念,讨论了图的Smarandachely邻点无圈边染色与邻点可区别无圈边染色之间的关系,并运用概率方法得到了图G的Smarandachely邻点无圈边色数的一个上界,其中G为无孤立边的图.

点可区别全色数的一个界

图G的一个正常全染色被称作点可区别全染色,如果G中任意两个点的色集合不同,其中每个点的色集合包含该点及其关联边的颜色。在点可区别全色数界(χvt(G)≤|V(G)|+2)的基础上,应用概率的方法得到了阶数为n,且无孤立边的简单图G的点可区别全色数的一个较小上界。

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

提出了图的邻点可区别星边染色及邻点可区别星边色数χ'ass(G)的概念,并用Lovász局部引理证明了若G=(V,E)是一个最小度为δ(G)≥3的简单无向图,则χ'ass(G)≤「32Δ32?。

图的邻点可区别全染色的渐近性质

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同,其所用的最少颜色数称为邻点可区别全色数.张忠辅老师猜想:对于|V(G)|≥3的连通图G,其邻点可区别全色数最多不超过△(G)+3.用概率方法证明了对简单图G,△≥14,有χ_(at)(G)≤△+C,其中C≥10^(26)+1.

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

图G的一个正常全染色被称作点可区别全染色,如果G中任意两个点的色集合不同,其中每个点的色集合包含该点及其关联边的色.应用概率的方法得到了n个点的k-正则图G的一个点可区别全色数的较小上界.

随机图的f-染色的分类Ⅱ

随机图G(n,p)是具有n个标号的顶点的图,并且图中的每一对顶点以概率p被随机且独立地选择为图G的边.对于有顶点集V和边集E的简单图G=(V,E),G的f-染色c是广义的边染色,使每个颜色类在任一顶点v上至多出现f(v)次,其中f(v)是分配给v的正整数.在这篇文章中,我们给出随机图G(n,p)是f-第一类的一个充分条件.

Linear Arboricity of Regular Digraphs

A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.