2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

It is well-known, but I do not know where did it appear for the first time.

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Brendan McKay Jan 17 '16 at 18:15
  • $\begingroup$ In this 1964 paper of Erdos: renyi.hu/~p_erdos/1964-06.pdf , he attributes this result to a 1955 Hebrew paper of himself (ref [6]). $\endgroup$ – Brendan McKay Jan 17 '16 at 18:25
  • $\begingroup$ @BrendanMcKay What do you call ``obvious generalization''? $\endgroup$ – Fedor Petrov Jan 17 '16 at 18:29
  • $\begingroup$ 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. $\endgroup$ – Brendan McKay Jan 17 '16 at 18:32
  • $\begingroup$ I am assuming that given a set of $n$ vertices that that there are at most $n$ edges between them. $\endgroup$ – mssmath Jan 17 '16 at 18:33

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.