1
$\begingroup$

This problem in graph theory was actually motivated by some problems in Theory of Fractals.

To formulate the problem I need to recall some definitions related to flow network.

A flow network is a weighted directed graph $\Gamma$ with two distinguished vertices $s$ and $t$ called the source and sink. More formally, a flow network is a 5-tuple $\Gamma=(V,E,w,s,t)$ consisting of the set $V$ of vertices, the set $E\subset \{(u,v)\in V\times V:u\ne v\}$ of oriented edges of a digraph, a capacity function $c:E\to[0,\infty)$ and two distinct vertices $s,t\in V$.

The inflow $in(v)$ (resp. outflow $out(v)$) at a vertex $v$ of a flow network is the sum of capacities of directed edges of the graph that end (resp. start) at the vertex $v$.

The defect $\delta(v)$ of a vertex $v\in V$ is defined as the difference $\delta(v)=in(v)-out(v)$ between the inflow and outflow at $v$. The defect $\delta(F)$ of a flow network $\Gamma$ is defined as $$\delta(\Gamma):=|1+\delta(s)|+|\delta(t)-1|+\sum_{v\in V\setminus\{s,t\}}|\delta(v)|.$$

For two flow networks $\Gamma_1=(V_1,E_1,c_1,s_1,t_1)$ and $\Gamma_2=(V_1,E_1,c_1,s_1,t_1)$ a flow network morphism $f:\Gamma_1\to\Gamma_2$ is a function $f:V_1\to V_2$ such that

$\bullet$ $s_1=f(s_2)$, $t_1=f(t_2)$;

$\bullet$ $E_2=\{(f(u),f(v)):(u,v)\in E_1,\;f(u)\ne f(v)\}$;

$\bullet$ the capacity $c_2(e)$ of an edge $e\in E_2$ equals the sum of capacities of all edges $(u,v)\in E_1$ with $e=(f(u),f(v))$.

Problem. Let $(\Gamma_n)_{n=0}^\infty$ be a sequence of flow networks $\Gamma_n=(V_n,E_n,c_n,s_n,t_n)$ and $(f_n:\Gamma_{n+1}\to \Gamma_n)_{n\in\omega}$ be a sequences of flow network morphisms such that for some constants $C>1$, $D\in\mathbb N$ and $N\in\mathbb N$

$\bullet$ $|E_n|\le N$ and $|f_n^{-1}(v)|\le D$ for any $n\in\omega$ and $v\in V_n$;

$\bullet$ for every $n$ any (non-directed) path connecting the sorce and sink in $\Gamma_n$ has more than $C^n$ edges (such path can exist only for $n$ with $C^n<N$).

Is it true that there exist positive constants $\varepsilon>0$ and $\lambda<1$ depending only on $C$ and $D$ (but not on $N$) such that $$\sum_n\delta(\Gamma_n)\cdot\lambda^n>\varepsilon?$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.