Research on extremal structures in combinatorics

(1)研究了多相交族的极值结构。我们发展了P. Frankl提出的随机漫步法。我们的一个新想法是将非均匀超图的加权大小（p-weight）与k-均匀超图联系起来。这里p和k/n是对应的，其中n是超图的顶点数。我们确定了r向t相交的k-一致超图的最大尺寸，这是Erdos-Ko-Rado定理的推广。我们还确定了非平凡t相交族和t相交Sperner族的最大大小。这些都是基于与P. Frankl的合作。(2)给出了Szemeredi、Furstenberg和Katznelson等人最初得到的一些组合划分定理的密度版本的替代证明。这是与v.r odl， M. Schacht， E. Tengan合作的作品。我们的证明是基于Gowers和Nagle-Rodl-Schacht-Skokan将Szemeredi的正则引理推广到超图上独立得到的一个极值超图结果。(3)求k-一致超图的整数包装箱数问题是np困难问题。而分形装箱数的求则可以在多项式时间内完成。我们给出了整数包装箱数用分数包装箱数表示的下界。

(1) We study extremal structures of multiply intersecting families. We developed the random walk method introduced by P. Frankl. One of our new ideas is to associate weighted size (p-weight) of non-uniform hypergraphs with k-uniform hypergraphs. Here p and k/n are corresponding, where n is the number of vertices of hypergraphs. We determined the maximal size of r-wise t-intersecting k-uniform hypergraphs, which is a generalization of the Erdos-Ko-Rado theorem. We also determined the maximal size of nontrivial t-intersecting families and t-intersecting Sperner families. These were based on a joint work with P. Frankl.(2) We gave alternative proofs of density version of some combinatorial partition theorems originally obtained by Szemeredi, Furstenberg and Katznelson. This was a joing work with V. Rodl, M. Schacht, E. Tengan. Our proofs are based on an extremal hypergraph result which was independently obtained by Gowers and Nagle-Rodl-Schacht-Skokan by extending Szemeredi's regularity lemma to hypergraph.(3) The problem of finding the integer packing number of a k-uniform hypergraph is an NP-hard problem. Find the fractinal packing number however can be done in polynomial time. We gave a lower bound for the integer packing number in terms of the fractional packing number.