Quantitative density theorem for ell divisive graphs

Choose divisibility witnesses $c,d$, put $z=\mathrm{\ell }(c{)}^{-1\mathrm{/}2}$, $b=2-{\log }_2(1-z)>2$, and $C_0=20bd$. First take $0<ϵ<c$, and define ${\delta }_0$ by the displayed formula with $C_0$. If ${\delta }_0\mathrm{\mid }G\mathrm{\mid }\le 1$, any singleton $S$ has the required size and zero edges in both graphs. Otherwise the parameter construction [F1] supplies $x,p,\eta ,t$ and ${\delta }_0<x^d{\eta }^t<{\eta }^t$; all hypotheses of [F2] hold with $\delta ={\delta }_0$.

For each integer $0\le r\le t$, the recurrence implies ${\beta }_0(ϵ,ϵ)\ge {\eta }^r{\min }_{0\le i\le r}{\beta }_r(p^iϵ,p^{r-i}ϵ)$. At $r=0$ this is equality. To pass from $r<t$ to $r+1$, apply [F2] with $s=r+1$ to every pair $(p^iϵ,p^{r-i}ϵ)$; both coordinates are at least $ϵ$ because $p>1$. The two children have exponent pairs $(i+1,r-i)$ and $(i,r+1-i)$, whose union over $i$ is exactly all pairs summing to $r+1$. Taking their finite minimum proves the induction step.

At $r=t$, the product of the two arguments in every terminal pair is $p^t{ϵ}^2\ge 1$ by the least-natural property in [F1]. At least one argument is therefore at least 1. Each terminal profile value equals 1 by [F3]. Hence ${\rho }_G(ϵ,ϵ)={\beta }_0(ϵ,ϵ)\ge {\eta }^t>{\delta }_0$. The attained maximum defining ${\rho }_G$ supplies a nonempty set of at least ${\delta }_0\mathrm{\mid }G\mathrm{\mid }$ vertices with one of the required edge bounds. Together with the singleton case, this proves the theorem on $(0,c)$ with constant $C_0$.

For the full interval set $a={\log }_2(1\mathrm{/}c)>1$ and $C_{H,\mathrm{\ell }}=a^2{C}_0$. Given $0<ϵ<1\mathrm{/}2$, put ${ϵ}^{\mathrm{\prime }}={ϵ}^a<c$ and let ${\delta }^{\mathrm{\prime }}$ be the small-interval fraction at ${ϵ}^{\mathrm{\prime }}$ with constant $C_0$. Since ${ϵ}^{\mathrm{\prime }}\le ϵ$ and $\mathrm{\ell }$ is nonincreasing, ${\log }_2\mathrm{\ell }({ϵ}^{\mathrm{\prime }})\ge {\log }_2\mathrm{\ell }(ϵ)>0$. Thus ${\log }_2(1\mathrm{/}{\delta }^{\mathrm{\prime }})=C_0{a}^2{\log }_2(1\mathrm{/}ϵ{)}^2\mathrm{/}{\log }_2\mathrm{\ell }({ϵ}^{\mathrm{\prime }})\le {\log }_2(1\mathrm{/}\delta )$, so ${\delta }^{\mathrm{\prime }}\ge \delta$.

The original hypothesis implies ${\mathrm{ind}}_H(G)\le ({\delta }^{\mathrm{\prime }}\mathrm{\mid }G\mathrm{\mid }{)}^{\mathrm{\mid }H\mathrm{\mid }}$. Apply the small-interval result to ${ϵ}^{\mathrm{\prime }}$: its set has size at least ${\delta }^{\mathrm{\prime }}\mathrm{\mid }G\mathrm{\mid }\ge \delta \mathrm{\mid }G\mathrm{\mid }$, and its edge bound with ${ϵ}^{\mathrm{\prime }}$ implies that with $ϵ$. This establishes the claimed constant on the entire open interval.