Existence of dense graph with relatively small codegree?

Question

Let $n$ be some parameter tending to infinity. I am wondering does there exists some kind of graphs $G$ on vertex-set $[n]$ with maximum degree less than $D$, so that

• $D\ge n/w_1(n)$,
• $e_G$, the number of edges of $G$ satisfies $e_G\ge\frac{nD}{2w_2(n)}$,
• maximum codegree $\max_{u,v\in V_G:u\neq v}|\{w:wv,wu\in E_G\}|\le D/w_3(n)$,

where $w_1,w_2,w_3\to\infty$ as $n\to \infty$, and $w_1,w_2\ll w_3$ ? For $\ll$, I mean it will be good if $w_1,w_2$ are less than some power of $\log w_3$ or some small power of $w_3$. Definitely we assume $w_3$ less than some small power of $n$.

Answer 1

No. At least for $w_1,w_2$ polylog$(n)$ and $w_3 \geq n^{\epsilon}$ for some $\epsilon \in \Omega(1)$, there is no such graph.

Suppose otherwise. Pick the set $B$ of $b = 2w_1w_2\log n$ vertices of the highest degree in $G$. The sums of the degrees of these vertices has to be at least $\frac{bD}{2w_2} \geq n \log n$.

However, let for each vertex $u \in G$, let $N_B(u)$ be the number of neighbors that $u$ has in $B$. Then $\sum_{u \in V(G)} N_B(u)$ is the sums of the degrees of vertices in $B$ which is $\frac{bD}{2w_2}$ $\geq n \log n$.

Furthermore, $N_B(u)$ is upper-bounded by $b$. So there are at least $(\frac{bD}{2w_2} - n)/b$ vertices $u$ adjacent to 2 or more vertices in $B$. As $\frac{bD}{2w_2}$ is at least $n \log n$, it follows that $\frac{bD}{2w_2}-n$ is at least $\frac{bD}{4w_2}$, and so (*) there are at at least $\frac{D}{4w_2}$ vertices $u$ adjacent to 2 or more vertices in $B$

However, the bound on the max codegree implies that (**) the number of vertices $u$ adjacent to 2 or more vertices in $B$ is no more than $\frac{b^2D}{w_3}$ which is $O(\frac{b^2D}{n^{\epsilon}})$ if $w_3 = n^{\epsilon}$.

However, note that $b$ is only polylog if $w_1$ and $w_2$ are polylog, so at most only one of (*) and (**) may hold if both $w_1$ and $w_2$ are polylog and $w_3$ is $\Omega(n^{\epsilon})$ for some $\epsilon \in \Omega(1)$.