Doctor(Science), Waseda University

Natural sciences, Applied mathematics and statistics

Natural sciences, Basic mathematics

Informatics, Information theory

1993
小野梓記念学術賞
Japan

1993
Onoazusa Memorial Award(Academic Award)

1992
大川功賞
Japan

1992
Isao OKAWA Award

VC-dimensions of finite automata and commutative finite automata with k letters and n states
Y Ishigami; S Tani
DISCRETE APPLIED MATHEMATICS, ELSEVIER SCIENCE BV, 74, 3, 229-240, May 1997, Peer-reviwed, An investigation is conducted of the Vapnik-Chervonenkis dimensions (VC-dimensions) of finite automata having k letters and n stares. It is shown for a fixed positive integer k(greater than or equal to 2), that (1) the VC-dimension of DFA(k)(n) := (L subset of (1,2,...,k)* : some deterministic finite automaton with at most n states accepts L) is n + log(2) n - O (log log n) for k = 1 and (k - 1 + o(1))n log(2) n for k greater than or equal to 2, and (2) the VC-dimension of CDFA(k)(n) := (L is an element of DFA(k)(n) : L is commutative) is n + o(n).
Scientific journal, English

離散構造の中の擬ランダム性（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
We show that the Ramsey number is linear for every uniform hypergraph with bounded degree. This is a hypergraph extension of the famous theorem for ordinary graphs which Chvátal et al. [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, Jr., The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), pp. 239-243] showed in 1983. Our proof demonstrates the potential of a new regularity lemma by [Y. Ishigami, A simple regularization of hypergraphs, preprint, arXiv:math/0612838 (2006)]. © 2007 Elsevier B.V. All rights reserved., 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とその周辺

Random graphs and pseudo-random graphs I,II,III
2004, 研究集会 Random graphsとその周辺

Vertex-disjoint cycles containing prescribed vertices
Y Ishigami; T Jiang
Enomoto [7] conjectured that if the minimum degree of a graph G of order n greater than or equal to 4k - 1 is at least the integer [root n + (9/4 k(2) - 4k + 1) + 3/2 k - 1], then for any k vertices, G contains k vertex-disjoint cycles each of which contains one of the k specified vertices. We confirm the conjecture for n greater than or equal to ck(2) where c is a constant. Furthermore, we show that under the same condition the cycles can be chosen so that each has length at Most six. (C) 2003 Wiley Periodicals, Inc., JOHN WILEY & SONS INC, Apr. 2003, JOURNAL OF GRAPH THEORY, 42, 4, 276-296, English, 0364-9024, WOS:000181867200002

Vertex-disjoint cycles containing prescribed vertices
Y Ishigami; T Jiang
Enomoto [7] conjectured that if the minimum degree of a graph G of order n greater than or equal to 4k - 1 is at least the integer [root n + (9/4 k(2) - 4k + 1) + 3/2 k - 1], then for any k vertices, G contains k vertex-disjoint cycles each of which contains one of the k specified vertices. We confirm the conjecture for n greater than or equal to ck(2) where c is a constant. Furthermore, we show that under the same condition the cycles can be chosen so that each has length at Most six. (C) 2003 Wiley Periodicals, Inc., JOHN WILEY & SONS INC, 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

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

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
For any integer r greater than or equal to 1, let a(r) be the largest constant a greater than or equal to 0 such that if epsilon > 0 and 0 < c < c(0) for some small c(0) = c(0)(r, epsilon) then every graph G of sufficiently large order n and at least
(1 - 1/r +c)((n)(2))
edges contains a copy of any (r+1)-chromatic graph H of independence number
alpha(H) less than or equal to (a-epsilon)log n/log(1/c)
T. Kovari et al. (1954, Colloq. Math. 2. 50-57) and B. Bollobas and P. Erdos (1973, Bull. London Math. Sac. 5, 317-321) showed that 1 less than or equal to a(1) less than or equal to 2. In an improvement to the Erdos-Stone theorem (1946), B. Bollobas et al. (1976, J. London Math. Soc. (2) 12, 219-224) showed that a(r) > 0 for all r and conjectured that lim inf(r-->infinity) a(r) not equal 0. V. Chvatal and E. Szemeredi (1981, J. London Math. Soc. (2) 23, 207-214) settled it by giving a(r) greater than or equal to 0.002 for all r. We show that, for all r, a(r) = a(1).
Further we prove the conjecture of B. Bollobas and Y. Kohayakawa (1994, Combinatorica 14, 279-286). The weak form of it states that for any r greater than or equal to 1, 0 < c < 1/r, every graph G of sufficiently large order n greater than or equal to n(0)(r, c) and (1 - 1/r + c)((n)(2)) edges contains any (r+1)-chromatic graph such that, in a proper vertex coloring, the smallest and the other color classes are of size at least
betalog n/log(1/c) and betalog n/log r,
log(1/c) log r respectively, for an absolute constant beta > 0. That is, all color classes but one are relatively large for fixed r, small c --> 0, and large n --> infinity. Our proof method is based on Szemeredi's Regularity Lemma. (C) 2002 Elsevier Science (USA)., ACADEMIC PRESS INC ELSEVIER SCIENCE, 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
We present two extensions of a theorem by Alon and Yuster (1992, Graphs Comb., 8, 95-102) that give degree conditions guaranteeing an almost-spanning subgraph isomorphic to a given graph. The first extension gives a sharp degree condition when the desired subgraph consists of small connected components (i.e., a packing of a host graph with small graphs), improving a theorem of Komlos (2000, Combinatorica, 20, 203-218). The second extension weakens the assumption of the desired subgraph in the Alon-Yuster theorem.
Given a graph F, we write chi(F) and A (F) for the chromatic number and the maximum degree, respectively. We also denote by sigma(r) (F) the smallest possible colour class size in any proper r-vertex-colouring of F. The first theorem states that, for every Delta greater than or equal to 1 and is an element of > 0, there exists a mu > 0 and an no such that the following holds. Let H = (boolean OR) over dot(i) H-i be a non-empty graph such that
\H\ less than or equal to (1 - epsilon)n, Delta(H) less than or equal to Delta, and, for each H-i, \H-i\ less than or equal to mun.
Then every graph G with order n greater than or equal to n(0) and minimum degree
delta(G) greater than or equal to (1 - 1 - (σ) over tilde /r -1 - mu)n
contains a copy of H where r := max(i) chi(H-i) and (σ) over tilde := max{Sigma(j) sigma(r) (H-i)/\H\, epsilon}.
The second theorem states that, for any r > 1, Delta greater than or equal to 0, and epsilon > 0, there exists a mu > 0 and an n(0) such that for every graph G with order n greater than or equal to n(0) and
delta(G) greater than or equal to (1 - 1/r - mu)n,
one of the following two holds:
For any graph H with
\H\ less than or equal to (1 - epsilon)n, Delta(H) less than or equal to Delta, chi(H) less than or equal to r, and b(H) less than or equal to mun,
G contains a copy of H (where b(H) denotes the bandwidth of H).
By deleting and adding at most epsilonn(2) edges and r vertices of G, G can be isomorphic to K-r([n/r]) or K-[n/r] + Kr-2([n/r]) + K-[n/r].
The assumption of b(H) cannot be dropped. (C) 2002 Elsevier Science Ltd. All rights reserved., ACADEMIC PRESS LTD ELSEVIER SCIENCE LTD, 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
The Erdos-Stone theorem (1946, Bull. Am. Math. Soc., 52, 1089-1091) and the Alon-Yuster theorem (1992, Graphs Comb., 8, 95-102) are both very fundamental in extremal graph theory, We give a common extension of them, which states as follows: For every epsilon > 0 and r greater than or equal to 2, there exists c = c(epsilon,r) > 0 such that, for any 0 less than or equal to theta less than or equal to 1, if H is a graph of order \H\ less than or equal to c log n and with chromatic number r then every n-vertex graph G with minimum degree at least (1 - 1/r-1 + theta/r(r-1))n contains at least (theta - epsilon)n/\H\ vertex-disjoint copies of H.
When theta = epsilonr (r - 1) or theta = 1, it would imply the two theorems.
The important point is that our theorem enables us to deal with a larger graph H of order \H\ --> infinity (as n --> infinity), while \H\ was fixed in the Alon-Yuster theorem (and in another common extension by Komlos (2000, Combinatorica, 20, 203-218)).
The bounds c log n and (1 - 1/r-1 + theta/r(r-1))n are both essentially the best possible (C) 2002 Elsevier Science Ltd. All rights reserved., ACADEMIC PRESS LTD ELSEVIER SCIENCE LTD, 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
We give an alternative proof of a conjecture due to Wang (J. Graph Theory 26 (1997) 105) in a stronger form. The main theorem states that for any integer k greater than or equal to 2 if G is a graph of order n greater than or equal to 4k - 1 and d(u) + d(v) greater than or equal to n + 2k - 2 for each pair of non-adjacent vertices u and v of G, then, for any k independent edges e(1),...,e(k) of G, there exist k vertex-disjoint cycles C-1,...,C-k in G such that
(i) e(i) epsilon E(C-i) for all 1 less than or equal to i less than or equal to k,
(ii) V(C-1) boolean OR...boolean OR V(C-k) = V(G), and
(iii) #{i less than or equal to kparallel toC(i)\ > 4} less than or equal to 1,
unless K-a + (K) over bar (n-2k-a) subset of G subset of K-a + K-2k + Kn-2k-a for some a (2k-2 < a < n-4k+2). It strengthens the conjecture of Wang, which was first proven by Egawa et at. (Graphs Combin. 16 (2000) 81). (C) 2002 Published by Elsevier Science B.V., ELSEVIER SCIENCE BV, Feb. 2002, DISCRETE MATHEMATICS, 245, 1-3, 127-137, English, 0012-365X, WOS:000174311400008

An extension of a theorem on cycles containing specified independent edges
Y Ishigami; H Wang
We give an alternative proof of a conjecture due to Wang (J. Graph Theory 26 (1997) 105) in a stronger form. The main theorem states that for any integer k greater than or equal to 2 if G is a graph of order n greater than or equal to 4k - 1 and d(u) + d(v) greater than or equal to n + 2k - 2 for each pair of non-adjacent vertices u and v of G, then, for any k independent edges e(1),...,e(k) of G, there exist k vertex-disjoint cycles C-1,...,C-k in G such that
(i) e(i) epsilon E(C-i) for all 1 less than or equal to i less than or equal to k,
(ii) V(C-1) boolean OR...boolean OR V(C-k) = V(G), and
(iii) #{i less than or equal to kparallel toC(i)\ > 4} less than or equal to 1,
unless K-a + (K) over bar (n-2k-a) subset of G subset of K-a + K-2k + Kn-2k-a for some a (2k-2 < a < n-4k+2). It strengthens the conjecture of Wang, which was first proven by Egawa et at. (Graphs Combin. 16 (2000) 81). (C) 2002 Published by Elsevier Science B.V., ELSEVIER SCIENCE BV, Feb. 2002, DISCRETE MATHEMATICS, 245, 1-3, 127-137, English, 0012-365X, WOS:000174311400008

極値グラフ理論における擬確率的手法
2002, 無限グラフとスペクトル, 76-85

極値グラフ理論における擬確率的手法
2002, 無限グラフとスペクトル, 76-85

On the regularity lemma
2002, 関西グラフ理論研究集会

Proof of a conjecture of Bollobás and Kohayakawa on the Erdos-Stone theorem
Yoshiyasu Ishigami
For any integer r ≥1, let a(r) be the largest constant a≥0 such that if ε>
0 and 0<
c<
c0 for some small c0 = c0(r,ε) then every graph G of sufficiently large order n and at least edges contains a copy of any (r+1)-chromatic graph H of independence number T. Kovári et al. (1954, Colloq. Math. 2, 50-57) and B. Bollobás and P. Erdos (1973, Bull. London Math. Soc. 5, 317-321) showed that 1 ≤a(1)≤2. In an improvement to the Erdos-Stone theorem (1946), B. Bollobás et al. (1976, J. London Math. Soc. (2) 12, 219-224) showed that a(r)>
0 for all r and conjectured that lim infr→∞a(r)≠0. V. Chvátal and E. Szemerédi (1981, J. London Math. Soc. (2) 23, 207-214) settled it by giving a(r)≥0.002 for all r. We show that, for all r, Further we prove the conjecture of B. Bollobás and Y. Kohayakawa (1994, Combinatorica 14, 279-286). The weak form of it states that for any r≥1,0<
c<
1/r, every graph G of sufficiently large order n≥n0(r,c) and (1-1/r+c)(2 n) edges contains any (r+1)-chromatic graph such that, in a proper vertex coloring, the smallest and the other color classes are of size at least respectively, for an absolute constant β>
0. That is, all color classes but one are relatively large for fixed r, small c→0, and large n→∞. Our proof method is based on Szemerédi's Regularity Lemma. © 2002 Elsevier Science (USA)., 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
The Erdos-Stone theorem (1946, Bull. Am. Math. Soc., 52, 1089-1091) and the Alon-Yuster theorem (1992, Graphs Comb., 8, 95-102) are both very fundamental in extremal graph theory. We give a common extension of them, which states as follows: For every ε >
0 and r ≥ 2, there exists c = c ε,r >
0 such that, for any 0 ≤ θ ≤ 1, if H is a graph of order |H| ≤ log n and with chromatic number r then every n-vertex graph G with minimum degree at least (1 - 1/r-1 + θ/r(r-1)n contains at least (θ - ε)n/|H| vertex-disjoint copies of H. When θ = εr(r-1) or θ = 1, it would imply the two theorems. The important point is that our theorem with a larger graph H of order |H| → ∞ (as n → ∞), while |H| was fixed in the Alon-Yuster theorem (and in another common extension by Komlós (2000, Combinatorica, 20, 203-218)). The bounds c log n and (1 - 1/r-1 + τ/r(r-1)n are both essentially the best possible. © 2002 Elsevier Science Ltd. All rights reserved., 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
We present two extensions of a theorem by Alon and Yuster (1992, Graphs Comb., 8, 95-102) that give degree conditions guaranteeing an almost-spanning subgraph isomorphic to a given graph. The first extension gives a sharp degree condition when the desired subgraph consists of small connected components (i.e., a packing of a host graph with small graphs), improving a theorem of Komlós (2000, Combinatorica, 20, 203-218). The second extension weakens the assumption of the desired subgraph in the Alon Yuster theorem. Given a graph F, we write χ(F) and Δ(F) for the chromatic number and the maximum degree, respectively. We also denote by σr(F) the smallest possible colour class size in any proper r-vertex-colouring of F. The first theorem states that, for every Δ ≥ 1 and ε >
0, there exists a μ >
0 and an n0 such that the following holds. Let H = ∪iHi be a non-empty graph such that |H| ≤ (1 - ε)n, Δ(H) ≤ Δ, and, for each Hi, |Hi| ≤ μn. Then every graph G with order n ≥ n0 and minimum degree δ(G) ≥ (1 - 1 - σ̃/r - 1 - μ)n contains a copy of H where r: = maxi χ(Hi) and σ̃: = max {∑i σr(Hi)/|H|, ε}. The second theorem states that, for any r >
1, Δ ≥ 0, and ε >
0, there exists a μ >
0 and an n0 such that for every graph G with order n >
n0 and δ(G) ≥ (1 - 1/r - μ)n, one of the following two holds: • For any graph H with |H| ≤ (1 - ε)n Δ(H) <
Δ, χ(H) ≤ r, and b(H) ≤ μn, G contains a copy of H (where b(H) denotes the bandwidth of H). • By deleting and adding at most εn2 edges and r vertices of G, G can be isomorphic to Kr (⌊n/r⌋) or K⌊n/r⌋ + K r-2(⌊n/r⌋) + K⌊n/r⌊. The assumption of b(H) cannot be dropped. © 2002 Elsevier Science Ltd. All rights reserved., 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

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
We obtain a sharp minimum degree condition delta (G) greater than or equal to right perpendicular rootn+k2 - 3k + 1 left perpendicular + 2k - 1 of a graph G of order n greater than or equal to 3k guaranteeing that, for any k distinct vertices, G contains k vertex-disjoint cycles of length at most four each of which contains one of the k prescribed vertices. (C) 2001 John Wiley & Sons, Inc., JOHN WILEY & SONS INC, May 2001, JOURNAL OF GRAPH THEORY, 37, 1, 37-47, English, 0364-9024, WOS:000168231900003

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

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

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

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
We obtain a sharp minimum degree condition δ(G) ≥ equation presented √n + k2 - 3k + 1 equation presented + 2k - 1 of a graph G of order n ≥ 3k guaranteeing that, for any k distinct vertices, G contains k vertex-disjoint cycles of length at most four each of which contains one of the k prescribed vertices. © 2001 John Wiley &
Sons, Inc., 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
We show that any orthogonal polygon of n vertices can be covered with at most right perpendicular 3/4n left perpendicular - 2 - omega "diagonal rectangles" where omega = 1 (n = 8, 12, 16) and omega = 0 (otherwise). An orthogonal polygon is a polygon whose edges are horizontal or vertical. A diagonal rectangle (of an orthogonal polygon) is a rectangle whose opposite corners are vertices of the orthogonal polygon. The result is sharp and settles a question of Mamoru Watanabe [11]., SPRINGER VERLAG, 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

Vertex-disjoint cycles containing specified edges
Y Egawa; RJ Faudree; E Gyori; Y Ishigami; RH Schelp; H Wang
Dirac and Ore-type degree conditions are given for a graph to contain vertex disjoint cycles each of which contains a previously specified edge. One set of conditions is given that imply vertex disjoint cycles of length at most 4, and another set of conditions are given that imply the existence of cycles that span all of the vertices of the graph (i.e. a 2-factor). The conditions are shown to be sharp and give positive answers to conjectures of Enomoto in [3] and Wang in [5]., SPRINGER-VERLAG, 2000, GRAPHS AND COMBINATORICS, 16, 1, 81-92, English, 0911-0119, WOS:000168577400005

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
Dirac and Ore-type degree conditions are given for a graph to contain vertex disjoint cycles each of which contains a previously specified edge. One set of conditions is given that imply vertex disjoint cycles of length at most 4, and another set of conditions are given that imply the existence of cycles that span all of the vertices of the graph (i.e. a 2-factor). The conditions are shown to be sharp and give positive answers to conjectures of Enomoto in [3] and Wang in [5]., SPRINGER-VERLAG, 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
An investigation is conducted of the Vapnik-Chervonenkis dimensions (VC-dimensions) of finite automata having k letters and n states. It is shown for a fixed positive integer k(greater than or equal to 2) that (1) the VC-dimension of DFA(k)(n) := {L subset of(1,2,..., k}* : some deterministic finite automaton with at most n states accepts L} is n + log(2) n - O(log log n) for k = 1 and (k - 1 + o(1))n log(2) n for k greater than or equal to 2, and (2) the VC-dimension of CDFA(k)(n) := {L epsilon DFA(k)-(n) : L is commutative} is o(n).s n + o(n)., ELSEVIER SCIENCE BV, Apr. 1997, DISCRETE APPLIED MATHEMATICS, 74, 2, 123-134, English, 0166-218X, 1872-6771, WOS:A1997WV74800002

組み合わせ論における手法と道具
1997, 日本数学会・秋季総合分科会・企画特別講演, 62-71

組み合わせ論における手法と道具
1997, 日本数学会・秋季総合分科会・企画特別講演, 62-71

Methods and tools in combinatorics
1997, Mathematical Society of Japan, Special Planned Speech, 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
Let d(t)(n) be the smallest number d having d permutations {sigma(1),sigma(2),...,sigma(d)} of [n] such that for every permutation tau of every t elements of [n], there exists a sigma(i)(1 less than or equal to i less than or equal to d) containing tau. For fixed t greater than or equal to 4 and large n, we show d(t)(n)greater than or equal to(t-2)! log(t) n., ELSEVIER SCIENCE BV, 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
In graph theory and a study of transmission delay and fault tolerance of networks, the connectivity and the diameter of a graph are very important and they have been studied by many mathematicians. We studied the wide-diameter of a k-regular k-connected graph which is defined by the maximum of the k-distance between two distinct vertices, when the k-distance between x and y is equal to the least number I such that there exists k vertex-disjoint paths between x and y whose lengths are at most I. Because the wide-diameter of any k-regular k-connected graph is greater than its diameter, a k-regular k-connected graph whose wide-diameter is equal to ''1 + its diameter'' is optimal. For example, it is known that the hypercube is such a graph. We define n-dimensional toroidal mesh C(d(1), d(2),..., d(n)) with vertices {(x(1),..., x(n))\0 less than or equal to x(i) < d(i) (1 less than or equal to i less than or equal to n)}. Each vertex (x(1),..., x(n)) is adjacent to 2n other vertices {(x(1),..., x(n))\0 less than or equal to x(i) < d(i)(1,..., x(n))},..., (x(1), x(2),..., x(n) +/- 1), where additions are performed module d(i)(1 less than or equal to i less than or equal to n). This graph is an n-dimensional orthogonal mesh with global edges, which is 2n-connected and 2n-regular. We show that the graph satisfies the above property with respect to its 2n-diameter and its diameter except for some special cases. (C) 1996 John Wiley & Sons, Inc., JOHN WILEY & SONS INC, 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
We define B(x,y) to be the disk in the plane which has the points x,y as its diametral end points, Let Pi(B)(n) [or <(Pi)over bar(B)>(n)] be the largest number such that for every set [or every convex set]P of n points in R(2), there exist two points x, y is an element of P for which B(x, y) contains <(Pi)over bar(B)>(n) [or<(Pi)over bar(B)>(n)] points of P. We show that <(Pi)over bar(B)>(n) = <(Pi)over bar>(B)(n) = [n / 3] + 1., ELSEVIER SCIENCE BV, May 1996, DISCRETE MATHEMATICS, 151, 1-3, 15-18, English, 0012-365X, WOS:A1996UL43800003

On circles containing the maximum number of points
J Akiyama; Y Ishigami; M Urabe; J Urrutia
We define B(x,y) to be the disk in the plane which has the points x,y as its diametral end points, Let Pi(B)(n) [or <(Pi)over bar(B)>(n)] be the largest number such that for every set [or every convex set]P of n points in R(2), there exist two points x, y is an element of P for which B(x, y) contains <(Pi)over bar(B)>(n) [or<(Pi)over bar(B)>(n)] points of P. We show that <(Pi)over bar(B)>(n) = <(Pi)over bar>(B)(n) = [n / 3] + 1., ELSEVIER SCIENCE BV, 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
In graph theory and a study of transmission delay and fault tolerance of networks, the connectivity and the diameter of a graph are very important and they have been studied by many mathematicians. We studied the wide-diameter of a k-regular k-connected graph which is defined by the maximum of the k-distance between two distinct vertices, when the k-distance between x and y is equal to the least number / such that there exists k vertex-disjoint paths between x and y whose lengths are at most /. Because the wide-diameter of any k-regular k-connected graph is greater than its diameter, a k-regular k-connected graph whose wide-diameter is equal to "1 + its diameter" is optimal. For example, it is known that the hypercube is such a graph. We define n-dimensional toroidal mesh C(d1, d2, . . . , dn) with vertices {(X11, . . . , xn)|0 ≤ xi <
di (1 <
i <
n)}. Each vertex (x1, . . . , Xn) is adjacent to 2n other vertices: (X1 ± 1, x2, . . . , xn), (x1, x2 ± 1, . . . , xn), . . . , (x1, X2, . . . , xn ± 1), where additions are performed modulo di (1 ≤ i ≤ n). This graph is an n-dimensional orthogonal mesh with global edges, which is 2n-connected and 2n-regular. We show that the graph satisfies the above property with respect to its 2n-diameter and its diameter except for some special cases, © 1996 John Wiley &
Sons, Inc., 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
For any integers n, d ≥ 2, let P{cyrillic}(n, d) be the largest number such that every set P of n points in Rd contains two points x, y ∈ P satisfying |boxd(x, y) ∩ P| ≥P{cyrillic}(n, d), where boxd(x, y) means the smallest closed box with sides parallel to the axes, containing x and y. We show that, for any integers n, {Mathematical expression}, which improves the lower bound due to Grolmusz [9] by a short self-contained proof. © 1995 Springer-Verlag., 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
For any integers n, d greater than or equal to 2, let II(n, d) be the largest number such that every set P of n points in R(d) contains two points x, y epsilon P satisfying \box(d)(x, y)boolean AND P\ greater than or equal to II(n, d), where box,(x, y) means the smallest closed box with sides parallel to the axes, containing x and y. We show that, for any integers n, d greater than or equal to 2, 2/(2 root 2)(2d) n+2 less than or equal to II(n,d)less than or equal to 2/7([d/5])2(2d-1) n+5, which improves the lower bound due to Grolmusz [9] by a short self-contained proof., SPRINGER VERLAG, 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
Let d, n be positive integers, and P a set of n points in the d-dimensional Euclidean space. For x is-an-element-of P and epsilon=epsilon(epsilon1,...,epsilon(d)) is-an-element-of {-1,1}d, the epsilonth-orthant of x is defined by L(d)(x,epsilon):= {x+y\y=(y1,...,y(d)) is-an-element-of R(d) and epsilon(alpha)gamma(alpha) greater-than-or-equal-to 0 for any 1 less-than-or-equal-to alpha less-than-or-equal-to d-{x}. We show that if d is sufficiently large and n greater-than-or-equal-to 1.76d then there are x is-an-element-of P and epsilon is-an-element-of {-1, 1}d such that the orthant L(d)(X, epsilon) contains at least two points of P., ELSEVIER SCIENCE BV, 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
This paper presents four asymptotic conditions of smooth worldlines in Minkowski space that are often used in special relativistic particle dynamics. (A) Permanency with respect to an observer's time. (B) Permanency with respect to the proper time. (C) Finiteness of the gamma factor. (D) Intersection with the light cone of any apex. The conditions (B) and (D) are free from observers and it is verified that (A) and (C) are invariant conditions for all inertial observers. To examine the inclusion relations between (A), (B), (C) and (D), some inclusion relations are proved and some are denied by counter examples. Then the concluding Venn diagram is obtained. Such researches must interest theoretical physicists who unintentionally use one or plural number of these conditions., PHYSICAL SOC JAPAN, May 1993, JOURNAL OF THE PHYSICAL SOCIETY OF JAPAN, 62, 5, 1495-1499, English, 0031-9015, WOS:A1993LE58600022

SOME ASYMPTOTIC CONDITIONS OF WORLDLINES IN MINKOWSKI SPACE
G YONEDA; Y ISHIGAMI; S ARIMA
This paper presents four asymptotic conditions of smooth worldlines in Minkowski space that are often used in special relativistic particle dynamics. (A) Permanency with respect to an observer's time. (B) Permanency with respect to the proper time. (C) Finiteness of the gamma factor. (D) Intersection with the light cone of any apex. The conditions (B) and (D) are free from observers and it is verified that (A) and (C) are invariant conditions for all inertial observers. To examine the inclusion relations between (A), (B), (C) and (D), some inclusion relations are proved and some are denied by counter examples. Then the concluding Venn diagram is obtained. Such researches must interest theoretical physicists who unintentionally use one or plural number of these conditions., PHYSICAL SOC JAPAN, 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

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

American Mathematical Society

日本数学会

American Mathematical Society

離散数学・組合せ論への応用を意図したランダムネスと擬ランダムネスの理論
石上 嘉康
日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(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 1996 - 1996

組合せ理論における極値的問題の確率的証明手法、及びそのアルゴリズム的側面の研究
石上 嘉康
日本学術振興会, 科学研究費助成事業, 電気通信大学, 奨励研究(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