Erd?s－Ko－Rado 定理的一个新证明

Erds-Ko-Rado定理是极值组合学里非常基础也非常重要的定理,它给出了自相交有限子集族里基数大小的上界的一个非常好的估计,在集合论和图论等相关领域有很多应用.证明方法很多,既有组合方面的,也有代数方面的.通过构建某些集合族间的2种单射以及一些相关的性质,诸如自相交性,给出了该定理的另一种证明方法.     

拉姆赛型问题的研究及应用

通过对一道数学竞赛题的讨论，研究了拉姆赛数，给出了与拉姆赛数相关的4个定理2个推论，最后由实例给出了拉姆赛型问题的一些解法．     

A new bound for the ratio between the 2-matching problem and its linear programming relaxation

Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation, the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem. Received August 26, 1996 / Revised version received July 6, 1999? Published online September 15, 1999     

50余年来的数学科研工作成果综述

1945-2001年主要研究领域为组织分析、渐近分析、函数逼近论、计算方法与计算组合数学。这篇自述报告只就高维渐近积分定理、算子半群理论第一指数公式的量化定理、大范围收敛迭代方法、快速振荡函数积分的渐近展开、Gould-Hsu反演公式、广义Mǒbius反演理论、广义Stirling数的统一研究等成果略作介绍。     

信息调度中的一个组合问题

研究了多用户信息服务中的实时调度问题,在基于双向扫描调度模型的基础上使用组合分析技术,对使用扫描算法进行调度时造成的服务延迟这一组合问题进行定量分析,推导出了计算延迟的递推公式.数值计算表明平均延迟时间随用户数的增长率近于常数.该公式可用于对双向扫描算法服务性能的评价.     

从完全基因组出发建立原核生物亲缘关系和分类系统时遇到的数学问题

我们课题组近10年所发展的组分矢量(CVTree)方法,已经成为从完全基因组出发而不使用序列联配来构建细菌亲缘关系的有效手段.在整个生物分类学日益后继乏人的背景下,组分矢量(CVTree)方法伴随着基因组时代的发展,成为人人可以方便使用的微生物分类的定义性工具.本综述不讨论CVTree的生物学结果,而着重从非线性科学的角度,介绍我们在研究过程中所提出和解决的数学问题.这将涉及组合学、图论、形式语言学等离散数学的篇章.我们特别希望,本文所列举的一些尚未解决的数学问题能引发新的研究工作,使CVTree方法的理论基础更为坚实.     

More complete intersection theorems

The seminal complete intersection theorem of Ahlswede and Khachatrian gives the maximum cardinality of a $k$-uniform $t$-intersecting family on $n$ points, and describes all optimal families. In recent work, we extended this theorem to the weighted setting, giving the maximum ${\mu }_p$ measure of a $t$-intersecting family on $n$ points. In this work, we prove two new complete intersection theorems. The first gives the supremum ${\mu }_p$ measure of a $t$-intersecting family on infinitely many points, and the second gives the maximum cardinality of a subset of ${\mathbb{Z}}_m^n$ in which any two elements $x,y$ have $t$ positions $i_1,\dots ,i_t$ such that $x_{i_j}?y_{i_j}\in \{?(s?1),\dots ,s?1\}$. In both cases, we determine the extremal families, whenever possible.