# Minimum Edge Density given a particular condition

Consider a graph with $n$ vertices such that if one takes any 4 vertices there are at most 4 edges among these 4 vertices (Notice that there are 6 "possible" edges among these 4 vertices). What is the maximum possible edge density for such a graph as a function of $n$ and what is the limit as $n$ goes to infinity?

Using a probabilistic argument one can show that as $n$ goes to infinity that the edge density can be at most $\frac{2}{3}+\epsilon$, yet finding such a construction seems extremely tricky.

The answer is $f(2k)=k^2$ for $n=2k$ and $f(2k+1)=k(k+1)$ for $n=2k+1$. Examples are bipartite graphs $K_{k,k}$ and $K_{k,k+1}$. The proof of upper estimate goes by induction. Base $n=4$ is clear. Assume that $n\geqslant 5$ and graph on $n-1$ vertices may have at most $f(n-1)$ edges. Assume that some graph $G$ on $n$ vertices has at least $f(n)+1$ edges. Remove some edges so that exactly $f(n)+1$ edges remain. Each vertex $v$ has degree at least $f(n)-f(n-1)+1$, else $G\setminus v$ has more than $f(n-1)$ edges. Thus total number of edges is not less than $n(f(n)-f(n-1)+1)/2>f(n)+1$ (check this for two cases). The contradiction.
• Interestingly these have density only $\frac12+o(1)$ as $n\to\infty$. Do you know if the limiting density is known for the obvious generalization? – Brendan McKay Jan 17 '16 at 18:15
• @BrendanMcKay What do you call obvious generalization''? – Fedor Petrov Jan 17 '16 at 18:29
• The Hebrew paper: renyi.hu/~p_erdos/1955-15.pdf (see your answer on the first page). The generalization would be to ask what the max density of an $n$-vertex graph can be if it has no $k$-vertex subgraph with more than $\ell$ edges. It is what Erdos calls $f$ and I guess the general solution is very difficult. – Brendan McKay Jan 17 '16 at 18:32
• I am assuming that given a set of $n$ vertices that that there are at most $n$ edges between them. – mssmath Jan 17 '16 at 18:33