Timeline for The least number of edges to add to a tree that would force a certain number of edge-disjoint cycles
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 9, 2019 at 23:35 | vote | accept | hbm | ||
| Feb 6, 2019 at 4:29 | comment | added | Mike | Thanks @hbm added | |
| Feb 6, 2019 at 4:28 | history | edited | Mike | CC BY-SA 4.0 |
added 2854 characters in body
|
| Feb 6, 2019 at 4:23 | history | edited | Mike | CC BY-SA 4.0 |
added 2854 characters in body
|
| Feb 6, 2019 at 0:59 | comment | added | hbm | thanks! For completeness, could you add this to the answer as a note. I will accept the answer. | |
| Feb 5, 2019 at 23:53 | comment | added | Mike | Does this answer your question @hbm ? | |
| Feb 5, 2019 at 21:43 | comment | added | Mike | So for $i > \log L+2$, there definitely are fewer than $2^{i-2}m_1$ vertices of distance $i$ from $v$. So there is indeed a cycle of length $2i+1 = O(\log L)$ or less | |
| Feb 5, 2019 at 21:41 | comment | added | Mike | And so on and so forth; for there to be no cycles of length 7 or less, the number $m_3$ of vertices of distance 3 of $v$ has to satisfy $m_3 \geq 2m_2 \geq 2^2m_1$, and for general $i$, for their to be no cycles of length $2i+1$ or less, the number $m_i$ of vertices that are of distance $i$ from $v$ has to satisfy $m_i \geq 2m_{i-1}$ $\ge 2^{i-2}m_1$. BUT there are only $L=2^{\log L}$ vertices in $G$. | |
| Feb 5, 2019 at 21:36 | comment | added | Mike | So for there to be no cycles of length 5 or less, the number $m_2$ of vertices within distance 2 of $v$ has to satisfy $m_2 \geq \min_u (d(u)-1) m_1 \ge 2m_1$, where $u$ is a vertex of distance 1 from $v$. | |
| Feb 5, 2019 at 21:35 | comment | added | Mike | Now, each of these vertices $u$ within distance 1 of $v$ has a multiset $N_u$ of $d(u)-1 \ge 2$ neighbours besides $v$ itself, and for there to be no cycles of length 5 or less, the $N_u$s cannot intersect each other--lest their be a cycle of length $\le 5$, $u$ cannot be in $N_u$ (lest their be a loop), and if $u'$ is another vertex of distance 1 from $v$ then $u'$ cannot be in $N_u$ either, lest their be a cycle of length 3. Furthermore every vertex in the multiset $N_u$ can only appear once lest there be parallel edges (cycle of length 2). | |
| Feb 5, 2019 at 21:25 | comment | added | Mike | Sure. Let $G$ be a multigraph where every vertex has degree 3. Take any vertex $v$. Let $l$ be the length of the smallest cycle in $G$ . Then within distance 1 there have to be $m_1 \geq 3$ vertices. .... | |
| Feb 5, 2019 at 21:01 | comment | added | hbm | could you please justify why the cycle are $O(log(L))$ | |
| Feb 4, 2019 at 18:40 | history | edited | Mike | CC BY-SA 4.0 |
added 41 characters in body
|
| Feb 4, 2019 at 2:25 | history | edited | Mike | CC BY-SA 4.0 |
added 9 characters in body
|
| Feb 4, 2019 at 2:18 | history | edited | Mike | CC BY-SA 4.0 |
added 2 characters in body
|
| Feb 4, 2019 at 2:12 | history | edited | Mike | CC BY-SA 4.0 |
added 16 characters in body
|
| Feb 4, 2019 at 2:05 | history | edited | Mike | CC BY-SA 4.0 |
added 103 characters in body
|
| Feb 4, 2019 at 1:52 | history | edited | Mike | CC BY-SA 4.0 |
added 1 character in body
|
| Feb 4, 2019 at 1:46 | history | edited | Mike | CC BY-SA 4.0 |
added 1 character in body
|
| Feb 4, 2019 at 1:45 | comment | added | Mike | math.stackexchange.com/questions/3073345/… | |
| Feb 4, 2019 at 1:39 | history | edited | Mike | CC BY-SA 4.0 |
added 230 characters in body
|
| Feb 4, 2019 at 1:34 | comment | added | Mike | This line of reasoning was adapted and modified from one of @Misha Lavrov's answers in MSE | |
| Feb 4, 2019 at 1:32 | history | answered | Mike | CC BY-SA 4.0 |