Timeline for Number of edges in linklessly embeddable graphs
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 27, 2014 at 0:04 | vote | accept | Salman Parsa | ||
| Oct 27, 2014 at 0:04 | |||||
| Sep 29, 2014 at 17:15 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 59 characters in body
|
| S Sep 29, 2014 at 15:04 | history | suggested | Salman Parsa | CC BY-SA 3.0 |
added a comment for the answer to first question
|
| Sep 29, 2014 at 14:40 | review | Suggested edits | |||
| S Sep 29, 2014 at 15:04 | |||||
| Sep 26, 2014 at 13:44 | comment | added | Tony Huynh | Here is a link to the Kostochka/Thomason result (note they proved the same result independently). math.uiuc.edu/~kostochk/docs/old/cca84.pdf | |
| Sep 26, 2014 at 13:41 | comment | added | Tony Huynh | Thanks for the information on the Sachs' paper. Wikipedia claims that the paper does prove the claim in question, so that might need to be corrected. Perhaps they just linked to the wrong reference though. I'll do some more digging when I have the chance. | |
| Sep 26, 2014 at 13:39 | comment | added | Tony Huynh | For the $Cn$ bound you do not really need the full strength of the Graph Minors Structure. Once you exclude a single graph as a minor, you automatically go down to linear density. This follows from a result of Kostochka and Thomason. That is, there is an absolute constant $C$ such that for all $t$ and all graphs $G$, if $G$ does not have a $K_t$-minor, then $G$ has at most $Ct\sqrt{\log t} |V(G)|$ edges. | |
| Sep 26, 2014 at 13:29 | comment | added | Salman Parsa | The Sachs' paper you referred to leaves the question as an open problem. It just says that there are some graphs linklessly embeddable with that many edges. | |
| Sep 26, 2014 at 13:16 | comment | added | Salman Parsa | Thanks Tony. Can you please give me a reference for the $Cn$ bound? Or sketch how a proof would work? | |
| Sep 25, 2014 at 19:44 | history | edited | Tony Huynh | CC BY-SA 3.0 |
deleted 19 characters in body
|
| Sep 25, 2014 at 19:27 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 200 characters in body
|
| Sep 25, 2014 at 18:11 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 1 character in body
|
| Sep 25, 2014 at 17:42 | history | answered | Tony Huynh | CC BY-SA 3.0 |