可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）275-283www.elsevier.com/locate/entcs代数、图和θ马塞尔·K de Carli Silva部圣保罗大学计算机科学系加布里埃尔·科蒂尼奥部Minas Gerais巴西贝洛奥里藏特Chris Godsil2部滑铁卢大学Combinatorics andOptimization University of加拿大滑铁卢David E. 罗伯森部丹麦技术大学应用数学和计算机科学系Kongens Lyngby，丹麦摘要我们扩展团-团不等式，以前已知的持有图在关联计划和顶点传递图，图在齐次相干配置和1-走正则图。我们进一步将它推广到一个更强的不等式，它涉及到图的Lova′szθnumber，以及一些θ变式，包括等式的特征关键字：团-团不等式，矩阵-代数，Lov′aszθ函数，凝聚构形1电子邮件：mksilva@ime.usp.br。这项工作得到了国家发展委员会的部分支持。 423833/2018-9、456792/2014-7和477203/2012-4）。2杯Godsil非常感谢加拿大自然科学和工程委员会（NSERC）的支持RGPIN-9439。https://doi.org/10.1016/j.entcs.2019.08.0251571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。276M.K. de Carli Silva等人/理论计算机科学电子笔记346（2019）2751介绍用ω（G）表示图G中团的最大大小，用α（G）表示一个团的最大大小;一个团是一个独立的顶点集，也称为稳定集。想一个有一个大团和一个大团的图。一般来说，这两个子结构的大小与图的大小相比似乎没有（不明显的）限制。然而，如果图显示出高度的规则性或对称性，那么人们很快就会发现，大集团不能与大集团一起出现更具体地说，对于n个顶点的图G，它是距离正则的或点传递的，我们有α（G）ω（G）≤n。这就是所谓的集团-集团界限;例如见[8，第3章]。在本文中，我们观察到，一个更一般的框架，这些图和他们的团和coclique可以铸造是足够的证明团-coclique界。这出现在定理3.1和3.2以及推论4.1中。我 们 的 设 置 也 允 许 这 个 不 等 式 的 扩 展 到 一 个 更 强 的 不 等 式（whichturnouttobeanequality），在voving图和它的补图的Lov′aszthetanumber这在推论4.2中找到。 这些结果仅针对顶点传递图而已知，因此我们的贡献显著增加了满足所显示的性质的已知图的数量。在过去的一些工作中，与本文主题密切相关的主题已经完成。Godsil和Meagher[8]给出了属于关联方案的图中团和团的Dukanovic和Rendl [7]证明了点传递图及其补图的一些涉及θ的推广的等式Roberson [14]指出，我们可以以某种方式放松图是点传递的要求。我们的论文中的一些结果是在寻找哪些图满足这个放松的条件。使用正半有限性来寻找组合结构中的边界可以追溯到Delsarte它最近由Schrijver[16]在编码理论的背景下复兴，后来由Hobart [11]和Hobart和Williford [12]应用于一些连贯的配置。一些调查可以在[1]中找到。在所有情况下，主要的工具是这样一个事实，即一个半正定矩阵在某些矩阵代数中的投影仍然是半正定的。我们在引理2.5和2.6中探讨了这一事实，以建立我们的理论框架。2代数在复n×n矩阵的复向量空间Mn（C）中，用迹内积M，N<$= trMN<$.我们将研究矩阵n-代数，这意味着Cn × n中的线性子空间在常规矩阵乘积和取共轭转置下是封闭的。 一个矩阵 代数是 单的， 如果它没 有非平 凡的真 （双侧） 理想。 我们从Wedderburn定理在半单代数上的下列推论开始M.K. de Carli Silva等人/理论计算机科学电子笔记346（2019）275277我∗∗定理2.7]，或者[2，第1章]。定理2.1若A是矩阵代数，则A是简单矩阵的直和代数SA=EiA，（1）i=0其中{E0，...，Es}是中心的极小幂等元的正交基，A.这里我们依赖于这样一个事实[1，定理9.3]，即每个交换矩阵E-代数B都有矩阵E0，…，Es使得Ei ∈ Ei且E2= Ei，对于每个i且EiEj= 0，只要ii = j;这样的矩阵称为B的极小幂等元。给定一个矩阵M，我们将用M表示M在A上的正交投影。由于上面的分解，可以得出M是M在每个EiA上的投影之和。下面的事实也是众所周知的，例如见[1，推论9.1]。推论2.2一个正半有限矩阵在一个矩阵代数上的投影是正半有限的。从这里开始，我们假设A中的所有矩阵都有常数对角线。这种性质应称为A是均匀的。引理2.3若A是齐次矩阵λ-代数，则A中的所有01矩阵行和和列和都是常数。此外，若A包含不可约的01矩阵，则全1s矩阵J属于A.最后，如果A包含全1矩阵J，则A中所有矩阵的行和与列和相等，即J位于A的中心。证据设A∈ A是01矩阵.然后A<$∈ A，所以AA<$∈ A和A<$A∈ A。 AA的对角项是A的行和，AA的对角项是A的列和。因为A是齐次的，所以所有行和都相等，列和也是如此 现在如果A是不可约的，并且因为它的行和是常数，那么根据Perron-Frobenius理论，全1 s向量是1维子空间中的特征向量，因此J是A中的多项式，因此它属于A。现在的结果来自于注意到，对于所有M∈ A，MJ和JM的对角项分别是M的行和列和。这些是常数对角线，因为trMJ = trJM，所以这些对角线实际上相等。Q由于M<$→M<$是一个自伴算子，因此，M，N下面我们将在两种特殊情况下利用这一事实278M.K. de Carli Silva等人/理论计算机科学电子笔记346（2019）275nn2Pi，Pii=0i=0引理2.4设M是一个矩阵，A是一个包含I和J的齐次矩阵代数。 然后和trM = trM，tr JM= tr JM.是的。 由于I和J都是A，所以我们有I=I和J=J。Thus，trM=MQ下面我们展示如何在一个特殊但有用的情况下获得迹不等式引理2.5设A是包含I的齐次矩阵λ-代数。 设M和N是半正定n×n矩阵.设I = P0，P1，.Pd是代数A的正交基. 假设对于所有i = 0，<$M，Pi <$$>Pi，N <$<$≤ 0。然后N≤（trM）（trN）。此外，等式成立当且仅当对所有i = 0，<$M，Pi<$$>Pi，N <$= 0。证据 这是一个简单的计算：M.布吕德Pakistan，Pakistan普雷普，普雷普吴恩达i=0i iD=M，PiPi，N⟨M,I ⟩⟨I,N ⟩我，我...(trM）（trN）=.n平等的特征立即出现Q引理2.6设A是包含I和J的齐次矩阵λ-代数。 让M和N是正半有限n × n矩阵。然后N≥（trJM）（trJN）.此外，等式成立当且仅当M N是J的标量倍数。证据 根据引理2.3，全1s向量是A中所有矩阵的特征向量，并且J位于A的中心。 记作A = sEiA，如定理2.1所示。 则EiJ/= 0对于恰好一个索引i：如果EiJ=λiJ且EjJ=λjJ且λi/= 0λj，则EiEjJ = λiλjJ这意味着i = j，因为E0，.， E是极小幂等元。我们可以假定E0J/= 0。 由于CJ是单矩阵代数E0A的理想，我们发现E0A = CJ，因此我们可以假设E0= J。我≤M.K. de Carli Silva等人/理论计算机科学电子笔记346（2019）275279ΣSi=0i=0i=0设Mi表示定理2.1中M在每个EiA上的投影，对于N和Ni也是如此.然后S sM=Mi和N=Ni，矩阵Mi和Ni是半正定的，由推论2.2证明。此外，分解的正交性意味着，SMN =MiNi.i=0回想一下，半正定矩阵乘积的迹是非负的。因此trMN = trMiNi≥ trM0N0（trJM）（trJN）=n2。i=0等式成立当且仅当MiNi= 0对所有i0，相当于MN是J的标量倍数。Q将矩阵B和C的Schur（分量）积表示为B <$C。在下文中，我们将典型地考虑正半有限矩阵M和N，关于图G的邻接矩阵A和补图G的邻接矩阵A = J-I-A，满足以下两个条件之一：M<$A= 0且N<$A= 0，（A）MA≤0，NA = 0，NA ≥ 0。（B）3图现在我们给出两类满足上述引理性质的矩阵λ-代数的例子3.1齐次凝聚构形相干配置是非零01矩阵{A0，...，Ad}，满足以下性质：(i) Ai= J.(ii) 对于所有i ∈ {0，.，d}，如果Ai的一个对角项非零，则Ai是对角的。(iii) 配置是转置闭合的。(iv) AiAj是配置中矩阵的线性组合，对于所有i和J.连贯的配置自然地出现在设计理论、有限几何学、编码理论和有限群的表示它们最初是280M.K. de Carli Silva等人/理论计算机科学电子笔记346（2019）275ΣΣ≥”[10]中的“义”。当单位矩阵是构成构形的矩阵之一时，我们称这种构形是齐次的。当构成组态的关联图式的理论是巨大而丰富的，与组合数学的联系是压倒性的;例如，见[4]。从这里开始，我们假设{I = A0，...，Ad}是一个齐次相干配置。这些矩阵生成一个复代数，称为凝聚代数，我们用A表示。注意，这个代数是一个包含I和J的齐次矩阵n-代数。如果图的邻接矩阵是一个和，则它属于凝聚构形矩阵的形式的配置。所谓的距离正则图是在关联方案中发现（并生成）的图的标准示例。另一类例子来自点传递图--对应于图的自同构的置换矩阵形成一个群，它在Mn（C）中的交换子包含图的邻接矩阵，是一个齐次凝聚代数。设A是一个图的邻接矩阵，且属于由构造{I = A0，...，Ad}，由此得出，对于某个R∈ {1，...，d}，我们有因此，A=Ar.r∈RA=Ar，r∈R其中R={1， . ，d}\R. 更进一步，如果Ar=Ar，则r∈R蕴涵r∈R.因此，如果M和N是满足条件（A）和（B）之一的半正定矩阵，则可以得出，对于所有r∈，{1，.，d}，因此M，N，A及其基{A0，.，Ad}满足引理2.5的条件。应用引理2.3，2.5和2.6，我们得到下面的结果。定理3.1设A是一个连通图的邻接矩阵，该连通图属于齐次凝聚构形{I = A0，...，Ad}。设M和N是满足条件（A）或（B）的非零半正定矩阵。 然后（trJM）（trJN）n.(trM）（trN）此外，等式成立当且仅当M<$N <$是J的标量倍数，并且(A) 成立或（B）以这样的方式成立，即对于所有r/= 0，3.21-行走正则图（及其补图）一个具有邻接矩阵A的图G称为1-走正则的，如果对任意正整数k，Ak在对角线上和对应于A的元素上都是常数M.K. de Carli Silva等人/理论计算机科学电子笔记346（2019）275281≥A的支持。也就是说，对于任何正整数k，存在常数ak和bk，使得AkI = akI和Ak A = bkA。设G是1-行走正则的，A是它的邻接矩阵。例如，注意G必须是正则的，因为A2的对角线是常数。设A是由A和I生成的代数，即图G的邻接代数。这显然是一个矩阵代数。实际上，它是一个对称交换矩阵代数，因此Rn到A-模的分解就是它的同时对角化.考虑正交基I=A0，A=A1，A2，.，了dna例如，这可以通过将Gram-Schmidt应用于I，A，A2，...，了dna 1-行走正则性的相关结果是：当基是正交的且A的所有矩阵在I和A的支撑上是常数时，对所有k≥2，Ak<$I=0和Ak<$A= 0.现在设M和N是半正定矩阵，并假设（A）或(B) 保持。 则对所有k ≥ 1，Ak，N≤0。 因此，M，N，A及其基{A0，.，Ad}满足引理2.5和2.6的条件，因此我们有以下定理。定理3.2设A是1-路正则图的邻接矩阵. 设M和N是满足上述条件（A）或（B）的非零正半有限矩阵。然后（trJM）（trJN）n.(trM）（trN）此外，等式成立当且仅当M<$N <$是J的标量倍数，并且（A）成立或（B）成立，使得对于所有r/= 0，I= A0，A = A1，A2，...，Ad是G的邻接代数的正交基.4Thetas定理3.1和3.2的直接推论是所谓的团-团界限。设S是一个团，T是一个团，在一个图中，这是在一个齐次凝聚配置或1-行走正则。设χS和χT是它们各自的特征向量，并定义N=χSχηS和M=χTχηT。因此，M<$A= 0，N<$A= 0。因此，定理3.1或定理3.2适用，并且我们得到下面的结果，该结果在之前对于结合方案中的图或点传递图已经陈述过（例如参见[8，定理3.8.4]）。推论4.1设S是一个团，T是n个顶点的图中的一个团，该图要么是齐次凝聚配置的，要么是1-行走正则的。 然后|S||不|≤ n。282M.K. de Carli Silva等人/理论计算机科学电子笔记346（2019）275证据 这个不等式直接来自定理3.1或定理3.2。Q关于M和N是正半有限的并且满足（A）或（B）的条件允许这个结果的一个很好的推广。我们写X0，如果X是一个正半有限矩阵。Lova′szθ图参数θ（G）被定义为（参见[13]）以下半有限程序的最佳值G = max {G =J，X=：X=A = 0，tr X = 1，X0}.在公式中进行小的变化时，分别获得Schrijver theta[15]和Szegedy theta[17]函数：−（G）= max {<$J，X<$：X<$A = 0，tr X = 1，X≥ 0，X0}.G = max {G_J，X_j：X_j≤ 0，tr X = 1，X_0}.众所周知，由于这些θ的第一次出现，对于所有的图，在n个顶点上，我们有α（G）≤n-（G）≤n-（G）≤n+（G）≤x（G），（2）其中x（G）是G的色数;<$（G）<$（G）≥n和<$−（G）<$+（G）≥n，（3）对于点传递图，在（3本文的结果推广了（3）中关于同素凝聚构形图和1-行走正则图的等式情形。推论4.2设G是n个顶点的图，且G是齐次凝聚配置或1-行走正则的。然后（G）= n和（G）= n。证据设M和N是半正定矩阵，分别是G的最优解和G的最优 满足条件（A），因此定理3.1 或3.2适用。 因此n≥ <$（G）<$（G），则（3）表明等式成立。 对于矩阵N和M也可以得出同样的结论，它们分别是<$−（G）和<$+（G）的最优解，只要注意它们满足条件（B）。Q推论4.2意味着，如果M和N对于G1-行走正则或在齐次相干构形中，对于G 1-行走正则或对于G1-行走正则或对于G 2-行走+（G）是最优的，则引理2.5和引理2.6中的等式特征成立。有趣的是考虑我们开发的工具和框架是否可以用于加强涉及其他theta变体的类似不等式，例如[7]和[14]中的不等式，以及其他半有限程序的层次结构（参见，例如，[9]）。M.K. de Carli Silva等人/理论计算机科学电子笔记346（2019）275283引用[1] 安霍斯，M。F.和J. B. Lasserre，编辑，URLhttp://link.springer.com/10.1007/978-1-4614-0769-0[2] Arveson，W.，39，Springer Science Business Media，2012.[3] Bachoc， C.， D. C. Gijswijt， A.Schrijver和 F.Vallentin， Invariant semide finite programs ， in ：Handbook on semide finite，conic and polynomial optimization，Internat.欧泊爵士管理科学研究166，Springer，New York，2012 pp. 219-269URLhttps://doi.org/10.1007/978-1-4614-0769-0_9[4] Brouwer，A. E、A. M. Cohen和A. Neumaier，[5] Cohn，P.M.，[6] Delsarte ， P. ， “ 编 码 理 论 的 关 联 方 案 的 代 数 方 法 ”， 博 士 。 论 文 ， Universit'eCatholiquedeLouvain（1973）.[7] 杜卡诺维奇岛和F.李文，余正规划的稳定性和色数的界，数学程序。121（2010），pp. 249-268。URLhttps://doi.org/10.1007/s10107-008-0233-x[8] G o dsil，C.和K.MEagher，“Erd Eagos-Ko-Rado theorems ： a lgeological approa c hes”，《高等数学中的Ca m bridge研究》149，剑桥大学出版社，剑桥，2016年，xvi+335页。URLhttps://doi.org/10.1017/CBO9781316414958[9] 你好，我也是。 和M. 张文，张文，等.计算机辅助设计中的计算机辅助设计.北京：清华大学出版社，2000，21（1）：117 - 118. OPTIM。19（2008），pp. 572-591.URLhttps://doi.org/10.1137/050648237[10] Higman，D. G.，连贯的配置。I.普通表示论，几何学4（1975），pp. 1-32网址https://doi.org/10.1007/BF00147398[11] Hobart，S.一、相干配置子集的界限，Michigan Math. J.58（2009），pp. 231-239网址https://doi.org/10.1307/mmj/1242071690[12] Hobart，S. A. Williford，Tightness in subset bounds for coherent configurations，J. Algebras Combin.39（2014），pp. 647-658URLhttps://doi.org/10.1007/s10801-013-0459-4[13] 洛瓦兹湖关于图的香农容量，IEEE Trans.告知。Theory25（1979），pp.一比七URLhttps://doi.org/10.1109/TIT.1979.1055985[14] Roberson，D. E、 Conic formulations of graph homomorphisms，J. Algebras Combin. 43（2016），pp.877-913URLhttps://doi.org/10.1007/s10801-016-0665-y[15] S c hrij ver，A.， Delsarte和Lov'aszbounds的比较，IEEE Trans。告知。 Theory25（1979），pp. 425-429URLhttps://doi.org/10.1109/TIT.1979.1056072[16] Schrijver ， A. ， NewCodeUpperBoundsFromtheTerwilligerAlgebraandSemideFiniteProgramming，IEEE Transactions on Information Theory51（2005），pp. 2859-2866。URLhttp://ieeexplore.ieee.org/document/1468304/[17] Szegedy ， M. ， AnoteonthethetanumberberofLov′aszandthegeneralizedDelsartebound ，in ：Proceedingingsof the 35th Annual IEEE Symposium on Foundations of Computer Science，1994.
我的内容管理
展开
