Atlantic Graph Theory Seminar
October 23, 2024 @ 3:30 pm - 4:30 pm
Speaker #1: Peter Collier, Dalhousie University
Title #1: Zero Forcing on Twisted Hypercubes
Abstract #1:
The hypercube stands out as a compelling and versatile structure that extends the geometric notion of a cube into higher dimensions. We study the twisted hypercube variant in an attempt to optimize processes on similarly degree-regular, highly connected graphs. The particular process we optimize is zero forcing, a graph infection process in which a particular colour change rule is iteratively applied to the graph and an initial set of vertices. We use the alternative framing of forcing arc sets to construct a family of twisted hypercubes of dimension k$\geq3$ with zero forcing sets of size $2^{k-1}-2^{k-3}+1$.
Speaker #2: Alexander Clow, Simon Fraser University
Title #2: Cornering Robots and Synchronizing Automata
Abstract #2:
A deterministic finite automata (DFA) is a model for any deterministic computational system with a finite number of states. In this talk, we describe a DFA as a finite directed multigraph G = (V, E), possibly with loops, along with an edge labelling ψ : E → Ψ. Here the vertices of the graph are the states the system might be in, the edge labels are possible inputs to the system, and the edges represent the transitions between states. Words σ generated from the alphabet Ψ act on vertices, v, as if v is the initial state of the system, and σ(v) is the state of the system after input σ is given. A word σ is synchronizing if for all u, v ∈ V , σ(u) = σ(v).
In this talk, we define a general strategy for constructing synchronizing words, which we call the cornering strategy. We then show that a DFA is synchronizable if and only if the cornering strategy can be successfully applied. As a demonstration of the strategy, we will discuss how all DFAs arising from movement in Rd can be synchronized. This is joint work with Peter Bradshaw (University of Illinois Urbana-Champaign) and Ladislav Stacho (Simon Fraser University).
Zoom link:
Meeting ID: 868 6149 9971
Passcode: 325258