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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
11
  • $\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
    Commented Jan 17, 2016 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
    Commented Jan 17, 2016 at 18:25
  • $\begingroup$ @BrendanMcKay What do you call ``obvious generalization''? $\endgroup$
    – Fedor Petrov
    Commented Jan 17, 2016 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
    Commented Jan 17, 2016 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
    Commented Jan 17, 2016 at 18:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .