Talk:Goddyn's conjecture on thin spanning trees

Thin odd vertex pairing? -- Tamás Király (talk) 04:06, 2 June 2014 (UTC)

One can define [math]\epsilon[/math]-thinness of odd vertex pairings similarly. The existence of a thin spanning tree implies the existence of a thin odd vertex pairing, so maybe the latter is easier to prove.

Re: Thin odd vertex pairing? -- Tamás Király (talk) 21:11, 8 September 2015 (UTC)

To add some motivation to this question, we show that the existence of a thin odd vertex pairing would imply the [math](2+\epsilon)[/math]-flow conjecture (Open Problem Garden). If we add an [math]\epsilon[/math]-thin odd vertex paring to a graph G=(V,E), and take an Eulerian orientation of the resulting Eulerian graph, then the orientation restricted to G satisfies

[math]\frac{1-\epsilon}{1+\epsilon} \leq \frac{\varrho(X)}{\delta(X} \leq \frac{1+\epsilon}{1-\epsilon}[/math]

for every [math]X\subseteq V[/math]. By Hoffman's circulation theorem, this digraph has a circulation satisfying lower bound [math]1-\epsilon[/math] and upper bound [math]1+\epsilon[/math] on every arc.