組合せ論・グラフ理論における擬確率的手法

组合学和图论中的伪概率方法

• 批准号: 14740065
• 负责人: 石上 嘉康
• 金额: $ 2.5万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14740065/
• 关键词: doubly-stochastic matrix; グラフ理論; 組合せ論; 擬確率; 組み合わせ理論; アルゴリズム

平成16年度も、平成15年度に引き続き、組合せ論・グラフ理論の特に極値問題において、擬確率的手法の研究を行った。擬確率的手法を駆使する際に、グラフなどの離散構造を標準化することによって、doubly-stochastic行列またはそれに準ずる構造に置き換えることができる。そのためにdoubly-stochastic行列の研究は基本的で極めて重要である。また、固有値の分布が、その離散構造の擬確率性を特徴付けることが知られている。doubly-stochastic行列の固有値の分布について1980年代にMincが提起した問題に対して、反例を見つけ、さらにより多くの反例の分布状況を調べたが、それほど多くは無く、かなり稀な場合であることがわかった。上の研究に関連して、やはりdoubly-stochastic行列の成果として知られ、グラフ理論をはじめとする組合せ論において広く応用されているBregmanの定理がある。この定理は、80年代に拡張されたものが発表されているが、特定の次元のものに限られていた。そのために、応用の範囲が限られていたが、それを一般次元の場合へと拡張することに成功した。このことによって、より広い分野へ応用されることが期待される。また、擬確率的手法を強化することにつながると思われる。離散数学において基本的な擬確率的現象を力学系理論的視点及び理論計算機科学的視点から特徴付ける成果を得た。

In 2016 and 2015, we conducted research on methods for introducing, combining, analyzing, and solving special problems in theory. The method of accuracy is to standardize the discrete structure of the system, and to standardize the structure of the system. The study of double-stochastic ranks is fundamental and extremely important. The distribution of intrinsic values and the quasi-deterministic characteristics of discrete structures are discussed. The distribution of inherent values of double-stochastic arrays in the 1980s was a problem of Minc raising, counterexamples, counterexamples, and the distribution of counterexamples was adjusted. Bregman's theorem is the result of a double-Stochastic theory. This theorem is based on the theory that in the 1980s, there was a limit to the number of dimensions. For example, if you want to use a computer, you can use a computer. This is the first time I've ever seen you. The method of accuracy is strengthened. Discrete mathematics, basic accuracy, phenomena, theoretical viewpoints of mechanical systems, theoretical computer science, and results.

项目成果

Ishigami, Yoshiyasu: "Almost-spanning subgraphs with bounded degree in dense graphs"European J. Combin. 23, no.5. 583-612 (2002)

Ishigami, Yoshiyasu：“密集图中具有有界度的几乎跨越子图”European J. Combin。

Ishigami, Yoshiyasu: "Proof of a conjecture of Bollobas and Kohayakawa on the Erdos-Stone theorem"J. Combin. Theory Ser. B. 82, no.2. 222-254 (2002)

石上义保：“Bollobas 和 Kohayakawa 关于 Erdos-Stone 定理的猜想的证明”J.

Y.Ishigami, J.Tao: "Vertex-disjoint cycles containing prescribed vertices"Journal of Graph Theory. 42・4. 276-296 (2003)

Y.Ishigami，J.Tao：“包含指定顶点的顶点不相交循环”图论杂志 42・4（2003）。

Ishigami, Yoshiyasu: "A common extension of the Erdos-Stone theorem and the Alon-Yuster theorem for unbounded graphs"European J. Combin.. 23, no.4. 431-448 (2002)

Ishigami，Yoshiyasu：“无界图的 Erdos-Stone 定理和 Alon-Yuster 定理的常见扩展”European J. Combin.. 23，第 4 期。