Der Preprint “A very short proof of Sidorenko’s inequality for counts of homomorphism between graphs” präsentiert einen prägnanten, elementaren Beweis für ein klassisches Extremitätsergebnis in der extremalen Graphentheorie. Das Theorem, das ursprünglich 1994 von Sidorenko bewiesen wurde, besagt, dass für jeden zusammenhängenden Graphen (G) mit (k+1) Knoten und jeden Zielgraphen (H) die Anzahl der Graphenhomomorphismen von (G) zu (H) durch die Anzahl der Homomorphismen vom Sterngraphen (S_k) mit (k) Kanten zu (H) nach oben begrenzt ist. In Symbolen, (#mathrm{hom}(G,H)le #mathrm{hom}(S_k,H)). Die Autoren reduzieren das Problem auf Bäume: Das Entfernen von Kanten aus (G) kann nur die Anzahl der Homomorphismen erhöhen, so dass es ausreicht, (k)-Eckenbäume mit dem Stern zu vergleichen. Sie führen die Schreibweise (T(k,ell)) für die Menge der (k)-Eckenbäume mit genau (ell) Blättern ein und stellen fest, dass (T(k,k)={S_k}). Der entscheidende Schritt besteht darin, zu zeigen, dass es für jeden Nicht-Sternbaum (Tin T(k,ell)) einen Baum (T’in T(k,ell+1)) mit einem weiteren Blatt gibt, der mindestens genauso viele Homomorphismen in jedes (H) zulässt. Dies wird erreicht, indem man zwei Blätter (b_1,b_2) des Skeletts von (T) auswählt, alle an sie angrenzenden Blätter entfernt, um einen kleineren Baum (T(b_1,b_2)) zu erhalten, und dann die Homomorphismen in zwei Stufen zählt: zuerst die Abbildung von (T(b_1,b_2)) und dann die Erweiterung auf die entfernten Blätter. Der Ausdruck für das Zählen umfasst die Grade der Bilder von (b_1) und (b_2) in (H) und eine Wahrscheinlichkeitsverteilung (p(u,v)), die die Wahrscheinlichkeit beschreibt, dass ein zufälliger Homomorphismus von (T(b_1,b_2)) (b_1) nach (u) und (b_2) nach (v) schickt. Durch Anwendung der Hölderschen Ungleichung auf die Randverteilungen (p_1) und (p_2) leiten die Autoren eine obere Schranke ab, die als die Homomorphismenzahl eines neuen Baums (T’) interpretiert werden kann, den man erhält, indem man (vec d_1+vec d_2) Blätter an einen der Scheitelpunkte anhängt. Die Iteration dieser Operation zum Hinzufügen von Blättern ergibt schließlich den Stern, wodurch die gewünschte Ungleichung entsteht. Das Argument führt auch zu einer etwas stärkeren Form des Sidorenko-Ergebnisses, die zu dem Korollar führt, dass jeder Baum mit (k)-Ecken höchstens so viele Homomorphismen hat wie der Baum, den man erhält, wenn man ein einzelnes Blatt an ein Blatt von (S_{k-1}) anhängt, was wiederum durch den Stern begrenzt ist.

Der Preprint ordnet seinen Beitrag zwischen drei bereits existierenden Beweisen ein. Der ursprüngliche Beweis von Sidorenko verwendet eine Korrespondenz zwischen Graphenungleichungen und Ordnungen von integralen Funktionen auf Maßräumen und beruft sich auf log-konvexe Kombinationen und Ungleichungen vom Hölder-Typ. Csikvári und Lin lieferten einen Beweis, der sich auf den Wiener Index und elementare kombinatorische Operationen stützt. Levin und Peres boten ein prägnantes probabilistisches Argument, das die Anzahl der Homomorphismen mit der stationären Verteilung eines einfachen zufälligen Spaziergangs auf dem Zielgraphen verbindet. Der neue Beweis zeichnet sich durch seine Einfachheit aus: Er erfordert nur elementares Zählen und die klassische Hölder-Ungleichung auf endlichen Wahrscheinlichkeitsräumen, wodurch die Extremität der Sterne transparent wird.

Die Arbeit ist ein Gemeinschaftswerk von Lukas Lüchtrath vom Weierstraß-Institut für Angewandte Analysis und Stochastik (WIAS) in Berlin und Christian Mönch von der Johannes Gutenberg-Universität Mainz. Das Manuskript wurde am 15. August 2024 eingereicht und ist als Preprint Nummer 3120 gekennzeichnet. Die Finanzierung des Projekts stammt aus zwei Quellen: Lüchtraths Forschung wird von der Leibniz-Gemeinschaft durch die Leibniz-Nachwuchsgruppe “Probabilistische Methoden für dynamische Kommunikationsnetze” (Förderkennzeichen J105/2020) unterstützt, während Mönchs Arbeit von der Deutschen Forschungsgemeinschaft (DFG) unter dem Förderkennzeichen 443916008 (SPP 2265) finanziert wird. Der Preprint wird vom WIAS herausgegeben, was die Rolle des Instituts bei der Koordinierung der Forschung und der Sicherstellung der Qualität des endgültigen Dokuments widerspiegelt.