CanaDAM 2021
En ligne, 25 - 28 mai 2021

Flows and signed graphs

RAFAEL GONZÁLEZ D'LEÓN, Universidad Sergio Arboleda, Colombia
Column-convex {0,1}-matrices, consecutive coordinate polytopes and flow polytopes  [PDF]

We study normalized volumes of a family of polytopes associated with column-convex {0,1}-matrices. Such a family is a generalization of the family of consecutive coordinate polytopes, studied by Ayyer, Josuat-Vergès, and Ramassamy, which in turn generalizes a family of polytopes originally proposed by Stanley in EC1. We prove that a polytope associated with a column-convex {0,1}-matrix is integrally equivalent to a certain flow polytope. We use the recently developed machinery in the theory of volumes and lattice point enumeration of flow polytopes to find various expressions for the volume of these polytopes, providing new proofs and extending results of Ayyer, Josuat-Vergès, and Ramassamy. A consequence of our techniques is that the set of higher-dimensional Entringer numbers are log-concave in root directions.

Signed Alternating-runs Enumeration in Classical Weyl Groups  [PDF]

The alternating-runs polynomial enumerates alternating runs in the symmetric group $\mathfrak{S}_n$. Three formulae are known for $R_{n,k}$, the number of permutations in $\mathfrak{S}_n$ with $k$ alternating runs, but all of them are complicated. We show that when alternating runs are enumerated with sign taken into account, one gets a {\it neat formula}. This has several consequences: we firstly get a near refinement of a result of Wilf on the exponent of $(1+t)$ that divides the alternating-runs polynomial in $\mathcal{A}_n$, the alternating group. Other applications include a moment-type identity, and enumeration of alternating permutations in $\mathcal{A}_n$. Similar results are obtained for the type B and type D Coxeter groups. This is a joint work with Krishnan Sivasubramanian.

ANDREW GOODALL, Charles University Prague
Tutte's dichromate for signed graphs  [PDF]

A signed graph is a graph with signed edges (positive or negative). Two signed graphs are considered equivalent if their edge signs differ on a cutset of the graph. Proper colourings and nowhere-zero flows of signed graphs are defined analogously to those of graphs. For graphs, these are both enumerated by evaluations of the Tutte polynomial. For signed graphs, Zaslavsky enumerated proper colourings, and recently DeVos--Rollov\'a--\v{S}\'amal showed that the number of nowhere-zero flows satisfies a deletion-contraction recurrence, and, independently, Qian--Ren and Goodall--Litjens--Regts--Vena gave a subset expansion formula. We construct a trivariate polynomial invariant of signed graphs that contains both the number of proper colourings and the number of nowhere-zero flows as evaluations: for this, three variables are needed. Specializations include Zaslavsky’s bivariate rank-generating polynomial of the (frame matroid of the) signed graph and the Tutte polynomial of the (cycle matroid of the) underlying graph.

YITING JIANG, Université de Paris (IRIF), France and Zhejiang Normal University, China
Colouring of generalized signed planar graphs  [PDF]

Assume $G$ is a graph and $S$ is a set of permutations of positive integers. An $S$-signature of $G$ is a pair $(D, \sigma)$, where $D$ is an orientation of $G$ and $\sigma: E(D) \to S$ is a mapping which assigns to each arc $e=(u,v)$ a permutation $\sigma(e)$ in $S$. We say $G$ is $S$-$k$-colourable if for any $S$-signature $(D, \sigma)$ of $G$, there is a mapping $f: V(G) \to [k]$ such that for each arc $e=(u,v)$ of $G$, $\sigma(e)(f(u)) \ne f(v)$. The concept of $S$-$k$-colourable is a common generalization of many colouring concepts. We call a set $S\in S_4$ \emph{good} if every planar graph is $S$-$4$-colourable. The Four Colour Theorem is equivalent to say that $S=\{id\}$ is good. In this talk, we figure out the good sets in $S_4$. We also consider similar problems on triangle-free planar graphs, since Gr\"otzsch's theorem says that every triangle-free planar graph is $3$-colourable.

ROBERT ŠÁMAL, Charles University
Many flows in the group connectivity setting  [PDF]

Two well-known results about nowhere-zero flows are Jaeger's 4-flow theorem asserting that every 4-edge-connected graph has a nowhere-zero $\mathbb{Z}_2\times\mathbb{Z}_2$-flow and Seymour's 6-flow theorem asserting that every 2-edge-connected graph has a nowhere-zero $\mathbb{Z}_6$-flow. In both of these settings, exponentially many flows exist; we improve earlier results in this direction.

The concept of a nowhere-zero flow was extended by Jaeger, Linial, Payan, and Tarsi to a choosability-type setting. An oriented graph $G=(V,E)$ is called $\Gamma$-\emph{connected} if for every function $f:E\rightarrow\Gamma$ there is a flow $\phi:E\rightarrow\Gamma$ with $\phi(e)\neq{}f(e)$ for every $e\in{}E$. Jaeger et al.\ proved that every oriented 3-edge-connected graph is $\Gamma$-connected whenever $|\Gamma|\ge6$. We prove that there are exponentially many solutions whenever $|\Gamma|\ge8$. For the group $\mathbb{Z}_6$ we prove that for every oriented 3-edge-connected $G=(V,E)$ with $\ell=|E|-|V|\ge11$ and every $f:E\rightarrow\mathbb{Z}_6$, there are at least $2^{ \sqrt{\ell}/\log\ell}$ flows $\phi$ with $\phi(e)\neq{}f(e)$ for every $e\in{}E$.

Joint work with M.DeVos, R.Langhede, and B.Mohar.