什么是旗代数?  

What Is a Flag Algebra?

作　　者：Alexander A.Razborov 李乔(译) 陆柱家(校) 

机构地区：[1]芝加哥大学计算机科学系 [2]不详

出　　处：《数学译林》2019年第3期275-278,共4页MATHEMATICS

摘　　要：在试图回答标题所提问题前,先稍许讨论一下另一个问题是有用的:发明旗代数是为了解决哪一类问题?让我们考察3个类似的组合难题.设我们有一个(简单,无向)图,其顶点数是n.为了保证图中有三角形,最少的边数m(作为n的函数)是多少?此外,假定m超过这个阀值,这时图中至少有多少三角形?再进一步,如把图改成(简单)3-图,即n个顶点集合的一些无序三元子集(称为3丈)的集,我们再问,边数m至少多大才能保证有4个顶点,使得它们的4个三元子集都是此3-图的3-边?

关 键 词：顶点数 顶点集合 三角形 代数 子集 三元 

分 类 号：G63[文化科学—教育学]