Timeline for Maximum number of edges in bipartite graph without cycles of length 4
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2016 at 21:03 | vote | accept | Ilya | ||
| Oct 12, 2016 at 17:19 | history | edited | Ilya | CC BY-SA 3.0 |
added 46 characters in body
|
| Oct 12, 2016 at 11:37 | comment | added | Oliver Krüger | ... "for large enough n" it should say for the general upper bound of ex(n,n,C_4) in my previous comment. | |
| Oct 12, 2016 at 11:28 | comment | added | Oliver Krüger | Not really solved by Bollobás. It was solved by István Reiman in 1958 (who showed that n = 2(q^2 + q + 1) where q is the order of a projective plane (in particular for prime powers q) then ex(n,n,C_4) = (q^2 + q + 1)(q + 1), and therefore ex(n,n,C_4) <= (1/2) (n + n*sqrt(4n-3))). The proof is however availible in Bollobás book "Extremal Graph Theory" from 1978 (which has a 2004 reprint). | |
| Oct 12, 2016 at 11:09 | history | answered | Ilya | CC BY-SA 3.0 |