2
$\begingroup$

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?

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

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

$\endgroup$
  • $\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 '17 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$ – Yuval Filmus Dec 28 '17 at 6:33
  • $\begingroup$ I have no idea what "$k$ is independent of $n$" means. Ask the setter of the question. $\endgroup$ – Yuval Filmus Dec 28 '17 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 '17 at 17:02

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.