Many flows in the group connectivity setting

Abstract: Two well-known results in the world of nowhere-zero flows are Jaeger's 4-flow theorem asserting that every 4-edge-connected graph has a nowhere-zero

m a t h b b Z_{2} i m e s m a t h b b Z_{2}

-flow and Seymour's 6-flow theorem asserting that every 2-edge-connected graph has a nowhere-zero

m a t h b b Z_{6}

-flow. Dvov{r}'ak and the last two authors of this paper extended these results by proving the existence of exponentially many nowhere-zero flows under the same assumptions. We revisit this setting and provide extensions and simpler proofs of these results. The concept of a nowhere-zero flow was extended in a significant paper of Jaeger, Linial, Payan, and Tarsi to a choosability-type setting. For a fixed abelian group

G a m m a

, an oriented graph

G = (V, E)

is called

G a m m a

-connected if for every function

f : E i g h t a r r o w G a m m a

there is a flow

p h i : E i g h t a r r o w G a m m a

with

p h i (e) e q f (e)

for every

e i n E

(note that taking

f = 0

forces

p h i

to be nowhere-zero). Jaeger et al. proved that every oriented 3-edge-connected graph is

G a m m a

-connected whenever

| G a m m a | g e 6

. We prove that there are exponentially many solutions whenever

| G a m m a | g e 8

. For the group

m a t h b b Z_{6}

we prove that for every oriented 3-edge-connected

G = (V, E)

with

e l l = | E | - | V | g e 11

and every

f : E i g h t a r r o w m a t h b b Z_{6}

, there are at least

2^{s q r t e l l / l o g e l l}

flows

p h i

with

p h i (e) e q f (e)

for every

e i n E

.

This page was built for publication: Many flows in the group connectivity setting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6341058)