Local Conditions for Exponentially Many Subdivisions

© 2016 Cambridge University Press. Given a graph F, let s t (F) be the number of subdivisions of F, each with a different vertex set, which one can guarantee in a graph G in which every edge lies in at least t copies of F. In 1990, Tuza asked for which graphs F and large t, one has that s t (F) is exponential in a power of t. We show that, somewhat surprisingly, the only such F are complete graphs, and for every F which is not complete, s t (F) is polynomial in t. Further, for a natural strengthening of the local condition above, we also characterize those F for which s t (F) is exponential in a power of t.