Timeline for Extremal examples for a folklore lemma on subgraphs of large minimum degree
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 11, 2014 at 10:44 | answer | added | JDRS | timeline score: 4 | |
| Apr 11, 2014 at 5:45 | answer | added | David Eppstein | timeline score: 10 | |
| Apr 10, 2014 at 20:14 | answer | added | Shagnik | timeline score: 4 | |
| Apr 10, 2014 at 17:24 | answer | added | Peter Dukes | timeline score: 4 | |
| Apr 10, 2014 at 16:45 | comment | added | BPN | I mean asymptotically, of course. When I say $d$ fixed, I mean for large $d$ and infinitely many $n$ (number of vertices) for that $d$, i.e., $d \to \infty$ and for each $d$ in that sequence, an infinite family of graphs on a larger and larger number of vertices of average degree about $d$. Does that clarify what I'm asking for? | |
| Apr 10, 2014 at 16:12 | comment | added | Dr J | If $d$ is a positive integer, then a graph with average degree $d$ must actually contain a subgraph with minimum degree at least $\lfloor\frac{d}{2}\rfloor+1>\frac{d}{2}$, so when you say that the constant $\frac{1}{2}$ cannot be improved, you mean asymptotically as $d\to\infty$, right ? But then in the second part of your post you seem to consider $d$ as being fixed. Could you clarify ? | |
| Apr 10, 2014 at 15:33 | review | First posts | |||
| Apr 10, 2014 at 15:43 | |||||
| Apr 10, 2014 at 15:15 | history | asked | BPN | CC BY-SA 3.0 |