トゥラングラフ

トゥラングラフ
トゥラングラフT(13,4)
名前の由来	パル・トゥラン
頂点	${\displaystyle n}$
エッジ	〜${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}}$
半径	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{otherwise}}\end{array}}\right.}$
直径	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{otherwise}}\end{array}}\right.}$
胴回り	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{otherwise}}\end{array}}\right.}$
彩色数	${\displaystyle r}$
表記	${\displaystyle T(n,r)}$
グラフとパラメータの表

トゥラングラフは と表記され、完全な多部グラフである。これは、頂点の集合を可能な限り等しい大きさの部分集合に分割し、2つの頂点が異なる部分集合に属する場合に限り、辺で接続することによって形成される。 と は を で割った商と余りである（したがって）とすると、グラフは の形をとり、辺の数は である。 ${\displaystyle T(n,r)}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle q}$ ${\displaystyle s}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle n=qr+s}$ ${\displaystyle K_{q+1,q+1,\ldots ,q,q}}$

${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}-s^{2}}{2}}+{s \choose 2}}$ 。

の場合、この辺数はより簡潔に と表すことができます。グラフにはサイズ の部分集合とサイズ の部分集合があり、各頂点の次数はまたは です。が で割り切れる場合（つまり の場合）、これは正則グラフです。 ${\displaystyle r\leq 7}$ ${\displaystyle \left\lfloor \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}\right\rfloor }$ ${\displaystyle s}$ ${\displaystyle q+1}$ ${\displaystyle rs}$ ${\displaystyle q}$ ${\displaystyle nq-1}$ ${\displaystyle nq}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle s=0}$

トゥランの定理

トゥラン グラフは、極値グラフ理論の重要な成果であるトゥランの定理を証明するために使用したパル トゥランにちなんで名付けられました。

鳩の巣原理によ​​り、 トゥラングラフのr + 1 頂点の各集合には、同じ分割部分集合内の 2 つの頂点が含まれる。したがって、トゥラングラフにはサイズ r + 1 のクリークは含まれない 。トゥランの定理によると、トゥラングラフは、n頂点を持つすべての ( r  + 1)-クリークフリーグラフの中で、最大数の辺を持つ 。Keevash & Sudakov (2003) は、トゥラングラフは、α が 1 に十分近い場合、 α n頂点のすべての部分集合が少なくとも 辺に広がる、 順序nの唯一の ( r + 1)-クリークフリーグラフでもあることを示している。 ^[1]エルデシュ–ストーン定理は、固定されたトゥラングラフを部分グラフとして持たないグラフの辺の数を制限することで、トゥランの定理を拡張している。この定理により、サブグラフの 彩色数に応じて、任意の除外サブグラフに対して極値グラフ理論における同様の境界を証明できます。${\displaystyle {\frac {r\,{-}\,1}{3r}}(2\alpha -1)n^{2}}$

特殊なケース

八面体 は3次元交差多面体であり、その辺と頂点はK _2,2,2、つまりトゥラングラフT (6,3) を形成する。この面心投影では、連結されていない頂点は同じ色で示されている。

トゥラン グラフの パラメータrをいくつか選択すると、独立して研究された注目すべきグラフが生成されます。

トゥラングラフT (2 n , n ) は、完全グラフK _{2 n}から完全マッチングを取り除くことで形成できる。ロバーツ (1969) が示したように、このグラフはちょうどn の箱型度を持つ。ロバーツグラフと呼ばれることもある。^{[2]このグラフは}n次元交差多面体の1-スケルトンでもある。例えば、グラフT (6,3) =  K _2,2,2は正八面体グラフ、つまり正八面体のグラフである。n組のカップルがパーティーに行き、各人がパートナー以外のすべての人と握手すると、このグラフは行われる握手の集合を表す。このため、カクテルパーティーグラフとも呼ばれる。

トゥラングラフT ( n ,2) は完全二部グラフであり、n が偶数の場合にはムーアグラフとなる。rがnの約数である場合にはトゥラングラフは対称かつ強正則となるが、一部の研究者はトゥラングラフを強正則性の自明なケースとみなし、強正則グラフの定義から除外している。

トゥラングラフのクラスは指数関数的に多くの極大クリークを持つことができるため、このクラスには少数のクリークは存在しない。例えば、トゥラングラフには3 ^a 2 ^{b 個}の極大クリークがあり、3 a  + 2 b  =  nかつb ≤ 2 である。各極大クリークは、各分割部分集合から1つの頂点を選択することで形成される。これは、グラフの辺の数に関わらず、すべてのn頂点グラフ の中で最大となる極大クリークの数である。これらのグラフはムーン・モーザーグラフと呼ばれることもある。^[3]${\displaystyle T(n,\lceil n/3\rceil )}$

その他の特性

全てのトゥラングラフはコグラフである。つまり、個々の頂点から互いに素な和と補の演算の列によって形成される。具体的には、そのような演算列は、トゥラングラフの各独立集合を、孤立した頂点の互いに素な和として形成することから始まる。そして、グラフ全体は、これらの独立集合の補集合の互いに素な和の補集合となる。

Chao & Novacky (1982) は、トゥラングラフが彩色的に唯一であることを示した。つまり、他のグラフは同じ彩色多項式を持たない。Nikiforov (2005) は、トゥラングラフを用いて、グラフとその補グラフのk番目の固有値の合計の下限を与えた。 ^[4]

Falls、Powell、Snoeyink（2003）は、データをグラフとして表現し、大きなTuránサブグラフを検索することで、ゲノムデータ内の遺伝子の相同グループのクラスターを見つけるための効率的なアルゴリズムを開発しました。^[5]

トゥラングラフは幾何学的グラフ理論に関連した興味深い特性もいくつか持っている。Pór & Wood (2005) はトゥラングラフの任意の3次元グリッド埋め込みの体積について Ω(( rn ) ^3/4 )の下限を与えている。 ^{[6] Witsenhausen (1974) は、} R ^d内の単位直径を持つn点間の距離の二乗和が最大となるのは、トゥラングラフを正則単体の頂点に埋め込むことで形成される構成であると予想している。^[7]

n頂点グラフGがトゥラングラフT ( n , r ) の部分グラフである場合、かつその場合のみ、Gはr色で均等彩色可能である。トゥラングラフを独立集合に分割することは、 Gを色クラスに分割することに対応する。特に、トゥラングラフは、r色で均等彩色可能な唯一の最大n頂点グラフである。

注記

1. Keevash & Sudakov (2003).
2. ロバーツ (1969).
3. ムーン＆モーザー（1965年）。
4. チャオ＆ノヴァッキー（1982年）。
5. フォールズ、パウエル、スノイインク（2003年）。
6. Pór＆Wood（2005年）。
7. ヴィッツェンハウゼン（1974年）。

参考文献

• Chao, CY; Novacky, GA (1982). 「最大飽和グラフについて」.離散数学. 41 (2): 139– 143. doi : 10.1016/0012-365X(82)90200-X .
• Falls, Craig; Powell, Bradford; Snoeyink, Jack (2003). 「Turán型グラフを用いた高厳密性COGの計算」(PDF) .
• Keevash, Peter; Sudakov, Benny (2003). 「禁制部分グラフを持つグラフにおける局所密度」(PDF) .組合せ論、確率、計算. 12 (2): 139– 153. doi :10.1017/S0963548302005539. S2CID  17854032.
• Moon, JW; Moser, L. (1965). 「グラフのクリークについて」. Israel Journal of Mathematics . 3 : 23–28 . doi :10.1007/BF02760024. S2CID  9855414.
• ニキフォロフ, ウラジミール (2007). 「ノルドハウス・ガドゥム型の固有値問題」.離散数学. 307 (6): 774– 780. arXiv : math.CO/0506260 . doi : 10.1016/j.disc.2006.07.035 .
• Pór, Attila; Wood, David R. (2005). 「3Dにおける3次元の直線化」Proc. Int. Symp. Graph Drawing (GD 2004) . Lecture Notes in Computer Science no. 3383, Springer-Verlag. pp.  395– 402. doi :10.1007/b105810. hdl : 11693/27422 .
• Roberts, FS (1969). Tutte, WT (編). 「グラフの箱型性と立方性について」. Recent Progress in Combinatorics : 301– 310.
• トゥラン、P. (1941)。 「Egy gráfelméleti szélsőértékfeladatrol (グラフ理論の極限問題について)」。マテマティカイ エス フィジカイ ラポック。48 : 436–452 .
• Witsenhausen, HS (1974). 「直径制約下における距離の二乗和の最大値について」アメリカ数学月刊誌. 81 (10): 1100–1101 . doi :10.2307/2319046. JSTOR  2319046.

外部リンク

• ワイスタイン、エリック・W.「カクテルパーティーグラフ」。マスワールド。
• ワイスタイン、エリック・W.「八面体グラフ」。MathWorld。
• ワイスタイン、エリック・W.「トゥラン・グラフ」。マスワールド。
• 被覆設計データ – Klas Markström が管理する極値ハイパーグラフと被覆設計のデータベース