Research on extremal structures in combinatorics

组合数学中的极值结构研究

基本信息

批准号：
16340027
负责人：
TOKUSHIGE Norihide
金额：
$ 5.22万
依托单位：
University of the Ryukyus
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2007
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16340027/
关键词：
Extremal set theory multiply intersecting families random walk Szemeredi regularity lemma regularity method packing Erdos-ko-Rado theorem ランダムウォーク Szemeredi regularity lemma L-system integer packing

项目摘要

(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.

(1)我们研究多重相交族的极值结构。我们开发了 P. Frankl 提出的随机游走方法。我们的新想法之一是将非均匀超图的加权大小（p-权重）与 k-均匀超图相关联。这里p和k/n是对应的，其中n是超图的顶点数。我们确定了 r 方向 t 相交 k 一致超图的最大尺寸，这是 Erdos-Ko-Rado 定理的推广。我们还确定了非平凡 t 相交族和 t 相交 Sperner 族的最大大小。这些是基于与 P. Frankl 的联合工作。(2) 我们给出了最初由 Szemeredi、Furstenberg 和 Katznelson 获得的一些组合划分定理的密度版本的替代证明。这是与 V. Rodl、M. Schacht、E. Tengan 的合作作品。我们的证明基于极值超图结果，该结果是由 Gowers 和 Nagle-Rodl-Schacht-Skokan 通过将 Szemeredi 正则引理扩展到超图而独立获得的。 (3) 求 k-均匀超图的整数包装数的问题是一个NP 难题。然而，找到分形堆积数可以在多项式时间内完成。我们根据分数包装数给出了整数包装数的下界。