Timeline for Maximal number of directed edges in suitable simple graphs on $n$ vertices without directed triangles.
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 12, 2011 at 20:11 | answer | added | Sergey Norin | timeline score: 8 | |
| Apr 12, 2011 at 19:12 | history | edited | Sergey Norin |
edited tags
|
|
| Mar 28, 2011 at 12:48 | answer | added | Gordon Royle | timeline score: 2 | |
| Mar 24, 2011 at 13:13 | comment | added | JBL | gordon-royle, this is ruled out for $k \geq 2$ by the condition that there be no 2-cycles. | |
| Mar 24, 2011 at 13:03 | comment | added | Gordon Royle | Do you insist that if (u,v) is a directed edge, then (v,u) is not present? | |
| Mar 24, 2011 at 11:22 | comment | added | Roland Bacher | The Caccetta-Haggkvist conjecture is probably the right setting for this kind of problems. | |
| Mar 24, 2011 at 10:33 | comment | added | Nathann Cohen | Your question makes me think of the Caccetta-Haggkvist conjecture though, even if it does not contain in its definition any connectivity requirement. math.uiuc.edu/~west/openp/cacchagg.html | |
| Mar 24, 2011 at 10:33 | comment | added | Nathann Cohen | Without the connectivity constraint I would have said "orient transitively the edges of a complete graph" to have $\binom n 2$ edges and no directed cycle at all. To respect the connectivity constraint you can always add a direct path of length k+1 from the element of maximum indegree to the element of minimum indegree. Then you have for each $k$ a "family of digraphs with roughly $\binom n 2$ edges and no circuit of size $\leq k$." | |
| Mar 24, 2011 at 9:48 | history | asked | Roland Bacher | CC BY-SA 2.5 |