博士（理学）, 早稲田大学

自然科学一般, 応用数学、統計数学

自然科学一般, 数学基礎

情報通信, 情報学基礎論

受賞日 1993年
小野梓記念学術賞
日本国

受賞日 1993年
Onoazusa Memorial Award(Academic Award)

受賞日 1992年
大川功賞
日本国

受賞日 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, 出版日 1997年05月, 査読付, 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).
研究論文（学術雑誌）, 英語

離散構造の中の擬ランダム性（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., 出版日 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とその周辺

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, 出版日 2003年04月, JOURNAL OF GRAPH THEORY, 42巻, 4号, 掲載ページ 276-296, 英語, 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, 出版日 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

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, 出版日 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
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, 出版日 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
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, 出版日 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
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, 出版日 2002年02月, DISCRETE MATHEMATICS, 245巻, 1-3号, 掲載ページ 127-137, 英語, 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, 出版日 2002年02月, DISCRETE MATHEMATICS, 245巻, 1-3号, 掲載ページ 127-137, 英語, 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, 英語, 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, 英語, 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, 英語, 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, 出版日 2001年05月, JOURNAL OF GRAPH THEORY, 37巻, 1号, 掲載ページ 37-47, 英語, 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, 英語, 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, 出版日 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

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, 英語, 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, 英語, 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, 出版日 1997年04月, DISCRETE APPLIED MATHEMATICS, 74巻, 2号, 掲載ページ 123-134, 英語, 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, 出版日 1996年11月, DISCRETE MATHEMATICS, 159巻, 1-3号, 掲載ページ 279-283, 英語, 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, 出版日 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
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, 出版日 1996年05月, DISCRETE MATHEMATICS, 151巻, 1-3号, 掲載ページ 15-18, 英語, 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, 出版日 1996年05月, DISCRETE MATHEMATICS, 151巻, 1-3号, 掲載ページ 15-18, 英語, 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, 英語, 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, 出版日 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
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, 英語, 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, 出版日 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
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, 出版日 1993年05月, JOURNAL OF THE PHYSICAL SOCIETY OF JAPAN, 62巻, 5号, 掲載ページ 1495-1499, 英語, 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, 出版日 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年

American Mathematical Society

日本数学会

American Mathematical Society

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