研究部会だより

離散システム研究部会について

離散システム研究部会は，1990年の応用数理学会設立に合わせて発足した最古の研究部会です．

一口に「離散システム」といっても，その対象となる分野は相当広範囲なものになると考えられるが， とりあえずは「離散システム研究部会」＝「離散構造を有するシステムの理論とアルゴリズムの研究部会」と考えていただければよいであろう．

これは，初代主査の藤重悟先生が寄せられた1991年の研究部会だよりの第一文です．要は離散的でありさえすれば，分野を問わず，研究対象になります．

当初の活動は，世界的に活躍する研究者によるチュートリアル講演会の開催でした．その記録は，「離散構造とアルゴリズム」シリーズ1～7として近代科学社から刊行されました．現在は，アマゾンオンデマンドから入手できるようになっています．このシリーズでは，離散システムに関わる様々なトピック―基本的なものから非常に高度なものまで（「試し読み」で目次をごらんください）―が扱われる世界的にも類のない書物で，私自身，学生時代よりこのシリーズで勉強しましたが，離散システム研究の発展・研究者育成に多大な貢献をしてきました．

現在の離散システム研究部会の活動は，年会と研究部会連合発表会でのオーガナイズドセッションの開催のみとなっていてやや淡泊な状況ではありますが，まずは当研究部会の存在感を高めることを目標にして活動していきたいと思います．

当研究部会の最近の講演・話題をいくつか紹介します．系統組合せ論（phylogenetic combinatorics）は，生命進化の系統樹・ネットワークの推定に関わる離散構造とアルゴリズムを研究する新しい分野です．早水桃子「Tree-based networkの構造定理と系統樹推定に関する諸問題への応用」(2018年度研究部会連合発表会)では，Tree-based networkと呼ばれる系統ネットワークに対する構造定理が示され，それに基づいて，系統樹推定にまつわる諸問題に対して高速アルゴリズムが与えられました．この発表には，優秀講演賞が贈られました．

佐竹翔平「On pseudo-randomness of digraphs and ranking tournaments」(2019年度年会OS)では，擬ランダムネスをもつ完全グラフの向き付け（トーナメント）の明示的構成問題（Erdős-Moon問題）に対して，組合せ論におけるdifference methodを用いた新しい解答例が示されました．この発表には，若手優秀講演賞が贈られました．

当研究部会の伝統的トピックとして，シンボリック行列（変数を含む行列）のランク計算があります．行列ランクの計算はシステムの自由度を決める基本的な問題として現れますが，２部マッチングや線形マトロイドに関わる組合せ最適化問題の一般化ともみなせます．この事実に基づくシステム解析へのアプローチは，「離散構造とアルゴリズムI」の第２章「マトロイドとシステム解析」（室田一雄著）の主題でもありました．ごく最近になって，「変数たちが非可換である」と緩和(!?)した「非可換ランク」の概念が導入され，このテーマが新たな展開を見せています．2020年度年会OSでは非可換ランクに関連する講演が２件ありました．

構造物・フレームワークの剛性もシンボリック行列のランクで決まります．2次元フレームワークの剛性については，組合せ的な特徴付け（Lamanの定理）が知られていますが，これを３次元に拡張することは，剛性理論の永年の未解決問題となっています．谷川眞一「グラフ上の極大K_tマトロイド予想」（2020年度年会OS）では，抽象的３次元剛性マトロイドと２次スプラインから決まるマトロイドが同値である，というWhiteleyの予想の解決が示されました．この結果は，上記未解決問題の解決へ向けた大きな進展で，組合せ論の世界的に著名なブログでも取り上げられるほどです．このような凄い成果の発表が行われることも当研究部会の大きな特徴と魅力といえるでしょう．

離散システム研究部会のwebページからは，最近の発表リストが見られます．暗号，乱数，ゲーム理論といった話題も扱われています．また，数値積分とも関連が深いデザイン理論の発表も増えてきました．年会や研究部会連合発表会の際は，ぜひ，離散システム研究部会のセッションをのぞいていただければと思います．なにかピンとくる講演にあたると思います．そこから研究部会の枠を超えたコラボレーションやムーヴメントが生まれることを期待します．

藤重悟先生と室田一雄先生から初期の活動について情報提供をいただきました．この場をかりて感謝します．