pith. sign in

arxiv: 1612.00206 · v1 · pith:XURB2DM3new · submitted 2016-12-01 · 🧮 math.CO

Local conditions for exponentially many subdivisions

classification 🧮 math.CO
keywords completeeveryexponentialgraphgraphslocalpowersubdivisions
0
0 comments X
read the original abstract

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 characterise those $F$ for which $s_t(F)$ is exponential in a power of $t$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.