Frage zu Turáns Extremalsatz
Ich mache die Übung 5.10 auf Seite 30 von Wilsons Einführung in die Graphentheorie . Es sagt:
Lassen $G$ sei ein einfaches Diagramm auf $2k$Eckpunkte ohne Dreiecke. Zeigen Sie, durch Induktion auf$k$, Das $G$ hat höchstens $k^2$ Kanten.
Die Adjazenzmatrix von $G$ muss eine quadratische Dimensionsmatrix sein $2k$und wenn man das abbricht $i$-th und $j$-th Zeilen und Spalten, das Ergebnis ist die Adjazenzmatrix des Graphen $G$ mit den beiden Scheitelpunkten $i$ und $j$gelöscht. Ich erinnere mich, dass die Spur des Quadrats einer Adjazenzmatrix doppelt so groß ist wie die Gesamtzahl der Kanten im Diagramm, und dass die Spur des Würfels einer Adjazenzmatrix die Gesamtzahl der Dreiecke multipliziert mit ist$6$. Dies bedeutet, dass benannt$A$ die Adjazenzmatrix von $G$, das $2k$ Elemente auf der Diagonale von $A^2$ sind so, dass die Summe von $2k-2$ von ihnen ist immer weniger als $(k-1)^2$durch die Induktivitätshypotese. Also im Allgemeinen, wenn wir haben$2k$ Zahlen mit dieser Eigenschaft kann die Summe aller Zahlen folgendermaßen begrenzt werden: $$(k-1)^2\frac {2k\choose {2k-2}}{{2k-1}\choose {2k-3}}.$$ Dies scheint mir richtig, da die Anzahl der verschiedenen $2k-2$-uples in einem Set mit $2k$ elements ist der Zähler des Bruchs, aber jedes Element gehört zu einer Anzahl von $2k-2$-uples gleich dem Nenner. Mit diesen Berechnungen erhalte ich, dass die Gesamtsumme der$2k$ Zahlen sind begrenzt durch $$\frac{k^3-k^2-k+1}{k}.$$ Dieser Wert ist jedoch streng kleiner als $k^2$, und dies kann nicht wahr sein, da die Obergrenze von Turàns Theorem leicht erreicht werden kann, zum Beispiel mit dem Radgraphen $W_6$. Was vermisse ich? Ich möchte insbesondere wissen, wo der Fehler in diesem Beweis liegt, ich bin nicht nur an einem Beweis des Satzes interessiert. Vielen Dank im Voraus für die Hilfe.
Antworten
Die Arbeit mit der Adjazenzmatrix ist selten so hilfreich, wie es zunächst scheint, und in diesem Fall verdeckt es Ihre Argumentation. Insbesondere, anstatt zu sagen, dass "die Spur von$A^2$ ist die doppelte Anzahl von Kanten ", können wir sagen" die Summe der Grad in einem Diagramm ist die doppelte Anzahl von Kanten "und erhalten ein äquivalentes Argument.
In einer konventionelleren Sprache sagen Sie das also
Das $2k$ Grad der Eckpunkte von $G$ sind so, dass die Summe von $2k-2$ von ihnen ist immer weniger als $(k-1)^2$durch die induktive Hypothese.
Dies scheint , wie es sollte funktionieren: Löschen von zwei Ecken Blätter einer$2k-2$-Vertex-Diagramm ohne Dreiecke. Und du hast Recht , dass , wenn es tat Arbeit können wir die Summe aller Grade gebunden: wenn wir alle zusammenzählen$\binom{2k}{2k-2}$ solche Summen, dann wird jeder Grad addiert $\binom{2k-1}{2k-3}$ Zeiten, die zu führen $\frac{\binom{2k}{2k-2}}{\binom{2k-1}{2k-3}} (k-1)^2 = k(k-1)$.
Aber wenn wir zwei Eckpunkte löschen $v$ und $w$, die Grad in der verbleibenden Grafik $G - v - w$ sind nicht die gleichen wie die Grade in der ursprünglichen Grafik $G$. Jeder Scheitelpunkt neben$v$ oder zu $w$ wird seinen Abschluss verlieren $1$ (und wenn ein Scheitelpunkt an beide angrenzt, sinkt sein Grad um $2$). Daraus können wir nicht schließen$G$ hat höchstens $k(k-1)$ Kanten.
Anders ausgedrückt, hier ist die Summe, mit der wir die induktive Hypothese verwenden können: $$ \sum_{v \in V} \sum_{w \in V-v} \left(\sum_{u \in V-v-w} \deg_{G-v-w}(u)\right) = \sum_{v \in V} \sum_{w \in V-v} 2|E(G-v-w)| \le \binom {2k}2 \cdot 2(k-1)^2 $$ Und hier ist die Summe wo $\deg_G(u)$ wird gezählt $\binom{2k-1}{2}$ mal: $$ \sum_{v \in V} \sum_{w \in V-v} \sum_{u \in V-v-w} \deg_G(u) = \binom{2k-1}{2}\sum_{u \in V} \deg_G(u) = \binom{2k-1}{2} (2|E(G)|). $$ Diese sind nicht gleich: in der ersten Summe, um die Anzahl der Kanten in zu erhalten $G-v-w$müssen wir den Grad von nehmen $u$ im $G-v-w$. In der zweiten Summe, um die Anzahl der Kanten in zu erhalten$G$ Am Ende müssen wir den Grad von nehmen $u$ im $G$. Das ist anders.
Das gleiche Problem tritt bei der Adjazenzmatrixberechnung auf (da die Adjazenzmatrixberechnung wirklich nur eine andere Möglichkeit ist, dasselbe Argument zu formulieren). Wenn Sie Zeilen und Spalten löschen$i$ und $j$ von $A$ um eine Matrix zu bekommen $B$, das $2k-2$ diagonale Einträge von $B^2$ wird nicht zustimmen $2k-2$ des $2k$ diagonale Einträge von $A^2$. Ein typischer diagonaler Eintrag von$A^2$ ist $$(A^2)_{kk} = \sum_{\ell=1}^{2k} A_{k\ell} A_{\ell k}$$ und wenn wir weitergehen $B^2$, die beiden Begriffe $A_{ki} A_{ik}$ und $A_{kj} A_{jk}$ verschwinden.
Aber es ist okay, wir können das beheben! Sie müssen nur ein bisschen mehr arbeiten. Wählen Sie die beiden Eckpunkte aus$v,w$zu löschen (oder, wenn Sie darauf bestehen, die zwei zu löschenden Zeilen und Spalten). Nach der induktiven Hypothese$G-v-w$ hat höchstens $(k-1)^2$Kanten. Wie viele Kanten von$G$sind keine Kanten von$G-v-w$? Es gibt$\deg(v) + \deg(w)$ wenn $v$ und $w$ sind nicht benachbart, oder $\deg(v) + \deg(w) - 1$ wenn sie sind (weil die Kante $vw$ wird zweimal gezählt von $\deg(v)+\deg(w)$).
Kannst du wählen $v$ und $w$ so, dass es höchstens gibt $k^2 - (k-1)^2$dieser fehlenden Kanten? Wenn ja, erhalten Sie einen Beweis für Mantels Theorem.