2024年5月31日金曜日

高次元エクスパンダーの集中講義をしました

東北大数学科で高次元エクスパンダーに関する集中講義を行いました。講義資料は私のページから誰でも無料で見れるようになっています。集中講義ではランダムウォークを定義し、エクスパンダーグラフを定義しAlon-Boppanaの定理の証明概要を与えてラマヌジャングラフの話だけをして、単体複体の定義とそのエクスパンダー性を定義して、最後にマトロイドを定義し基交換ウォークの混交性を証明しました。高次元エクスパンダーに関する日本語のちゃんとした解説資料は自分の知る限り全くといって良いほどないので、この概念を日本に輸入する上で非常に大きな意義のある講義/講義資料になっていると自負しています。嬉しいことに資料も非常に多くの人に好評をいただけました。

そもそも集中講義を受講したことがなくどのようなものかすら全く知らなかったのですが、私が行った集中講義ではまず最初に談話会と呼ばれる1時間程度の講演を行い、その翌日から4日間、15時から19時くらいまで黒板を使って定理の証明とかキモチを語るというものでした。実際やってみるまでどのような雰囲気かわからなかったのでとりあえず全力で講義資料を準備したおかげで講義そのものは全体的にスムーズに進み、マトロイドの基交換ウォークの混交性の証明までちゃんと話せたのは非常に良かったです。ちなみに談話会では自己紹介的な側面もあるらしく、どんな内容でも良いもののある程度自分の研究トピックに絡んだものであるのが良さそうです。聴衆はピュアマスの人が多いでしょうから、やはりピュアマスのTCSにおける応用の話をするとものすごく食いつきが良かったです。

ピュアマスの方々は黒板での議論を好むというイメージは昔からなんとなくあったものの、予想以上でした。最適化理論のサマースクールという位置付けで毎年夏に行われる組合せ最適化セミナーでは3日間、各日にそれぞれ1名の講演者が計3時間の講義をスライドを用いて行うというものがあるのですが、私の集中講義は毎日4時間を4日間の計16時間あったわけですので時間の単純計算で組合せ最適化セミナーの講師を5回務めたことになったわけです(講義資料の準備も考えるともっとありそう)。

一方でスライドでの発表と違って聴衆の咀嚼のスピードに合わせてこちらの講義のスピードも調節できるというのが黒板発表の大きなメリットであるように感じました。もちろん、これは聴衆が忍耐強く頑張って咀嚼してくれるというのが前提の話になりますが。

聴衆はそれなりに多くの方に来ていただけました。何人かの学生にも積極的に核心をついた質問やご指摘をいただき、自分の講義資料のどの部分が良くないかなどを見直す良いきっかけになりました。

数学科で集中講義をするという機会はなかなかないかもしれませんが、やはり応用を見据えていくにつれこのような機会は将来的に他の方も経験するようなことがあるかもしれません。(当たり前なことも含まれていますが)板書で講義をする機会のある人のためにいくつか助言を残しておくと

  • 講義資料はちゃんと作った方がよい(特に、各日にどこからどこまで話すかは事前に決めるべき)
  • 私の資料の各章はある程度具体例をスキップしても話すと1日4時間くらいかかります。これが目安になると思います
  • やはり細かい証明を与える前にまずその概要とか道筋を話すと聴衆の食いつきが良い
  • 一方で直感的な説明や式変形だけを資料に書いてしまうと、厳密に式を追いたい人は満足しないので、資料には書いておいた方が良い
  • 既存結果は誰がいつ発表したものかはちゃんと把握しておいた方が良い (誰が証明したのか?と聞かれることもある)
  • 基本的に白と黄色で説明するのが多分良い (教室依存だけど赤とかだと場所によっては見づらくなりうる)
などでしょうか。おかげさまで講義終了後に飲んだビールと食べた牛タンはめちゃくちゃ美味しかったです。ありがとうございました。



Håstadのスイッチング補題

回路計算量の理論における重要な結果の一つである Håstadのスイッチング補題 を紹介します. 簡潔にいうとこの補題は, 99%の変数をランダムに固定することによってDNFの決定木が小さくなることを主張する結果です. 応用としてparity関数に対する$\mathrm{AC}^0...