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$.


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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.