Triangle Abundance Forcing Large Clique Blow-Ups

Definitions and mathematical statement

Under the usual convention, let a graph mean a finite simple undirected graph. For such a graph $G$, let $\tau(G)$ be the number of unordered three-element subsets of $V(G)$ that span a triangle. Write $\log$ for the natural logarithm. For an integer $t\geq 1$, a $t$-blow-up of $K_3$ is the complete tripartite graph $K_{t,t,t}$. Containment here is interpreted as ordinary subgraph containment: there are pairwise disjoint sets $A,B,D\subseteq V(G)$, each of size $t$, with every edge between distinct sets present; edges within these sets are unrestricted. These conventions are not explicitly specified in the supplied record and require source confirmation.

The supplied clean and current statements ask whether \[ \begin{gathered} \forall C>0\ \exists\gamma=\gamma(C)>0\ \exists n_0=n_0(C)\in{\mathbb{N}},\quad n_0\geq 3,\\ \forall n\in{\mathbb{N}},\ n\geq n_0,\quad \forall G\text{ with }|V(G)|=n,\\ \tau(G)\geq \frac{n^{3/2}}{\exp(C\sqrt{\log n})} \quad\Longrightarrow\quad \exists t\in{\mathbb{N}}:\quad t\geq\gamma\sqrt{\log n} \ \text{ and }\ K_{t,t,t}\subseteq G. \end{gathered} \] Here $\subseteq$ denotes subgraph containment, without an induced-subgraph requirement.

There is an unresolved discrepancy in the supplied evidence: the field original_statement instead asks for \[ t\geq\gamma\log n,\qquad \gamma=\gamma(C), \] under the same triangle-count hypothesis. With the positive-constant and sufficiently-large-$n$ quantifiers made explicit as above, this is a stronger target than the square-root-logarithmic target. The original field does not itself explicitly state all of those quantifiers or the positivity of $\gamma$. The record labels the clean statement corrected_verified and reports that it was checked against the official report; that is supplied verification metadata, not independent verification in this draft. Both targets are retained here, and their discrepancy requires human source review.

Short English statement

The supplied corrected formulation asks whether, for every fixed $C>0$, sufficiently many triangles force a complete tripartite subgraph with each part of size at least $\gamma(C)\sqrt{\log n}$, where $\gamma(C)>0$. The recorded original formulation instead requires $\gamma(C)\log n$. The supplied status is open; the conflicting targets and implicit graph conventions remain subject to human review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30002474$, title "Triangle Abundance Forcing Large Clique Blow-Ups," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The recorded proposed year is 2014; no individual proposer is supplied.
• Supplied report citation: Combinatorics (2014), Oberwolfach Reports, pp. 5--90, DOI 10.4171/owr/2014/01. https://doi.org/10.4171/owr/2014/01. The supplied background describes these reports as records of mathematical workshops and their open-problem discussions.
• Supplied literature source: "Oberwolfach combinatorics report." https://ems.press/content/serial-article-files/46491.
• Supplied literature source: "Rödl--Schacht, complete partite subgraphs." https://www.math.uni-hamburg.de/en/personen/schacht/2012/blowup.pdf.
• Literature assessment checked on 2026-08-21, according to the supplied record. This is supplied dated curation, not independently verified. It labels the problem open and states that known triangle-count-to-blow-up theorems require substantially denser hypotheses, while the displayed threshold with a square-root-logarithmic blow-up conclusion remains unresolved. The background describes this assessment as literature triage derived from the supplied OWR curation and explicitly calls for independent verification of time-sensitive status and cited claims.
• The supplied statement-verification metadata claims that the clean statement was checked against the official report and preserves its hypotheses, notation, and open target. No source was independently visited or checked for this draft.