Affiliation |
Faculty of Environment and Information Sciences, Division of Social Environment and Information |
Job Title |
Associate Professor |
Research Fields, Keywords |
Graph Theory, Discrete Mathematics |
YNU Research Center |
Research Center for Topological Graph Theory |
Related SDGs |
OZEKI Kenta
|
YNU Research Center 【 display / non-display 】
-
Research Center for Topological Graph Theory
Education 【 display / non-display 】
-
-2009.3
Keio University Doctor Course Completed
Degree 【 display / non-display 】
-
Doctor of Science - Keio University
-
Master of Science - Keio University
Campus Career 【 display / non-display 】
-
2019.4
Duty Yokohama National UniversityFaculty of Environment and Information Sciences Division of Social Environment and Information Associate Professor
-
2017.2-2019.3
Duty Yokohama National UniversityFaculty of Environment and Information Sciences Division of Social Environment and Information Specially Appointed Associate Professor
-
2021.4
Concurrently Yokohama National UniversityInterfaculty Graduate School of Innovative and Practical Studies Associate Professor
-
2019.4
Concurrently Yokohama National UniversityGraduate School of Environment and Information Sciences Department of Information Media and Environment Sciences Associate Professor
-
2019.4
Concurrently Yokohama National UniversityGraduate School of Environment and Information Sciences Department of Information Environment Associate Professor
External Career 【 display / non-display 】
-
2012.11-2017.1
National Institute of Informatics
Research Areas 【 display / non-display 】
-
Natural Science / Applied mathematics and statistics
Books 【 display / non-display 】
-
中本 敦浩 , 小関 健太( Role: Sole author)
サイエンス社 ( ISBN:9784781915692 )
Language:Japanese Book type:Scholarly book
-
IT Text 離散数学
松原良太,大嶌彰昇,藤田慎也,小関健太,中上川友樹,佐久間雅,津垣正男( Role: Joint author , 4章 グラフと木)
オーム社
Language:Japanese Book type:Textbook, survey, introduction
情報系を学ぶ学生にとっての基礎数学として、わかりやすい言葉と高校までに学んだ範囲で離散数学を基礎からていねいに解説した教科書。システム開発者や他分野の方にも基礎概念の整理に役立つ一冊。
Thesis for a degree 【 display / non-display 】
-
Hamilton Cycles, Paths and Spanning Trees in a Graph
Kenta Ozeki
2009.3
Doctoral Thesis Single Work
Papers 【 display / non-display 】
-
A 2-Bisection with Small Number of Monochromatic Edges of a Claw-Free Cubic Graph
Eom Seungjae, Ozeki Kenta
GRAPHS AND COMBINATORICS 39 ( 1 ) 2023.2 [Reviewed]
Language:English Publishing type:Research paper (scientific journal) Joint Work
-
Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings
Mao Yaping, Ozeki Kenta, Robertson Aaron, Wang Zhao
JOURNAL OF COMBINATORIAL THEORY SERIES A 193 2023.1 [Reviewed]
Language:English Publishing type:Research paper (scientific journal) Joint Work
-
Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity a la Nash-Williams
Ito Takehiro, Iwamasa Yuni, Kakimura Naonori, Kamiyama Naoyuki, Kobayashi Yusuke, Maezawa Shun-Ichi … Show more authors
Ito Takehiro, Iwamasa Yuni, Kakimura Naonori, Kamiyama Naoyuki, Kobayashi Yusuke, Maezawa Shun-Ichi, Nozaki Yuta, Okamoto Yoshio, Ozeki Kenta Hide authors
ACM TRANSACTIONS ON ALGORITHMS 19 ( 1 ) 2023.1 [Reviewed]
Language:English Publishing type:Research paper (scientific journal) Joint Work
-
On Reachable Assignments Under Dichotomous Preferences
Ito Takehiro, Kakimura Naonori, Kamiyama Naoyuki, Kobayashi Yusuke, Nozaki Yuta, Okamoto Yoshio, Oz … Show more authors
Ito Takehiro, Kakimura Naonori, Kamiyama Naoyuki, Kobayashi Yusuke, Nozaki Yuta, Okamoto Yoshio, Ozeki Kenta Hide authors
PRIMA 2022: PRINCIPLES AND PRACTICE OF MULTI-AGENT SYSTEMS 13753 650 - 658 2023 [Reviewed]
Language:English Publishing type:Research paper (scientific journal) Joint Work
-
Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane
Ozeki Kenta
COMBINATORICA 42 ( SUPPL 2 ) 1451 - 1480 2022.12 [Reviewed]
Language:English Publishing type:Research paper (scientific journal) Single Work
Review Papers 【 display / non-display 】
-
エレガントな解答を求む 2023年5月号出題 1
小関 健太
数学セミナー 2023.5
Language:Japanese Publishing type:Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media) Publisher:日本評論社 Single Work
-
エレガントな解答を求む 2022年4月号出題 2
小関 健太,松本直己
数学セミナー 2022.4
Language:Japanese Publishing type:Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media) Publisher:日本評論社 Joint Work
-
エレガントな解答を求む 2021年4月号出題 2
小関 健太
数学セミナー 2021.4
Language:Japanese Publishing type:Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media) Publisher:日本評論社 Single Work
図1 はあるホテルの見取り図で,斜線部が部屋で白
い部分が廊下を表している.すべての廊下には電灯が
ついており,丸数字が表すスイッチにより隣接する廊
下の電灯のon–off を切り替えられる.ただし1 つの
スイッチは連動しており,例えば1 のスイッチを押す
と,図2 のように,1 と2 の間の廊下,1 と3 の間の
廊下,1 と4 の間の廊下の3 つの電灯のon–off が同時
に変わってしまう.(他の廊下の電灯のon–off は変わ
らない)
(1) 以下のどの状況のときに全部の廊下の電灯をoff に
できるでしょうか?
(A) 全部の電灯がon.
(B) 1 と2 の間の廊下と5 と6 の間の廊下だけ
電灯がoff,他はon,
(C) 1 と2 の間の廊下と4 と5 の間の廊下だけ
電灯がoff,他はon,
(2) 他の状態からはじめたときや別のホテルでも考え
てみてください.すべてをoff にできるための必
要十分条件を,すっきりした形で言えないでしょ
うか?
(1) のみの解答でも構いませんので,ぜひ考えてみて
ください. -
エレガントな解答を求む 2020年4月号出題 2
小関 健太,阿部 敏生
数学セミナー 2020.4
Language:Japanese Publishing type:Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media) Publisher:日本評論社 Joint Work
平面上にある点の集合 S に対し,次の 3 つのルールで何本かの線を引くことを考える.
各線は S のある点からスタートし,S の点をちょうど 1 つ通過し S の点で終わる.
線同士は S の点以外で交差しない(各線は自分自身とも S の点以外では交差できない).
S の各点で線の出入りは合計 3 回まで可能である.
例えば図 1 のように進行すると,3 本の線を引いた時点ですべての点で線の出入りがちょうど 3 回行われ,これ以上線が引けなくなる.特に,各線はスタートの点を通過したり,S の同じ点に戻ってきたりしてもよいことに注意されたい.一方で図 2 のように進行すると,線を 2 本引いた時点で線が引けなくなってしまう.
(1) S が 6 点のとき,最大で何本の線が引けるか ?
(2) S が 6 点のとき,それ以上線が引けなくなるまでに少なくとも何本の線を引く必要があるか ?
余裕のある方は,S が n 点のときも考えてみてください. -
ネットワークとグラフ理論
小関 健太
数理科学 2020.2
Language:Japanese Publishing type:Article, review, commentary, editorial, etc. (trade magazine, newspaper, online media) Publisher:株式会社サイエンス社 Single Work
Awards 【 display / non-display 】
-
2014年度 応用数学研究奨励賞
2015.3 日本数学会 応用数学分科会 (g, f)-factors in directed graphs
Individual or group name of awards:小関健太
-
日本数学会賞建部賢弘賞奨励賞
2013.3 日本数学会
Individual or group name of awards:小関健太
Grant-in-Aid for Scientific Research 【 display / non-display 】
-
グラフの彩色手法の発展と高次元超多面体グラフの彩色
Grant number:23K03195 2023.4 - 2027.3
科学研究費補助金 Grant-in-Aid for Scientific Research(C)
Investigator(s):小関 健太
Grant type:Competitive
-
多面体的グラフにおける閉路の諸問題
Grant number:22F22331 2022.11 - 2025.3
Grant-in-Aid for JSPS Fellows
Authorship:Other Grant type:Competitive
-
グラフの strong Gallai-Ramsey 理論の提案と発展
Grant number:22F20324 2022.4 - 2024.3
Grant-in-Aid for JSPS Fellows
Authorship:Other Grant type:Competitive
-
数学アプローチによる組合せ遷移の展開:活用事例を手がかりとして新解法へ
Grant number:20H05795 2020.10 - 2023.3
Authorship:Coinvestigator(s)
-
被覆グラフを利用した巨大グラフ解析へのアプローチ
Grant number:19H01803 2019.4 - 2022.3
Grant-in-Aid for Scientific Research(B)
Other external funds procured 【 display / non-display 】
-
グラフのハミルトン閉路に関する Nash-Williams と Grunbaum 予想の解決
2014.11 - 2015.11
The Sumitomo Foundation 住友財団 基礎科学研究助成
Investigator(s):小関 健太
グラフとは,頂点集合と辺集合(頂点集合の二元部分集合族)からなる構造として定義される.グラフの全ての頂点をちょうど一度ずつ通る閉路をハミルトン閉路と呼び,ちょうど一度ずつ通る道をハミルトン道と呼ぶ.「与えられたグラフがハミルトン閉路をもつかどうか決定する」という問題は,組み合わせ最適化の分野において特に重要な巡回セールスマン問題とも密接に関係しているため,グラフ理論の中でも非常に多くの研究がなされている.
ここで, グラフを平面グラフなどトポロジー的な閉曲面上のものに限ると,この問題は四色定理とも関わりを持つこともあり,多くの研究が行われている.本研究もこの流れに沿うものである.閉曲面上のグラフのハミルトン性については,表 1 にあるように 1956年の Tutte の結果以来様々な研究者が研究を行ってきた.例えば,1983年に Thomassen が「平面上の任意の 4-連結グラフはハミルトン連結である」と示したことを意味している.なお,グラフが,``任意の 2頂点に対し,それらを結ぶハミルトン道が存在する'' という性質を満たすとき,ハミルトン連結であるという.
このように,この分野についていくつかの結果が示されているが,未解決な部分も存在する.特に,次の命題は,40年以上未解決であり,グラフ理論全体の中でも重要なものとなっている.この予想の完全解決が研究の目的である.
予想 (Grunbaum `70, Nash-Williams `73)
トーラス上の任意の 4-連結グラフはハミルトン閉路を持つ.
Presentations 【 display / non-display 】
-
Kempe equivalence classes on 3-edge-colorings in cubic graphs
Kenta Ozeki [Invited]
2023 Joint Mathematics Meetings
Event date: 2023.1
Language:English Presentation type:Oral presentation (invited, special)
-
3-連結平面 3-正則グラフの Kempe 同値類の数
小関健太
第34回 位相幾何学的グラフ理論研究集会
Event date: 2022.11
Language:Japanese Presentation type:Oral presentation (general)
-
グラフの出次数制約のある向き付け
小関健太
第31回 位相幾何学的グラフ理論研究集会
Event date: 2019.11
Language:English Presentation type:Oral presentation (general)
-
An orientation of graphs with out-degree constraint
Kenta Ozeki [Invited]
The 2nd East Asia Workshop on Extremal and Structural Graph Theory
Event date: 2019.11
Language:English Presentation type:Oral presentation (invited, special)
-
Spanning trees with few leaves in graphs on surfaces
Kenta Ozeki [Invited]
International Conference on Graph Theory, Combinatorics and Applications
Event date: 2019.6
Language:English Presentation type:Oral presentation (general)
Charge of on-campus class subject 【 display / non-display 】
-
2023 Discrete Mathematics II
College of Engineering Science
-
2023 Discrete Mathematics I
College of Engineering Science
-
2023 Graph Theory
College of Engineering Science
-
2023 Advanced Mathematical Information Ⅱ
Interfaculty Graduate School of Innovative and Practical Studies
-
2023 Advanced Mathematical Information Ⅰ
Interfaculty Graduate School of Innovative and Practical Studies