過去のセミナー (第11回~第20回)
場所: オンライン開催(Zoom)
講演者: 盧暁南 (山梨大学)
講演題目: SATソルバーの組合せデザイン問題への応用事例
講演概要: 多くの組合せ問題は制約充足問題 (Constraint Satisfaction Problem; CSP) として定式化できる. CSPを命題論理式の充足可能性判定 (Satisfiability Testing; SAT) 問題へ変換し,高速なSATソルバーにより解くことが,CSPに対する強力な解法として幅広く利用されている. 本講演では,SATソルバーを利用して組合せデザイン問題の求解に役に立つ研究事例を2つ取り上げる.まず,SAT定式化でPaley行列から準最適なlocating arrayと呼ばれる組合せデザインを構成するアプローチについて述べる. 次に,代数的特徴付けとCSP型SATソルバーを併用して位数が小さいcyclic almost difference set の数え上げに関する結果を紹介する.
場所: オンライン開催(Zoom)
講演者: 野崎隆之 (山口大学)
講演題目: 数論的符号の重み分布と多元Tenengoltz符号の符号語数
講演概要: 数論的符号とは,1つまたは複数の合同式よって規定される系列の集合であり,挿入/削除誤りや非対称誤りの訂正に用いられる.符号化率(または伝送速度)は符号の性能指標の一つであり,符号の要素数である符号語数から導出される.しかしながら,数論的符号に対する符号語数の導出は,一般に容易ではない. 本講演では,数論的符号の符号語数を導出する上で重要な役割を果たす拡張重み分布を紹介し,拡張重み分布に関する恒等式を与える.更に,数論的符号の一つである多元Tenengoltz符号の符号語数を導く.
備考: 本講演の内容は 2020 IEEE International Symposium on Information Theory (ISIT) で発表したものです.この発表の予稿は IEEE Xplore から入手できます.また, プレプリント版は Arxiv にあります.
場所: オンライン開催(Zoom)
講演者: Badri Vishal Pandey (University of Virginia)
講演題目: Ellipsoidal T-design
講演概要: (PDF Version) A spherical t-design is a finite set X of points on the unit sphere in R^n which satisfies \frac{1}{|X|} \sum_{x \in X} P(x) = \frac{1}{Vol(S^{n-1})} \int_{S^{n - 1}} P(x) d \sigma(x) for all polynomials P(x) with degree ≤ t. The right-hand side is the surface integral over S^{n−1}. Recently, Miezaki generalized this concept to arbitrary (potentially infinite) subsets T of positive integers, as opposed to the finite set of degrees ≤ t. In the case where n = 2, he used the theory of complex multiplication by Z[i] to show that there are infinitely many spherical T -designs (namely lattice points of fixed norm) for the set T = Z^+ \ 4Z. We generalize the concept of spherical T-designs to ellipses in the case of imaginary quadratic orders with class number 1. This work relies on the theory of modular forms with complex multiplication. I will also talk about my recent work with Wei-Lun which extends the work to any classnumber.
場所: オンライン開催(Zoom)
講演者: 梶浦 大起 (広島大学)
講演題目: Difference setのassociation schemeへの一般化について
講演概要: 有限群上のdifference setは古典的によく知られている数学的対象である。 講演者らは準モンテカルロ積分と呼ばれる数値積分法の手法をassociation schemeに応用することを研究している。 有限可換群においては, Turynによって有限群の部分集合上の指標の和の値が(非自明な)指標の選び方に依存しないことと,その部分集合がdifference setであることが同値であることが知られている。 我々はその一般化として,可換association schemeに対し「association scheme上の関数に対しその総和を求める際,ある部分集合上での平均が最良近似を与えること」 と「部分集合がdifference setであること」の同値性を示した。Turynの結果は,thin-association schemeの場合に対応している。
また,設定を少し変えて,可換性を仮定せず,有限群Gがtransitiveに作用するXの定めるassociation scheme(Schurian association scheme)を考える。 Xの部分集合Dがdifference setになる必要十分条件が,DのGによる軌道(Xの部分集合族となる)が2-designになることと同値であることを示した。 この条件は,point transitiveなblock transitive 2-designという概念と同値であることもわかっている。
本講演ではこれらの結果と合わせて,数値実験により得られたいくつかのassociation scheme上のdifference setの具体例を紹介する。 本研究は松本眞(広島大)・奥田隆幸(広島大)との共同研究を一部含む。
場所: 愛知県立大学サテライトキャンパス (愛知県産業労働センター15階)
講演者: Sebastian M. Cioaba (University of Delaware)
講演題目: How to address graphs and hypergraphs ?
講演概要: In the 1970s, Graham and Pollak described a way to label/address the vertices of a connected graph with words of the same length over the alphabet {0,1,*} such that one can determine the shortest path between any two vertices using these addresses. Minimizing the length of such addresses is an interesting problem with connections to linear algebra and computer science. In this talk, I will describe some recent results in this area involving Hamming, Johnson graphs and other graphs as well as the extensions of this problem to hypergraphs. Many problems are open and the talk will be accessible to undergraduate students.
場所: 愛知県立大学サテライトキャンパス (愛知県産業労働センター15階)
講演者: 伊東圭司 (東北大学 情報科学研究科)
講演題目: 隣接代数の bases of matrix units
講演概要: 可換アソシエーションスキームはその隣接行列によって張られる隣接代数をもつ。 隣接代数は2つ目の基底として原始冪等元の集合を持つことが知られており、その性質のよさから さまざまな応用・発展が研究されている。 本研究では、非可換アソシエーションスキームやコヒアラント配置の隣接代数に対しても 性質のよい2つ目の基底を構成することを目標としており、nearly multiplicity-free と呼ばれる 条件を満たすような非可換アソシエーションスキームと、ファイバー可換なコヒアラント配置に対して、 bases of matrix units と呼ばれる性質のよい2つ目の基底が構成できることを紹介する。 本研究は、宗政昭弘氏(東北大)との共同研究である。
場所: 愛知県立大学サテライトキャンパス (愛知県産業労働センター15階)
講演者: 大浦学 (金沢大学)
講演題目: 符号のヤコビ多項式
講演概要: 2元体上の有限次元ベクトル空間を符号と呼ぶことにします。 符号とモジュラー形式の対応は色々と研究されてきました。 そのなかで、小関道夫氏はモジュラー形式に関連したヤコビ形式にならって、 符号のヤコビ多項式の概念を導入しました。 今回の話しは、この話しの一般種数版についてお話しします。 本間恵太氏、岡部尭文氏との共同研究です。
場所: 愛知県立大学サテライトキャンパス (愛知県産業労働センター15階)
講演者: 中島規博 (名古屋工業大学)
講演題目: 超平面配置の高階自由性について
講演概要: Holmは自由配置の高階化としてm-自由配置を定義し,同時に超平面配置のm-自由性に関して,次の問題を提唱した. (Q1)m-自由配置は(m+1)-自由配置であるか?(Q2)すべての超平面配置は十分大きな整数mに対してm-自由であるか? Holmなどの研究により,超平面配置がジェネリック配置のときにはQ1とQ2ともに正しく, 2次元の超平面配置ではQ2が正しいことが証明されている. 一方で,九州大学の阿部拓郎氏と講演者の最近の研究により,Q1とQ2の両方に反例が与えられた. 特に,Q2の反例は4次元以上のすべての次元で構成できる. 本講演では,高階自由配置に関する基本的事実,Holmの問題の反例,3次元超平面配置に対する問題Q2について議論する.
場所: 愛知県立大学サテライトキャンパス (愛知県産業労働センター15階)
講演者: 齋藤 正顕 (名古屋文理大学 基礎教育センター)
講演題目: 正則グラフの固有ベクトルに関する Berry 予想
講演概要: リーマン面上のシュレディンガー方程式の解の半古典極限をとると, その力学系が非正則な場合には, 固有関数の値分布がガウス分布になる」ことを M.V. Berry は 1977年の論文で予想した.D.A. Hejhal らは,2001年の論文で, 複素上半平面上の CM 型 Maass 波動形式についても,Berry の予想が成り立つ という数値実験の結果を発表している. 一方で, 近年, Brooks-Lindenstrauss (2013), Anantharaman-Le Masson (2015) などの研究では, グラフ上の量子エルゴード性の 観点から「半古典極限のグラフ理論的類似」を考えている. それを踏まえて, 本講演では, グラフ理論的な Berry の予想の類似を定式化し, その数値実験について報告する. 本研究は, 長谷川武博氏(滋賀大学)と瀬川悦生氏(横浜国立大学)との共同研究である.
日時: 2018年9月14日(金) 14:00〜17:00
場所: 愛知県立大学サテライトキャンパス (愛知県産業労働センター15階)
講演者1: 伊藤 真理 (東京理科大学 理工学部) (講演時間: 14:00〜15:00)
講演題目: スケジューリング問題のモデリング: 実社会へ最適化手法を応用するために
講演概要: 実社会にはスケジューリング問題が多数存在する.近年,スケジューリング問題を解くための最適化手法に関する理論的な研究が進み,現場への応用範囲が広がりつつある.講演者が携わってきた事例研究として,児童養護施設職員のシフトスケジューリング問題,手術室のスケジューリング問題, 人間ドックのスケジューリング問題,発電プラントの保全活動スケジューリング問題,地域熱利用インフラの統廃合スケジューリング問題等がある.本講演では,実社会のスケジューリング問題例,それらの問題解決に用いられる最適化手法,講演者によるスケジューリング問題の事例研究成果の一部を紹介する.
講演者2: 阿部 敏生 (横浜国立大学 環境情報学府) (講演時間: 15:30〜17:00)
講演題目: グラフの彩色とリスト辺彩色予想について
講演概要: グラフの各頂点に隣接する頂点同士は異なるように色を与える写像をグラフの頂点彩色と呼ぶ。特に、グラフが高々k色の色で頂点彩色できるときk-彩色可能であるという。 また、グラフの各頂点に大きさkの任意の色のリストを与え、そのリストから色を上手く選ぶことでグラフの頂点彩色が構成できるとき、そのグラフはk-リスト彩色可能(k-選択的)であるという。 本講演では曲面上に埋め込まれたグラフの染色数および選択数の上界やリスト辺彩色予想に関連する結果について紹介する。