A functional digraph is a finite digraph in which each vertex has a unique out-neighbor. Considered up to isomorphism and endowed with the directed sum and product, functional digraphs form a semigroup that has recently attracted significant attention, particularly regarding its multiplicative structure. In this context, a functional digraph X divides a functional digraph A if there exists a functional digraph Y such that XY is isomorphic to A . The digraph X is said to be prime if it is not the identity for the product, and if, for all functional digraphs A and B , the fact that X divides AB implies that X divides A or B . In 2020, Antonio E. Porreca asked whether prime functional digraphs exist, and in 2023, his work led him to conjecture that they do not. However, in 2024, Barbora Hudcová discovered that this result had already been proven by Ralph Seifert in 1971, in a somewhat forgotten paper. The terminology in that work differs significantly from that used in recent studies, the framework is more general, and the non-existence of prime functional digraphs appears only as a part of broader results, relying on (overly) technical lemmas developed within this general setting. The aim of this note is to present a much more accessible version of Seifert’s proof — that no prime functional digraph exists — by using the current language and simplifying each step as much as possible.

Abstract Boolean networks are popular tools for the exploration of qualitative dynamical properties of biological systems. Several dynamical interpretations have been proposed based on the same logical structure that captures the interactions between Boolean components. They reproduce, in different degrees, the behaviours emerging in more quantitative models. In particular, regulatory conflicts can prevent the standard asynchronous dynamics from reproducing some trajectories that might be expected upon inspection of more detailed models. We introduce and study the class of networks with linear cuts, where linear components—intermediates with a single regulator and a single target—eliminate the aforementioned regulatory conflicts. The interaction graph of a Boolean network admits a linear cut when a linear component occurs in each cycle and in each path from components with multiple targets to components with multiple regulators. Under this structural condition the attractors are in one-to-one correspondence with the minimal trap spaces, and the reachability of attractors can also be easily characterized. Linear cuts provide the base for a new interpretation of the Boolean semantics that captures all behaviours of multi-valued refinements with regulatory thresholds that are uniquely defined for each interaction, and contribute a new approach for the investigation of behaviour of logical models.

Given a digraph $G$, much attention has focused on the maximum number $\phi(G)$ of fixed points in a Boolean network $f:\{0,1\}^n\to\{0,1\}^n$ with $G$ as interaction graph. In particular, a central problem in network coding consists in studying the optimality of the feedback bound $\phi(G)\leq 2^{\tau}$, where $\tau$ is the minimum size of a feedback vertex set of $G$. In this paper, we study the maximum number $\phi_m(G)$ of fixed points in a monotone Boolean network with interaction graph $G$. We establish new upper and lower bounds on $\phi_m(G)$ that depend on the cycle structure of $G$. In addition to $\tau$, the involved parameters are the maximum number $\nu$ of vertex-disjoint cycles, and the maximum number $\nu^*$ of vertex-disjoint cycles verifying some additional technical conditions. We improve the feedback bound $2^\tau$ by proving that $\phi_m(G)$ is at most the largest sublattice of $\{0,1\}^\tau$ without chain of size $\nu+2$, and without another forbidden pattern described by two disjoint antichains of size $\nu^*+1$. Then, we prove two optimal lower bounds: $\phi_m(G)\geq \nu+1$ and $\phi_m(G)\geq 2^{\nu^*}$. As a consequence, we get the following characterization: $\phi_m(G)=2^\tau$ if and only if $\nu^*=\tau$. As another consequence, we get that if $c$ is the maximum length of a chordless cycle of $G$, then $2^{\nu/3^c}\leq\phi_m(G)\leq 2^{c\nu}$. Finally, with the techniques introduced, we establish an upper bound on the number of fixed points of any Boolean network according to its signed interaction graph.

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations toward their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. The guessing number approach converts this problem into determining the number of fixed points of coding functions f : An→ Anover a finite alphabet A (usually referred to as Boolean networks if A = {0, 1}) with a given interaction graph that describes which local functions depend on which variables. In this paper, we generalize the so-called reduction of coding functions in order to eliminate variables. We then determine the maximum number of fixed points of a fully reduced coding function, whose interaction graph has a loop on every vertex. Since the reduction preserves the number of fixed points, we then apply these ideas and results to obtain four main results on the linear network coding solvability problem. First, we prove that non-decreasing coding functions cannot solve any more instances than routing already does. Second, we show that the triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing. This is the first classification result for the linear network coding solvability problem. Third, we exhibit a new class of non-linearly solvable graphs. Fourth, we determine large classes of strictly linearly solvable graphs.

In this paper, we are interested in the number of fixed points of functions $f:A^n\to A^n$ over a finite alphabet $A$ defined on a given signed digraph $D$. We first use techniques from network coding to derive some lower bounds on the number of fixed points that only depends on $D$. We then discover relationships between the number of fixed points of $f$ and problems in coding theory, especially the design of codes for the asymmetric channel. Using these relationships, we derive upper and lower bounds on the number of fixed points, which significantly improve those given in the literature. We also unveil some interesting behavior of the number of fixed points of functions with a given signed digraph when the alphabet varies. We finally prove that signed digraphs with more (disjoint) positive cycles actually do not necessarily have functions with more fixed points.