Timeline for Minimum Edge Density given a particular condition
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 17, 2016 at 22:14 | comment | added | Fedor Petrov | @LiorSilberman exactly, and a closely related theory by Lovasz and his school. | |
| Jan 17, 2016 at 22:03 | comment | added | Lior Silberman | This seems like the kind of problem Razborov's theory of flag algebras was designed to solve. | |
| Jan 17, 2016 at 19:14 | comment | added | Fedor Petrov | It is up to constant factor the same problem as 'maximal number of edges without cycle of length 4', which is well known | |
| Jan 17, 2016 at 18:56 | comment | added | mssmath | I just realized my error. How did you get a bound of $n^\frac{3}{2}$? | |
| Jan 17, 2016 at 18:54 | comment | added | Fedor Petrov | @mssmath it is wrong already for $n=4$. Correct answer is of order $n^{3/2}$. | |
| Jan 17, 2016 at 18:49 | comment | added | mssmath | I would like to note that if say there are at most 3 edges among a set of 4 vertices then $f(n)=n-1$ follows using Fedor's methods. | |
| Jan 17, 2016 at 18:33 | comment | added | mssmath | I am assuming that given a set of $n$ vertices that that there are at most $n$ edges between them. | |
| Jan 17, 2016 at 18:32 | comment | added | Brendan McKay | 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. | |
| Jan 17, 2016 at 18:29 | comment | added | Fedor Petrov | @BrendanMcKay What do you call ``obvious generalization''? | |
| Jan 17, 2016 at 18:25 | comment | added | Brendan McKay | 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]). | |
| Jan 17, 2016 at 18:23 | vote | accept | mssmath | ||
| Jan 17, 2016 at 18:15 | comment | added | Brendan McKay | 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? | |
| Jan 17, 2016 at 18:02 | history | answered | Fedor Petrov | CC BY-SA 3.0 |