近日,山东师范大学张霞教授团队在国际知名期刊《Acta Mathematicae Applicatae Sinica, English Series》在线发表了题为“Bipartite Turán problem on complete bipartite graphs”的研究论文。山东师范大学硕士研究生王兰馨为论文第一作者,张霞教授为论文通讯作者。
二部图兰问题研究Km,n中不含指定子图H的生成子图的最大边数(记作ex(m,n; H))。与之密切相关的是Zarankiewicz问题,它研究Km,n中不含定向嵌入子图H的生成子图的最大边数(记作z(m,n; H))。这两类问题都是极值图论研究的经典问题,即使对H为完全二部子图的情形,也都没有得到完全解决。容易看出,两个值满足关系ex(m,n; H)≤z(m,n; H)。1982年,Erdős和Simonovits猜想ex(m,n; H)和z(m,n; H)同阶,该猜想也是广泛开放的。
张霞团队围绕H为完全二部子图的子问题展开研究。max{m,n} < s + t的情形,已于2007年被西班牙学者Balbuena, García-Vázquez, Marcote和Valenzuela 在期刊《Discrete Mathematics》上发表论文中完全解决。对于max{m,n}≥s+t的情形,王兰馨和张霞借助(0, 1)-矩阵工具和极图构造法对三个情况确定了ex(m,n; Ks,t)的值,并证明ex(m,n; Ks,t)=z(m,n; Ks,t)。特别地,她们对max{m,n}=s+t的情形给予了完整解决。
该论文推广了Balbuena, García-Vázquez, Marcote和Valenzuela 2007年的结果,并在上述三个情况下对Erdős和Simonovits的猜想进行了正面回应。该研究获得国家自然科学基金、山东省自然科学基金等项目的资助。