权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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.弗兰克尔。(2)给出了Szemeredi、Furstenberg和Katznelson等人提出的组合分拆定理的密度证明。这是一个joing工作与V. Rodl，M。Schacht，E.天安我们的证明是基于Gowers和Nagle-Rodl-Schacht-Skokan通过将Szemeredi的正则性引理推广到超图而独立得到的一个超图极值结果。(3)求k-一致超图的整数包装数是一个NP-难问题。然而，找到分数包装数可以在多项式时间内完成。利用分数填充数给出了整数填充数的一个下界。