Timeline for Connected sets with large boundary in a multigraph
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2022 at 1:32 | history | edited | Harry Richman | CC BY-SA 4.0 |
fix latex typo
|
| Nov 20, 2021 at 9:40 | comment | added | H A Helfgott | We could then continue the discussion in mathoverflow.net/questions/408974/… | |
| Nov 20, 2021 at 8:20 | comment | added | H A Helfgott | I think that should be an equivalence, at least if we drop the condition that the out-degree of every vertex equal its in-degree. | |
| Nov 20, 2021 at 8:13 | comment | added | H A Helfgott | The question reduces to the following one: given a subset $V'\subset V$ of $m$ vertices of degree $\geq 3$, can we show that there is a set $S$ such that $G|_S$ is connected and $\partial S$ has $\geq \delta m$ elements ($\delta>0$ fixed) in $V'$? Proof of reduction: Let $V'$ be the set of vertices whose in-degree is at least half the average. Let $S$ be as just stated. Then define your new set $S$ to be that $S$, plus half the vertices not in $S$, taken randomly. (This seems to give $\delta = 1/32$; tweak to get a larger $\delta$.) | |
| Nov 19, 2021 at 23:16 | history | edited | H A Helfgott | CC BY-SA 4.0 |
added 89 characters in body
|
| Nov 19, 2021 at 23:15 | comment | added | H A Helfgott | @Fedor_Petrov - ah, I should have made it clear - if $(v,w)$ is an arrow (edge of $G'$), then $\{v,w\}$ is an edge of $G$. | |
| Nov 19, 2021 at 23:13 | comment | added | Fedor Petrov | Is there any relation between two graphs? | |
| Nov 19, 2021 at 18:05 | history | asked | H A Helfgott | CC BY-SA 4.0 |