# Flow

A flow in an oriented graph $G$ with values in an Abelian group $A$ is a map $F$ from the edge set $E(G)$ to $A$ satisfying the Kirchhoff law that for each vertex $v$ $$\sum_{e\rightarrow v} F(e) = \sum_{e\leftarrow v} F(e) \ ,$$ that is, the flow into $v$ is equal to the flow out of $v$. A non-zero flow is one with the condition $F(e) \ne 0$ for all $e$.

The number $f_G(n)$ of non-zero flows on a graph $G$ with values in a finite group $A$ depends only on the order $n$ of $A$ and not its group structure, and a polynomial function of $n$, called the flow polynomial. This number does no depend on the orientation of the graph, so we may speak of the flow polynomial of an unoriented graph.

The flow polynomial is a contraction–deletion invariant: if $G/ e$ and $G\setminus e$ denote the contraction and deletion of $e$ respectively, then $$f_{G/ e}(n) = f_G(n) + f_{G\setminus e}(n) \ .$$

Tutte's five-flow conjecture states that if $G$ is a bridgeless graph, then it has a non-zero $n$-flow for $n=6$. It is known that this holds for $n=6$.

This establishes the remarkable relation between the flow polynomial $f_G$ and the chromatic polynomial $p_G$: $$f_G(n) = (-1)^{|V(G)|} p_G(-n).$$

# Ranked poset

A partially ordered set $(X,{\le})$ with a rank function $r : X \rightarrow \mathbf{N}$ such that $r(m) = 0$ for some minimal element $m \in X$, and $r(q) = r(p)+1$ when $q$ covers $p$: that is, $p. < q$ and there is no $x$ with $p < x < q$.

A graded poset is one in which every minimal element has rank $0$ and every maximal element has the same rank.

How to Cite This Entry:
Richard Pinch/sandbox-15. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-15&oldid=51733