2015 Workshop on Combinatorics and Applications at SJTU

April 21 -- 27, Shanghai Jiao Tong University

Home || Participants || Track A : Spherical Design and Numerical Analysis || Track B : Graph Homomorphisms and Dynamical Systems || Direction

Speaker: Yinfeng Zhu (祝隱峰), Shanghai Jiao Tong University

Date: Saturday, April 25, 2015

Time: 17:05 - 17:20

Venue: Large Meeting Room, Math Building

Title: A Glimpse at Boolean Linear Dynamical Systems


Let $\Gamma$ be a digraph. The Boolean linear dynamical system corresponding to $\Gamma$ is the digraph $\mathcal{P}\mathcal{S}_\Gamma$ whose vertex set is the set of nonempty subsets of $V(\Gamma)$ and $A \rightarrow B$ is an arc of $\mathcal{P}\mathcal{S}_\Gamma$ if and only if $B$ is the union of all those out-neighbors of vertices in $A$ in $\Gamma$. In the first part of the talk we show that whenever there is a walk from $A$ to $B$ in $\mathcal{P}\mathcal{S}_\Gamma$ then there is such a walk of length at most $D(\Gamma)|B|$ where $|B|$ is the size of the set $B$ and $D(\Gamma)$ is the diameter of $\Gamma$.

If $\mathcal A=\{\Gamma_1, \ldots, \Gamma_k\}$ is a set of $k$ digraphs on the same vertex set $V$, the Boolean linear dynamical system corresponding to $\mathcal A$ is the union of the $k$ digraphs $\mathcal{P}\mathcal{S}_{\Gamma_i}, i=1, \ldots, k,$, which we denote by $\mathcal{P}\mathcal{S}_{\mathcal A}$. We call $\mathcal A$ primitive if there is a number $T$ such that every walk of length at least $T$ in $\mathcal{P}\mathcal{S}_{\mathcal A}$ must end at $V$. In the second part of the talk we discuss some basic parameters associated with $k$ and $T$ in the framework of primitive Boolean linear dynamical systems.

This is joint work with Yaokun Wu and Zeying Xu.