Exact Results for Some Extremal Problems on Expansions I

The expansion of a graph F, denoted by F3, 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 T3 for certain class 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 F3 when F is a graph obtained from some tree T∈T by adding a new edge, thereby extending anti-Ramsey results on P2t3 by Gu–Li–Shi and C2t3 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 Ck3 or T3 for T∈T, thus answering a question of Lv et al. on generalized Turán problems.