YOSHIYASU ISHIGAMI
| Department of Informatics | Associate Professor |
| Cluster II (Emerging Multi-interdisciplinary Engineering) | Associate Professor |
Researcher Information
Research Activity Information
Award
Paper
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
15 Aug. 2007, Electronic Notes in Discrete Mathematics, 29, 47-51, English, 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
Apr. 2003, JOURNAL OF GRAPH THEORY, 42, 4, 276-296, English, 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
Jul. 2002, JOURNAL OF COMBINATORIAL THEORY SERIES B, 85, 2, 222-254, English, 0095-8956, WOS:000176607100004 - Almost-spanning subgraphs with bounded degree in dense graphs
Y Ishigami
Jul. 2002, EUROPEAN JOURNAL OF COMBINATORICS, 23, 5, 583-612, English, 0195-6698, WOS:000178540300012 - A common extension of the Erdos-Stone theorem and the Alon-Yuster theorem for unbounded graphs
Y Ishigami
May 2002, EUROPEAN JOURNAL OF COMBINATORICS, 23, 4, 431-448, English, 0195-6698, WOS:000177251100005 - An extension of a theorem on cycles containing specified independent edges
Y Ishigami; H Wang
Feb. 2002, DISCRETE MATHEMATICS, 245, 1-3, 127-137, English, 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, English, 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, English, 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, English, 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
May 2001, JOURNAL OF GRAPH THEORY, 37, 1, 37-47, English, 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, English, 0364-9024, 33751316505 - How many diagonal rectangles are needed to cover an orthogonal polygon?
Y Ishigami
Jul. 2000, DISCRETE & COMPUTATIONAL GEOMETRY, 24, 1, 117-140, English, 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, English, 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
Apr. 1997, DISCRETE APPLIED MATHEMATICS, 74, 2, 123-134, English, 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
Nov. 1996, DISCRETE MATHEMATICS, 159, 1-3, 279-283, English, 0012-365X, WOS:A1996VR62700028 - The wide-diameter of the n-dimensional toroidal mesh
Y Ishigami
Jul. 1996, NETWORKS, 27, 4, 257-266, English, 0028-3045, 80009117731, WOS:A1996UV27800001 - On circles containing the maximum number of points
J Akiyama; Y Ishigami; M Urabe; J Urrutia
May 1996, DISCRETE MATHEMATICS, 151, 1-3, 15-18, English, 0012-365X, WOS:A1996UL43800003 - The wide-diameter of the n-dimensional toroidal mesh
Yoshiyasu Ishigami
Wiley-Liss Inc., 1996, Networks, 27, 4, 257-266, English, 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, Dec. 1995, Graphs and Combinatorics, 11, 4, 327-335, English, 0911-0119, 34249753581 - 高次元空間における点と直方体の組合せ論
1995, SUT Bulletin, 24-32 - Containment problems in high-dimensional spaces
Y Ishigami
1995, GRAPHS AND COMBINATORICS, 11, 4, 327-335, English, 0911-0119, WOS:A1995TK85500003 - AN EXTREMAL PROBLEM OF ORTHANTS CONTAINING AT MOST ONE-POINT BESIDES THE ORIGIN
Y ISHIGAMI
Sep. 1994, DISCRETE MATHEMATICS, 132, 1-3, 383-386, English, Introduction scientific journal, 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
京都大学数理解析研究所, May 1994, 数理解析研究所講究録, 872, 79-81, English, 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
May 1993, JOURNAL OF THE PHYSICAL SOCIETY OF JAPAN, 62, 5, 1495-1499, English, 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
Books and other publications
- 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
Research Themes
- 離散数学・組合せ論への応用を意図したランダムネスと擬ランダムネスの理論
石上 嘉康
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 18540115
2006 - 2006 - Fundamental and application oriented studies of discrete structures
ANDO Kiyoshi; ISHIGAMI Yoshiyasu; KAWARABAYASHI Ken-ichi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), From an arrangement of points on the plane, we construct a tree joining points by straight line segments, then We call the resulting tree a geometric tree of the arrangement of points. We gave an upper bound on the crossing number of three geometric trees in terms of n each vertex set of which is the subset of each color points sets of a given arrangement of n points with three colors. For a vertex x of a tree, the number of leafs adjacent with x is called the leaf degree of x. We gave a necessary and sufficient condition for a connected graph to have a spanning tree whose maximum leaf degree is not exceed a given number. We showed that if both a graph and its complement are contraction critically κ-connected, then the square of its order is not exceed κ^3, also we showed the sharpness of this bound. An edge e of a 5-connected graph is called trivially noncontractible if there is a vertex of degree 5 which is adjacent, with both end vertices of e. We showed that a contraction critically 5-connected graph of order n has at least n/2 trivially noncontractible edges. We proved that a 4-connected graph with m vertices of degree greater than 4 has at least m 4-contractible edges., 14540105
2002 - 2004 - Graph theory, discrete optimization and their applications
ANDO Kiyoshi; ISHIGAMI Yoshiyasu; TAMURA Akihisa; ASANO Tetsuo
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), In computational geometry, we proposed an idea of a geometric representation of an image by using contour line which enables approaches completely different from conventional ones based on matrix representation of an image. We also gave an algorithm to approximate rectilinear contour lines by smooth curves while keeping several basic properties inherent in contour lines. These applications are closely related to digital geometry in which vertices have integer coordinates. We investigated a new approach for Digital halftoning which is a technique to convert a grey image into a binary (black and white) image. We introduced an notion of bidirected graph as an extension of directed graph and we gave a linear time algorithm for the generalized stable set problem on triangulated bidirected graphs. We proposed a polynomial time algorithm for the M-convex function minimization problem. We proved that the edge wide-diameter of a k-edge connected graph does not exceed a plynomial of the diameter of it of degree k. We proved that the number of vertices of degree 5 of every 5-contraction critical graph is at least 1/5 of its order and the number of vertices of degree 6 of every 6-contraction critical graph is at least 1/7 of its order. We developed a new pseudo-probablistic method and we proved Bollbas-Kohayakawa conjecture on Erdos-Stone theorem., 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
