DIE KOMPONENTENVERTEILUNG VON GESÄTTIGTEN

TEILGRAPHEN IN BAUMFAMILIEN

Gerd Baron und Michael Drmota

Technische Universität Wien

Ein Teilgraph H eines Graphen G (mit Knotenmenge V (G) und Kantenmenge E(G)) heißt gesättigt, wenn eine Kante (v, w) ∈ E(G) in E(H) enthalten ist, sobald die Knoten v, w in V (H) liegen. Es bezeichne g_{klm}(G) (m = (m_{1}, m_{2}, …)) die Anzahl der gesättigten Teilgraphen H von G mit |V (H)| = k, |E(H)| = l und m_{j} (Zusammenhangs-) Komponenten mit j Knoten (j ≥ 1).

Es sei F eine einfach erzeugte Baumfamilie von ebenen Wurzelbäumen, die durch eine Potenzreihe φ(t) = ∑_{i≥0} φ_{i}t^{i} (φ_{0} = 1) charakterisiert wird, mit Hilfe derer jedem ebenen

Wurzelbaum T ein Gewicht ω(T) zugeordnet wird, sodaß ω(T) > 0 nur für Bäume T aus

F gilt. (Siehe [MM].) Ist nun C(x, y, z, v) = ∑_{n,k,l,m} c_{nklm}x^{n}y^{k}z^{l}v^{m} (v = (v_{1}, v_{2}, …), v^{m} =

v_{1}^{m_{1}}v_{2}^{m_{2}} ⋯)) die (formale) erzeugende Funktion der Größen c_{nklm} = ∑_{|V (T)|=n} ω(T)g_{klm}(T),

so erfüllt diese, wie in [BD] gezeigt wurde, die Funktionalgleichung

\begin{aligned}C & = xφ(C) + xyφ (zC + (1 − z)xφ(C) + ∑_{j≥1}(1 − v_{j})(xyz)^{j} \frac{1}{j}[t^{j−1}]φ (xφ(C) + t)^{j}) \\ & − ∑_{j≥1}(1 − v_{j})(xy)^{j}z^{j−1} \frac{1}{j}[t^{j−1}]φ (xφ(C) + t)^{j} . \end{aligned} (1)

Sei weiters J eine endliche Menge positiver ganzer Zahlen und c_{nklm_{J}} = ∑_{m_{j},j∉J} c_{nklm} (m_{J} =

(m_{j})_{j∈J}), dann ist C(x, y, z, v_{J}) die erzeugende Funktion dieser Zahlen, wobei in v für j ∉ J v_{j} = 1 gesetzt wird. (Entsprechend ist C(x, y, 1, v_{J}) die erzeugende Funktion von Größen c_{nk·m_{J}}, usw.)

Ist nun (X_{n}^{J}) eine Folge von Zufallsvektoren der Dimension |J|+2 mit P[X_{n}^{J} = (k, l, m_{J})] = c_{nklm_{J}} /c_{n} (c_{n} = ∑_{k,l,m_{J}} c_{nklm_{J}}), so wurde in [BD] gezeigt, daß (X_{n}^{J}) unter sehr schwachen

Voraussetzungen für φ(t) asymptotisch normalverteilt ist mit Mittel μ_{n}^{J} = μ^{J}n + O(1) und Kovarianzmatrix Σ_{n}^{J} = σ^{J}n + O(1). Es wurden allerdings nur

μ^{J} = (\frac{1}{2}, \frac{1}{4}, (μ_{j})_{j∈J})  mit μ_{j} = \frac{\frac{1}{j}[t^{j−1}]φ (\frac{u_{0}}{2} + t)^{j}}{2^{j+1}φ′(u_{0})^{j−1}φ(u_{0})}  (2)

(wobei u_{0} die positive Lösung von tφ′(t) = φ(t) bedeutet) und Σ^{J} für J = ∅ angegeben. Für J = {i, j} ergibt sich

Σ^{J} = ( \begin{matrix}\frac{1}{4} & \frac{1}{4} & σ_{yi} & σ_{yj} \\ \frac{1}{4} & \frac{5+α}{16} & σ_{zi} & σ_{zj} \\ σ_{yi} & σ_{zi} & σ_{ii} & σ_{ij} \\ σ_{yj} & σ_{zj} & σ_{ij} & σ_{jj} \end{matrix} ) mit α = \frac{φ(u_{0})φ′′(u_{0})}{φ′(u_{0})^{2}},

Typeset by AMS-TEX

\begin{aligned}σ_{yi} & = \frac{(i − 1)μ_{i} − i\overline{μ}_{i}}{2}  mit \overline{μ}_{i} = \frac{\frac{1}{i}[t^{i}]φ (\frac{u_{0}}{2} + t)^{i}}{2^{i+2}φ′(u_{0})^{i}} , \\ σ_{zi} & = \frac{(3i − 5 − α)μ_{i}}{4} − \frac{i\overline{μ}_{i}}{2} , \\ σ_{ii} & = μ_{i} + (1 + α − 2i)μ_{i}^{2} − \frac{1}{α} (μ_{i} − i\overline{μ}_{i})^{2} , \\ σ_{ij} & = (1 + α − i − j)μ_{i}μ_{j} − \frac{1}{α} (μ_{i} − i\overline{μ}_{i}) (μ_{j} − j\overline{μ}_{j}) . \end{aligned}  (3)

Für größeres J läßt sich das Resultat daraus unmittelbar ablesen. Außerdem erhält man jetzt wie in [BD] beschrieben multivariate asymptotische Entwicklungen für c_{nklm_{J}}, c_{nk·m_{J}}, usw.

Da im allgemeinen die Eintragungen für Σ^{J} umständlich zu berechnen sind, kann man wie für μ_{j} in [BD] asymptotische Entwicklungen angeben. Sie berechnen sich aus den asymptotischen Entwicklungen von μ_{j} und \overline{μ}_{j}:

\begin{aligned}μ_{j} & = \frac{1}{2u_{0}} [\frac{φ (\frac{u_{0}}{2} + v_{0})}{2πφ′′ (\frac{u_{0}}{2} + v_{0})}]^{\frac{1}{2}} [\frac{φ′ (\frac{u_{0}}{2} + v_{0})}{2φ′(u_{0})}]^{j} j^{−3/2} (1 + O (\frac{1}{j})) , \\ \overline{μ}_{j} & = \frac{1}{4v_{0}} [\frac{φ (\frac{u_{0}}{2} + v_{0})}{2πφ′′ (\frac{u_{0}}{2} + v_{0})}]^{\frac{1}{2}} [\frac{φ′ (\frac{u_{0}}{2} + v_{0})}{2φ′(u_{0})}]^{j} j^{−3/2} (1 + O (\frac{1}{j})) , \end{aligned}  (4)

wobei v_{0} die kleinste positive Lösung von tφ′(u_{0}/2 + t) = φ(u_{0}/2 + t) bezeichnet.

Für φ(t) = 1/(1 − t) (ebene Wurzelbäume), für φ(t) = (1 + t)^{N} (N-äre Wurzelbäume mit n inneren Knoten) und für φ(t) = e^{t} (markierte Wurzelbäume) können diese Eintragungen auch exakt angegeben werden. Man benötigt zunächst α, μ_{j} und \overline{μ}_{j}. (Man beachte, daß der erste und der dritte Fall als “Spezialfälle” des zweiten angesehen werden können, wenn man in den Formeln von φ(t) = (1 + t)^{N} die Fälle N = −1 und N → ∞ betrachtet.)

\begin{aligned}φ(t) & = \frac{1}{1 − t} & α & = 2 & μ_{j} & = \frac{1}{j}\binom{2j − 2}{j − 1}\frac{2^{j−2}}{3^{2j−1}} & \overline{μ}_{j} & = μ_{j} \frac{2j − 1}{3j} \\ φ(t) & = (1 + t)^{N} & α & = 1 − \frac{1}{N} & μ_{j} & = \frac{1}{j}\binom{Nj}{j − 1}\frac{(2N − 1)^{(N−1)j+1}}{4(2N)^{Nj}} & \overline{μ}_{j} & = μ_{j} \frac{(N − 1)j + 1}{(2N − 1)j} \\ φ(t) & = e^{t} & α & = 1 & μ_{j} & = \frac{j^{j−1}}{j!2^{j+1}e^{j/2}} & \overline{μ}_{j} & = \frac{μ_{j}}{2} \end{aligned}

(5)

Für φ(t) = (1 + t)^{N} ergibt sich unmittelbar

\begin{aligned}σ_{yi} & = μ_{i} \frac{N(i − 2)}{2(2N − 1)}, \\ σ_{zi} & = μ_{i} \frac{iN(4N − 1) − (12N^{2} − 6N + 1)}{4N(2N − 1)}, \\ σ_{ii} & = μ_{i} − μ_{i}^{2} \frac{i^{2}N^{2}(N − 1) + 2iN(2N^{2} − 2N + 1) − (4N^{3} − 8N^{2} + 6N − 1)}{N(2N − 1)^{2}}, \\ σ_{ij} & = −μ_{i}μ_{j} \frac{ijN^{2}(N − 1) + (i + j)N(2N^{2} − 2N + 1) − (4N^{3} − 8N^{2} + 6N − 1)}{N(2N − 1)^{2}}. \end{aligned} (6)

Daraus gewinnt man für φ(t) = 1/(1 − t) (1. Spalte) und φ(t) = e^{t} (2. Spalte):

\begin{aligned}σ_{yi} & = μ_{i} \frac{i − 2}{6}, & σ_{yi} & = μ_{i} \frac{i − 2}{4}, \\ σ_{zi} & = μ_{i} \frac{5i − 19}{12}, & σ_{zi} & = μ_{i} \frac{i − 3}{2}, \\ σ_{ii} & = μ_{i} − μ_{i}^{2} \frac{2i^{2} + 10i − 19}{9}, & σ_{ii} & = μ_{i} − μ_{i}^{2} \frac{i^{2} + 4i − 4}{4} \\ σ_{ij} & = −μ_{i}μ_{j} \frac{2ij + 5i + 5j − 19}{9}, & σ_{ij} & = −μ_{i}μ_{j} \frac{ij + 2i + 2j − 4}{4}. \end{aligned}  (7)

In diesen drei Fällen ist es übrigens auch möglich, explizite Formeln zu gewinnen. In [BD] wurden bereits die Gesamtanzahlen c_{nklm} angegeben. Für φ(t) = 1/(1 − t) erhält man

c_{nklm} = \frac{1}{k − l} \binom{2n − 2}{n − k − 1}\binom{n − l − 2}{k − l − 1}\binom{k − l}{m}P^{m},  (8)

wobei \binom{k−l}{m} den Multinomialkoeffizienten (k −l)!/ ∏_{j≥1} m_{j}!, P^{m} = ∏_{j≥1} P_{j}^{m_{j}} und P_{j} = \frac{1}{j} \binom{2j−2}{j−1}

die Catalanzahlen bezeichen. Für φ(t) = (1 + t)^{N} ist

c_{nklm} = \frac{1}{k − l} \binom{Nn − k}{n − k − 1}\binom{N(n − k)}{k − l − 1}\binom{k − l}{m}P^{m}  mit P_{j} = \frac{1}{j}\binom{Nj}{j − 1} (9)

und für φ(t) = e^{t}

c_{nklm} = \frac{1}{k − l} \frac{n^{n−k}(n − k)^{k−l−1}}{(n − k)!(k − l − 1)!}\binom{k − l}{m}P^{m}  mit P_{j} = \frac{j^{j−1}}{j!} .  (10)

Etwas aufwendiger ist es aber, für vorgegebenes J, c_{nklm_{J}} explizit anzugeben. Es müssen dafür die Methoden von [BD] verfeinert werden. Die auftretenden Ausdrücke enthalten in den meisten Fällen alternierende Summen, die nicht mehr zu einer geschlossenen Form zusammengefaßt werden können. Zur Illustration sollen die Resultate für J = {1} angegeben werden. In der Reihenfolge φ(t) = 1/(1 − t), φ(t) = (1 + t)^{N}, φ(t) = e^{t} erhält man

\begin{aligned}c_{nklm_{1}} & = \frac{2}{n}\binom{2n − 2}{n − k − 1}\frac{(n − l − 2)!(2l − 1)!(k(3n − 2) − n(2l + 1 − n))}{(n − k)!m_{1}!(k − l − m_{1} − 1)!(k − m_{1})!(2l − k + m_{1})!}, \\ c_{nklm_{1}} & = \frac{N}{k − l} \binom{Nn − k}{n − k − 1}\binom{N(n − k) − 1}{k − l − 1}· \\ & · ∑_{j=m_{1}}^{k−l}(−1)^{j−m_{1}} \frac{k − j − l}{k − l} \binom{k − l}{j}\binom{j}{m_{1}}\binom{N(k − j)}{l}, \\ c_{nklm_{1}} & = \frac{n^{n−k−1}(n − k)^{k−l−1}}{(n − k)!l!m_{1}!} ∑_{j=m_{1}}^{k−l−1}(−1)^{j−m_{1}} \frac{(k − j)^{(l−1)}(n − j)}{(j − m_{1})!(k − l − j − 1)!}. \end{aligned}  (11)

Auch bei diesen expliziten Resultaten können der erste und der dritte Fall für N = −1 und N → ∞ aus dem zweiten gewonnen werden.

Literatur

[BD] Baron, G., and M. Drmota, Distribution Properties of Induced Subgraphs of Trees, Ars Combinatoria 35 (1993), 193–213..

[MM] Meir, A., and J.W. Moon, On Maximal Independent Sets of Nodes in Trees, J. Graph Th. 12 (1988), 265–283.

Abteilung für Diskrete Mathematik, Technische Universität Wien, Wiedner Hauptstraße 8–10/118, A-1040 Wien, Österreich.