# Extremal related question regarding Intersection of neighbourhood of vertices

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?

• What do you mean by "neighborhood"? – Yuval Filmus Dec 25 '17 at 16:42
• edited the question to clarify the meaning – Vk1 Dec 25 '17 at 16:44
• 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$? – Yuval Filmus Dec 25 '17 at 16:44
• Hope the clarification is fine now – Vk1 Dec 25 '17 at 16:48

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$.
• Very helpful, but I have a doubt. Does $k$ being constant have the same meaning as it being independent of $n$? – Vk1 Dec 28 '17 at 2:36
• 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$. – Yuval Filmus Dec 28 '17 at 6:33
• I have no idea what "$k$ is independent of $n$" means. Ask the setter of the question. – Yuval Filmus Dec 28 '17 at 6:34
• By $k$ being independent of $n$, I mean that $k$ is not $f(n)$, say $\sqrt{n}$ etc... Thanks for the clarifications – Vk1 Dec 28 '17 at 17:02