What is the maximum number of edges that a simple directed graph on $n$ vertices can have, if the graph has the following restriction.

Size of Intersection of Neighbourhood of any pair of vertices is at most $k$?

Neighbourhood is defined as follows. If a vertex $v$ has directed edges towards exactly three vertices $a$, $b$ and $c$, then $\{a,b,c\}$ constitutes the neighbourhood of $v$.

My hunch is $O(kn)$ but I am not able to prove it? Its easy to create such a graph which has $O(kn)$ edges, and has maximum intersection of neighbourhood to be at most k.

Simply create an empty graph on $n$ vertices say $v_1,v_2\ldots v_n$. Then for each $v_i$ give their neighbourhood to be $v_{i+1}$ to $v_{i+k}$. This gives a graph $O(kn)$ edges.

Can you show that this is the best which can be done?

  • 1
    $\begingroup$ What do you mean by "neighborhood"? $\endgroup$ Dec 25, 2017 at 16:42
  • $\begingroup$ edited the question to clarify the meaning $\endgroup$
    – Vk1
    Dec 25, 2017 at 16:44
  • $\begingroup$ There is no "usual meaning" for neighborhood in a directed graph. It can mean several different things. Suppose $v$ has outgoing edges to the vertices in $A$, and incoming edges from the vertices in $B$. What is the neighborhood of $v$? $\endgroup$ Dec 25, 2017 at 16:44
  • $\begingroup$ Hope the clarification is fine now $\endgroup$
    – Vk1
    Dec 25, 2017 at 16:48

1 Answer 1


This problem has been solved in the undirected case by Füredi, New asymptotics for bipartite Turán numbers, who showed that for constant $k$, the optimal bound is $$ \frac{1}{2} \sqrt{k} n^{3/2} + O(n^{4/3}), $$ when counting undirected edges. When counting directed edges, you have to double the number. The lower bound also holds in the directed case — it is given by an explicit construction based on finite fields.

Following Füredi's footsteps, we can generalize the upper bound to the directed case. Denote by $P_2$ a path consisting of two directed edges pointing at the central cases. The number of copies of $P_2$ in your graph is at most $k \binom{n}{2}$, since for every choice of the outer vertices there are at most $k$ choices of the inner vertex. On the other hand, the number of copies of $P_2$ is also $\sum_v \binom{d_{in}(v)}{2}$, where $d_{in}$ is the in-degree of $v$, since for every $v$, we can choose any two vertices in its incoming neighborhood to create a copy of $P_2$. Convexity now shows that $\sum_v \binom{d_{in}(v)}{2}$ is minimized when all in-degrees are the same. If the graph contains $m$ edges, then the total in-degree is $m$, and so $$ k \binom{n}{2} \geq n \binom{m/n}{2}, $$ from which we can deduce $m < \sqrt{k} n^{3/2} + n/2$.

  • $\begingroup$ Very helpful, but I have a doubt. Does $k$ being constant have the same meaning as it being independent of $n$? $\endgroup$
    – Vk1
    Dec 28, 2017 at 2:36
  • $\begingroup$ The bounds I quote don't cover the entire range of parameters, since we think of $k$ as constant, but they're enough to refute your guess. If you look at the actual construction, you might be able to get something even for non-constant $k$. $\endgroup$ Dec 28, 2017 at 6:33
  • $\begingroup$ I have no idea what "$k$ is independent of $n$" means. Ask the setter of the question. $\endgroup$ Dec 28, 2017 at 6:34
  • $\begingroup$ By $k$ being independent of $n$, I mean that $k$ is not $f(n)$, say $\sqrt{n}$ etc... Thanks for the clarifications $\endgroup$
    – Vk1
    Dec 28, 2017 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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