The expansion of a graph F, denoted by \(F^3\) , is the 3-graph obtained from F by adding a new vertex to each edge such that different edges receive different vertices. We establish a stability version of a theorem by Kostochka–Mubayi–Verstraëte (Kostochka et al in J Combin Theory Ser B 122:457–478, 2017) and demonstrate two applications of it by establishing tight upper bounds for large \(n:\) The maximum number of edges in an n-vertex 3-graph that does not contain \(T^3\) for certain class \({\mathcal {T}}\) of trees, thereby (partially) sharpening the asymptotic result of Kostochka–Mubayi–Verstraëte.
The minimum number of colors needed to color the complete n-vertex 3-graph to ensure the existence of a rainbow copy of \(F^3\) when F is a graph obtained from some tree \(T\in {\mathcal {T}}\) by adding a new edge, thereby extending anti-Ramsey results on \(P_{2t}^3\) by Gu–Li–Shi and \(C_{2t}^3\) by Tang–Li–Yan.
We introduce a framework that utilizes tools from Extremal Set Theory for solving certain generalized Turán problems. More specifically, we establish a parallel of the stability theorem above in generalized Turán problems. Using this stability theorem, we determine, for large n, the maximum number of triangles in an n-vertex graph that does not contain the shadow of \(C_{k}^3\) or \(T^3\) for \(T\in {\mathcal {T}}\) , thus answering a question of Lv et al. on generalized Turán problems.
