A graph has a pair $(m,f)$ if it has an induced subgraph on $m$ vertices and $f$ edges. We write $(n,e)\rightarrow (m,f)$ if any graph on $n$ vertices and $e$ edges has a pair $(m,f)$. Let $$S(n,m,f)=\{e: ~(n,e)\rightarrow (m,f)\} ~{\rm and}$$ $$\sigma(m,f) = \limsup_{n\rightarrow \infty}\frac{ |S(n,m,f)|}{\binom{n}{2}}.$$ These notions were first introduced and investigated by Erdős, Füredi, Rothschild, and Sós. They found five pairs $(m,f)$ with $\sigma(m,f)=1$ and showed that for all other pairs $\sigma(m,f)\leq 2/3$. We extend these results in two directions.
First, in a joint work with Weber, we show that not only $\sigma(m,f)$ can be zero, but also $S(n,m,f)$ could be empty for some pairs $(m,f)$ and any sufficiently large $n$. We call such pairs $(m,f)$ absolutely avoidable.
Second, we consider a natural analogue $\sigma_r(m,f)$ of $\sigma(m,f)$ in the setting of $r$-uniform hypergraphs. Weber showed that for any $r\geq 3$ and $m>r$, $\sigma_r(m,f)=0$ for most values of $f$. Surprisingly, it was not immediately clear whether there are nontrivial pairs $(m,f)$, $(f\neq 0$, $f\neq \binom{m}{r}$, $r\geq 3$), for which $\sigma_r(m,f)>0$. In a joint work with Balogh, Clemen, and Weber we show that $\sigma_3(6,10)>0$ and conjecture that in the $3$-uniform case $(6,10)$ is the only such pair.