グラフ理論的言い換え

この時間帯に書き直しました。

グラフ理論を知っている人用の書き方をすると

  1. 直径2かつk-正則グラフの頂点数nの最大値
  2. 直径2かつk-正則平面グラフの頂点数nの最大値

を求めたいという問題です。定義から平面グラフか一般のグラフか分からなかったので両方用意しました。
用語説明しておくと、

直径
任意の2頂点間の最短パスの長さの最大値
k-正則
頂点の次数が全てk (各頂点から辺がk本出ているということ)
平面グラフ
頂点を適当に置き換えて辺を伸ばせば、辺が交差することなく平面に書けるということ (K_{3,3}またはK_5を含むとそれはもう平面グラフでは無い)

関連研究, 自明な上限, 具体例

Moore's boundにより, 直径2で最大次数Δのグラフの頂点数の最大値はΔ^2+1が上界であることが知られています。直径をD, 最大次数をΔとしたときの頂点数最大のグラフを構成する問題は、“degree/diameter problem”と呼ばれ、グラフ理論やデザインの文脈で研究されているようです。参考になるサーベイとして, Moore graphs and beyond: A survey of the degree/diameter problem (pdf) がありました。最新のものが知りたい場合には、The (Degree,Diameter) Problem for Graphsに2008年5月時点の記録が纏まっています。

最大値の上限

  • またHoffmanとSingletonによって、k=2,3,7の場合は頂点数がk^2+1と上限ぴったりのグラフが存在します。また彼らによって2,3,7,57以外では頂点数k^2+1となるグラフが存在しないことが示されています。
  • Erdős, Fajtlowicz, Hoffman (1980) によって, C4 (頂点数4の巡回路または正方形) を除くと, Δ^2ぴったりは無理ということが示されています。
    • 実は、KurosawaとTsujii *1 (1981), BannaiとIto (1981) によって, 一般の直径に拡張されているとか。

一般的な下界

一般的な下界として、以下が知られています。

  • 逆に頂点数をnmとすると, (n+m-2)正則なグラフが作れます。構成法はRook's Graphを参照のこと。K_nとK_mから作るイメージ。

以上よりRook's Graphの構成法を使うと, n=m=76と取れば, 150-正則でも頂点数5776が実現できるということになりました。うまく作れば頂点数20000超えも出来るかも知れません。

k正則の例

最大値が分かっている例としては、

が与えられています。
また、

  • k=11:頂点数が104の例、(目標は105以上120以下)
  • k=13:頂点数が136の例、(目標は137以上168以下)
  • k=16:頂点数が198の例、(目標は199以上255以下)

というグラフがあります。

未解決問題

どうも, k=57のときに, 頂点数3251 = 57^2+1 となる例があるかどうかが未解決だそうです。これを解けばいい雑誌に載りますので頑張ってください。
また, 一般のk (≠2,3,7,57) では, k^2-1が良い上界なのでこれを達成出来ると良いそうです。とりあえずD=8でも頂点数57までしか知られていないので、これが狙い目ぽい。頂点数60を超えると凄いですね、という話。

話題を知ったところ

*1:調べたら, 現在暗号で有名な黒澤・辻井でした。

*2:計算機で全探索したら6つ程見つかったとか。See:Molodtsov “Largest Graphs of Diameter 2 and Maximum Degree 6”。ただこれが最大値かどうかはMolodtsovさんとそのプログラムを信頼するかどうかの様子。

本題とは関係無い。

b:id:harutabe あんま言いたくないけどこれがもし玻じゃなくて璽とか凹とかだったら「まあ、ルールだから」ってなるんじゃあないかと思うんですよ。その「ルール教徒」とは、あなたの想像上の存在にすぎないのでは?

そういえば、璽も凹も常用漢字なので、両方とも名付けに使える。ルール上セーフという話。
璽も凹も使えて玻がダメってのは不思議ですね、はい。

Gentryの博士論文

Craig Gentry's PhD Thesis
まさかのFully Homomorphic Encryption単体でした. 200ページあるので皆さん頑張って読みましょう. 技術的なところだけで170ページ位あります.
ちらっと見た限りでは, 鍵生成や暗号化の方法を変えることでイデアル格子のSIVPから平均時の困難性を示しているんですが, 量子計算機使って素因数分解を行うことで帰着を行うという話になっています. これまでの格子の最悪時/平均時では見られなかった手法なので要注目.

Signcryptionの本が出るらしい.

Boyenのサイト見てたら,

Xavier Boyen, Identity-Based Signcryption, invited chapter, to appear in (eds.) A. Dent, Y. Zheng, Practical Signcryption, Springer, 2009.

というのがあった.
同様に,

J. Baek and R. Steinfeld, Security for Signcryption: The Multi-User Model, Practical Signcryption, Y. Zheng and A. Dent (eds.), Springer-Verlag, 2009, to appear.

とかも.