石上 嘉康
| 情報学専攻 | 准教授 |
| Ⅱ類（融合系） | 准教授 |
研究者情報
研究活動情報
受賞
論文
MISC
- 離散構造の中の擬ランダム性（Szemerediの一様化補題、ランダムサンプリング、プロパティテスト、ラムゼー理論）
出版日 2008年, 第４回組合せ論若手研究集会 - Quasi-randomness in discrete structures (Szemeredi's regularity lemma, random samplings, property tests, Ramsey theory)
出版日 2008年, 4th combinatorics seminar for young researchers - Linear Ramsey Numbers for Bounded-Degree Hypergrahps
Yoshiyasu Ishigami
出版日 2007年08月15日, Electronic Notes in Discrete Mathematics, 29巻, 掲載ページ 47-51, 英語, 1571-0653, 34547660411 - Linear Ramsey Numbers for Bounded-Degree Hypergraphs
出版日 2007年, 29巻, 掲載ページ 47-51 - グラフとその周辺におけるランダム構造の話
出版日 2006年, 第２回組合せ論若手研究集会 - Random structures around graph theory
出版日 2006年, 2nd combinatorics seminar for young researchers - Dense graphs and pseudo-randomness
出版日 2005年, 第１回組合せ論若手研究集会 - Dense graphs and pseudo-randomness
出版日 2005年, 1st combinatorics seminar for young researchers - Random graphs and pseudo-random graphs I,II,III
出版日 2004年, 研究集会 Random graphsとその周辺 - Vertex-disjoint cycles containing prescribed vertices
Y Ishigami; T Jiang
出版日 2003年04月, JOURNAL OF GRAPH THEORY, 42巻, 4号, 掲載ページ 276-296, 英語, 0364-9024, WOS:000181867200002 - An analytic study of substructures of abstract graphs
出版日 2003年, Designs, Codes, Graphs and their Links IV - Spanning subgraphs in dense graphs
出版日 2003年, 応用数学合同研究集会 - An analytic study of substructures of abstract graphs
出版日 2003年, Designs, Codes, Graphs and their Links IV - Spanning subgraphs in dense graphs
出版日 2003年, Annual Join Meeting for the Study of Applied Mathematics - Proof of a conjecture of Bollobas and Kohayakawa on the Erdos-Stone theorem
Y Ishigami
出版日 2002年07月, JOURNAL OF COMBINATORIAL THEORY SERIES B, 85巻, 2号, 掲載ページ 222-254, 英語, 0095-8956, WOS:000176607100004 - Almost-spanning subgraphs with bounded degree in dense graphs
Y Ishigami
出版日 2002年07月, EUROPEAN JOURNAL OF COMBINATORICS, 23巻, 5号, 掲載ページ 583-612, 英語, 0195-6698, WOS:000178540300012 - A common extension of the Erdos-Stone theorem and the Alon-Yuster theorem for unbounded graphs
Y Ishigami
出版日 2002年05月, EUROPEAN JOURNAL OF COMBINATORICS, 23巻, 4号, 掲載ページ 431-448, 英語, 0195-6698, WOS:000177251100005 - An extension of a theorem on cycles containing specified independent edges
Y Ishigami; H Wang
出版日 2002年02月, DISCRETE MATHEMATICS, 245巻, 1-3号, 掲載ページ 127-137, 英語, 0012-365X, WOS:000174311400008 - 極値グラフ理論における擬確率的手法
出版日 2002年, 無限グラフとスペクトル, 掲載ページ 76-85 - On the regularity lemma
出版日 2002年, 関西グラフ理論研究集会 - Proof of a conjecture of Bollobás and Kohayakawa on the Erdos-Stone theorem
Yoshiyasu Ishigami
Academic Press Inc., 出版日 2002年, Journal of Combinatorial Theory. Series B, 85巻, 2号, 掲載ページ 222-254, 英語, 0095-8956, 0036311226 - A common extension of the Erdos-Stone theorem and the Alon-Yuster theorem for unbounded graphs
Yoshiyasu Ishigami
Academic Press, 出版日 2002年, European Journal of Combinatorics, 23巻, 4号, 掲載ページ 431-448, 英語, 0195-6698, 0036319643 - Almost-spanning subgraphs with bounded degree in dense graphs
Yoshiyasu Ishigami
Academic Press, 出版日 2002年, European Journal of Combinatorics, 23巻, 5号, 掲載ページ 583-612, 英語, 0195-6698, 0036384490 - The pseudo-probabilistic method in extremal graph theory
出版日 2002年, 掲載ページ 76-85 - On the regularity lemma
出版日 2002年 - Vertex-disjoint cycles of length at most four each of which contains a specified vertex
Y Ishigami
出版日 2001年05月, JOURNAL OF GRAPH THEORY, 37巻, 1号, 掲載ページ 37-47, 英語, 0364-9024, WOS:000168231900003 - Subgraphs in Dense Graphs and Szemeredi's Regularity Lemma
出版日 2001年, 関西グラフ理論研究集会 - A modern method for a wide range of classical problems in graph theory - the pseudo-probabilistic method
出版日 2001年, Mathematical Society of Japan（秋季総合分科会・応用数学・特別講演）, xxx巻, xxx号, 掲載ページ xxx-xxx - Extending Alon-Yuster's packing theorem
出版日 2001年, Mathematical Society of Japan, Fall meeting, xxx巻, xxx号, 掲載ページ xxx-xxx - Almost-spanning subgraphs in dense graphs
出版日 2001年, 応用数学合同研究集会, 掲載ページ 5-8 - Subgraphs in Dense Graphs and Szemeredi's Regularity Lemma
出版日 2001年 - A modern method for a wide range of classical problems in graph theory - the pseudo-probabilistic method
出版日 2001年, Mathematical Society of Japan（秋季総合分科会・応用数学・特別講演）, xxx巻, xxx号, 掲載ページ xxx-xxx - Extending Alon-Yuster's packing theorem
出版日 2001年, Mathematical Society of Japan, Fall meeting, xxx巻, xxx号, 掲載ページ xxx-xxx - Almost-spanning subgraphs in dense graphs
出版日 2001年, Annual Joint Meeting for the Study of Applied Mathematics, 掲載ページ 5-8 - Vertex-disjoint cycles of length at most four each of which contains a specified vertex
Yoshiyas Ishigami
Wiley-Liss Inc., 出版日 2001年, Journal of Graph Theory, 37巻, 1号, 掲載ページ 37-47, 英語, 0364-9024, 33751316505 - How many diagonal rectangles are needed to cover an orthogonal polygon?
Y Ishigami
出版日 2000年07月, DISCRETE & COMPUTATIONAL GEOMETRY, 24巻, 1号, 掲載ページ 117-140, 英語, 0179-5376, WOS:000087472600007 - Proof of a Bollobas-Kohayakawa Conjecture on the Erdos-Stone Theorem
出版日 2000年, MIGHTY XXXIII（MIdwest GrapH TheorY） Wright State University, Dayton, Ohio, USA - How many diagonal rectangles are needed to cover an orthogonal polygon?
出版日 2000年, Discrete and Computational Geometry, 24巻, 1号, 掲載ページ 117-140 - Proof of a Bollobas-Kohayakawa Conjecture on the Erdos-Stone Theorem
出版日 2000年, MIGHTY XXXIII（MIdwest GrapH TheorY） Wright State University, Dayton, Ohio, USA - Vertex-disjoint cycles containing specified edges
Y Egawa; RJ Faudree; E Gyori; Y Ishigami; RH Schelp; H Wang
出版日 2000年, GRAPHS AND COMBINATORICS, 16巻, 1号, 掲載ページ 81-92, 英語, 0911-0119, WOS:000168577400005 - Performance comparison of recognition systems: a Bayesian approach
OZEKI K; ISHIGAMI Y; TAKAGI K
出版日 1999年, The Journal of the Acoustical Society of Japan（E）, 20巻, 3号, 掲載ページ 171-179, 0388-2861 - Performance comparison of recognition systems: a Bayesian approach
出版日 1999年, The Journal of the Acoustical Society of Japan（E）, 20巻, 3号, 掲載ページ 171-179, 0388-2861 - Performance comparison of recognition systems: a Bayesian approach
OZEKI K.
出版日 1998年, Proc. EALREW '98, 掲載ページ 111-116, 10003787409 - Performance comparison of recognition systems: a Bayesian approach
出版日 1998年, 掲載ページ 111-116 - VC-dimensions of finite automata and commutative finite automata with k letters and n states
Y Ishigami; S Tani
出版日 1997年04月, DISCRETE APPLIED MATHEMATICS, 74巻, 2号, 掲載ページ 123-134, 英語, 0166-218X, 1872-6771, WOS:A1997WV74800002 - 組み合わせ論における手法と道具
出版日 1997年, 日本数学会・秋季総合分科会・企画特別講演, 掲載ページ 62-71 - Methods and tools in combinatorics
出版日 1997年, Mathematical Society of Japan, Special Planned Speech, 掲載ページ 62-71 - VC-dimensions of finite automata and commutative finite automata with $k$ letters and $n$ states
出版日 1997年, Discrete Applied Mathematics, 74巻, 2号, 掲載ページ 123-134 - An extremal problem of d permutations containing every permutation of every t elements
Y Ishigami
出版日 1996年11月, DISCRETE MATHEMATICS, 159巻, 1-3号, 掲載ページ 279-283, 英語, 0012-365X, WOS:A1996VR62700028 - The wide-diameter of the n-dimensional toroidal mesh
Y Ishigami
出版日 1996年07月, NETWORKS, 27巻, 4号, 掲載ページ 257-266, 英語, 0028-3045, 80009117731, WOS:A1996UV27800001 - On circles containing the maximum number of points
J Akiyama; Y Ishigami; M Urabe; J Urrutia
出版日 1996年05月, DISCRETE MATHEMATICS, 151巻, 1-3号, 掲載ページ 15-18, 英語, 0012-365X, WOS:A1996UL43800003 - The wide-diameter of the n-dimensional toroidal mesh
Yoshiyasu Ishigami
Wiley-Liss Inc., 出版日 1996年, Networks, 27巻, 4号, 掲載ページ 257-266, 英語, 0028-3045, 80009117731, 0039647017 - An extremal problem of $d$ permutations containing every permutation of every $t$ elements
出版日 1996年, Discrete Mathematics, 159巻, 1-3号, 掲載ページ 279-283 - Containment problems in high-dimensional spaces
Yoshiyasu Ishigami
Springer-Verlag, 出版日 1995年12月, Graphs and Combinatorics, 11巻, 4号, 掲載ページ 327-335, 英語, 0911-0119, 34249753581 - 高次元空間における点と直方体の組合せ論
出版日 1995年, SUT Bulletin, 掲載ページ 24-32 - Containment problems in high-dimensional spaces
Y Ishigami
出版日 1995年, GRAPHS AND COMBINATORICS, 11巻, 4号, 掲載ページ 327-335, 英語, 0911-0119, WOS:A1995TK85500003 - AN EXTREMAL PROBLEM OF ORTHANTS CONTAINING AT MOST ONE-POINT BESIDES THE ORIGIN
Y ISHIGAMI
出版日 1994年09月, DISCRETE MATHEMATICS, 132巻, 1-3号, 掲載ページ 383-386, 英語, 記事・総説・解説・論説等（学術雑誌）, 0012-365X, WOS:A1994PJ10800030 - Extremal Problems and Ramsey Properties of Ball, Box or Orthant containing many points in $R^d$ - And Combinatorics of Permutations(Computational Geometry and Discrete Geometry)
ISHIGAMI YOSHIYASU
京都大学数理解析研究所, 出版日 1994年05月, 数理解析研究所講究録, 872巻, 掲載ページ 79-81, 英語, 1880-2818, 120001446380, AN00061013 - An extremal problem of orthants containing at most one point besides the origin
出版日 1994年, Discrete Mathematics, 132巻, 1-3号, 掲載ページ 383-386 - SOME ASYMPTOTIC CONDITIONS OF WORLDLINES IN MINKOWSKI SPACE
G YONEDA; Y ISHIGAMI; S ARIMA
出版日 1993年05月, JOURNAL OF THE PHYSICAL SOCIETY OF JAPAN, 62巻, 5号, 掲載ページ 1495-1499, 英語, 0031-9015, WOS:A1993LE58600022 - The VC-dimensions of finite automata with n states
出版日 1993年, 744巻, 掲載ページ 328-341 - The VC-dimensions of finite automata with n states
出版日 1993年, 744巻, 掲載ページ 328-341
書籍等出版物
- Improvement of the Erdos-Stone Theorem
the 9th Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications（Kalamazoo, Michigan, USA）, 出版日 2000年 - Improvement of the Erdos-Stone Theorem
the 9th Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications（Kalamazoo, Michigan, USA）, 出版日 2000年
共同研究・競争的資金等の研究課題
- 離散数学・組合せ論への応用を意図したランダムネスと擬ランダムネスの理論
石上 嘉康
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 18540115
研究期間 2006年 - 2006年 - 離散構造の基礎的および応用的研究
安藤 清; 石上 嘉康; 河原林 健一; 金子 篤司
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 離散幾何学分野における本研究では平面上に配置された点集合を頂点とし、それらを結ぶ直線を辺とする幾何グラフを研究した。とくに2色の点集合から構成される幾何グラフとしての木の辺交差数に関する結果の3色の場合への拡張をはかり、良い評価を与えた。 グラフ論分野においては6-可縮臨界グラフの次数6の頂点の分布に関する研究に引き続き、7-可縮臨界グラフを調べ、7-可縮臨界グラフでは少なくともその1/64の頂点が次数7であることを示した。木の頂点に隣接する葉の数をその頂点の葉次数とよび、葉次数の最大値をその木の最大葉次数と呼ぶ。与えられた整数を超えない最大葉次数の全域木がグラフに存在するための必要十分条件を求めた。グラフとその補グラフがともにk-可縮臨界グラフならばその頂点数の2乗はkの3乗で押さえられることを示し、この評価が最良であることを示すグラフの構成に成功した。連結度が5のグラフにおいて次数5の頂点の近傍は自明な切断点集合と呼ばれ、自明な切断点集合に両端点が含まれる辺を自明な非可縮辺と呼ぶ。可縮臨界5-連結グラフは頂点数の1/2の辺が自明な非可縮辺を含むことを示した。この事実を示す過程で可縮臨界5-連結グラフにおける自明でない非可縮辺の存在とある特定の部分グラフの存在との間の関係を見い出した。これは自明でない非可縮辺を持つ可縮臨界5-連結グラフの部分構造の特徴付けの基礎をなすものと考えられる。さらに4-正則4-連結グラフは三角形に含まれない辺の数の1/2の4-可縮辺を含むことを示した。4-連結グラフの次数5以上の頂点xの近傍の次数4の頂点の誘導する部分グラフがP_4と同型でなければ、xから距離1以内に4-可縮辺が少なくとも2本存在することを示した。擬確率的手法を用いて規模の大きいグラフはわずかの部分を除いて規則的部分グラフで覆えることを示した。これは現在まで知られているAlon-Yusterの定理を含む結果である。, 14540105
研究期間 2002年 - 2004年 - グラフ論、離散最適化とその応用
安藤 清; 石上 嘉康; 田村 明久; 浅野 哲夫; 吉岡 正典
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), グラフ論、離散最適化、計算幾何学の諸分野に渡る本研究の研究成果の概要を以下に示す。 計算幾何学の分野の直線成分の抽出問題では従来用いられてきたハフ変換の性能の限界を理論的に示し,理論的に最適な方法を提案した。画像の等高線表現では、整数格子の性質を研究し、グラフ論、離散最適化を適用した問題解決法を提案した。ディジタルハーフトーニングを数学的最適化問題として定義し,ある種の測度を基礎にした実数要素行列の整数要素行列への変換法を導入することにより、ある制約のもとで効率よく実行できるアルゴリズムの開発に成功した。 離散最適化の分野では有向グラフの一般化として双向グラフを定義し、双向グラフ上で安定集合問題の一般化を定式化した。クローフリーグラフの最大重み独立集合を求めるMintyのアルゴリズムの訂正版を提案した。離散凸解析における重要な基本問題の一つであるM-凸関数の最小化問題に対する新しい多項式時間アルゴリズムを提案した。 グラフの距離構造についてはk-辺ワイド直径はグラフの直径のk次式のオーダーであることを示した。グクフの連結度については先行の結果を含むk-可縮辺の存在を保証するより一般的な禁止部分グラフ条件を示した。5-可縮臨界グラフでは少なくともその1/5の頂点が次数5であること、6-可縮臨界グラフでは少なくともその1/7の頂点が次数6であることを示した。与えられた任意のグラフをその誘導部分グラフに含む5-可縮臨界グラフの存在を示した。 極値グラフ理論の分野では新しい擬確率的手法を開発して当該分野の基本定理であるErdos-Stoneの拡張、Bollobas-Kohayakawa予想を肯定的に解決した。グラフを同型な部分グラフで敷き詰めることができるための次数条件を述べたAlon-Yusterの定理を必ずしも同型でない部分グラフの場合に拡張し、長年未解決であったEl-Zahar予想など多くの定理、予想を近似的に含む一般的な結果を得た。, 11640105
研究期間 1999年 - 2001年 - 組合せ論の極値的問題における確率的方法の研究
石上 嘉康
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(A), 11740058
研究期間 1999年 - 1999年 - 組合せ論の極値的問題における確率的方法の研究
石上 嘉康
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(A), 昨年のグラフ理論におけるサイクル被覆のWang予想の証明および直交多角形の長方形被覆に関するWatanabe予想の証明を発展させ、より強く美しい結果を得た。またグラフ理論におけるサイクルの存在性の研究を行い、成果を得た。 グラフがハミルトングサイクルをもつための条件として、オーレの次数条件(Ore,1961)がもっとも古典的なもので評価が高い。この後、オーレ型次数条件をもつグラフの中のサイクルの研究が盛んに進んでいるが、その流れのなかで、H.Wangは雑誌Jouranal of Graph Theoryにおいて、ある予想を提示した。それは、グラフの頂点数が十分大きい時、どの非隣接2頂点の次数和も\n+2k-2\以上あれば、任意の\k(＼geq 2)\個の独立辺のそれぞれを経由する\k\個サイクルで、グラフの頂点を分割できるというものである。彼のその論文の中で\k=2\の場合を主定理として証明している。また\k=3\の場合も証明できたことをアナウンスしている。これらの背景の中で、任意の\k\に対してWang予想が成り立つことを証明した。さらに頂点数の下限も\4k-1\であることを示し、\4k-2\の場合はサイクルをもたない場合もあるが、その場合はある簡単なグラフに限られることを示した。そしてその証明の大幅な簡略化に成功した。 またこの研究の流れの中で、指定された辺ではなく頂点を通るサイクルの研究を開始した。そして、被覆するサイクルの存在ではなく、短いサイクルの存在性に対して、ほぼベストな最小次数の条件を得ることに成功した。長さを限定しないサイクルの存在定理も実はこれらの結果から系として導かれる。, 09740137
研究期間 1997年 - 1998年 - 組合せ論の極値的問題における確率的方法の研究
石上 嘉康
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(A), ランダムハイパーグラフ上のラムゼ-理論を主に研究した。この分野に多いに貢献した著者B.Bollobas著Random Graphs(1985)は、ランダムグラフ上でのラムゼ-理論にはほとんど触れていない。が、最近の研究によってこの著書もすでに古くなった感があり、ラムゼ-理論の発展と確率的手法,ランダムグラフの研究の進展とともに,近年、ランダムグラフでのラムゼ-理論が技術的に可能になってきた。ランダムハイパーグラフ上のラムゼ-理論となると、まだあまり研究されていない。 Luczak氏らのランダムグラフにおけるRamsey的性質の研究をうけつぎ、最近、Kreuter氏がさらに広い場合について成果を拡張した。今回は,これらの状況をふまえ、さらにランダムハイパーグラフにおいて、これらの研究結果のいくつかを拡張した。ここでいうランダムハイパーグラフとは、もっとも標準的な確率モデルであるランダムk-ユニフォームハイパーグラフを採用した。つまり、n頂点完全k-ユニフォームハイパーグラフの各辺を一定の確率p(0 - 組合せ理論における極値的問題の確率的証明手法、及びそのアルゴリズム的側面の研究
石上 嘉康
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(A), ランダムグラフ上のラムゼ-理論を主に研究した。この分野に多いに貢献したB.Bollobas著Random Graphs(1985)は、ランダムグラフ上でのラムゼ-理論にはほとんど触れていない。が、最近の研究によってこの著書もすでに古くなった感があり、ラムゼ-理論の発展と確率的手法,ランダムグラフの研究の進展とともに,近年、ランダムグラフ上でのラムゼ-理論が技術的に可能になってきた。一方で、辺着色されたグラフの全頂点を単色の木で被覆する研究は強く注目をあびているものの古典的ラムゼ-理論の例にもれず,もっとも単純な完全グラフ上においてしかなされていない。 今回は,これらの状況をふまえ、この単色木被覆の研究はランダムグラフを融合させる試みを行なった。それによると、2着色の場合、完全グラフにおける(単色木による)被覆数は1、辺を一本除去したグラフは2まであがるが、その後、辺をランダムに除去し続けた場合、かなり辺が減ってしまった場合においても2のままでありつづけ,ある段階で突然無限にとんでしまう。(例えば、ほぼ全てのグラフの被覆数が2である。)また、着色数が3以上の場合、2着色の場合ほど突然ではなく、被覆数がもっと早い段階から増加していることがわかった。完全グラフの場合,2着色と3着色以上でも性質が似ているのに対し、ランダムグラフの場合でははっきりとした差が確認された。この意味でも興味深い。 ランダムグラフ上で議論可能なラムゼ-的性質はまだあまり多くはないが、なかでも本研究における単色木被覆の研究は新たにわかった基礎的なラムゼ-的性質であり,本研究が、古典的な完全グラフ上での研究の単なる拡張ではなく、ランダムグラフとラムゼ-の融合による独特の課題であるという点でも意義が認められる。, 07740147
研究期間 1995年 - 1995年 - 組み合わせ論・グラフ理論における擬確率的手法。ラムゼー理論。及びその計算機科学への応用。確率・近似アルゴリズム。
研究期間 1994年 - Pseudo-probabilistic methods in combinatorics and graph theory with applications to computer sciences. Ramsey theory. Probabilistic and approximation algorithms.
研究期間 1994年
