Speaker: Tommy Cai (UManitoba)
Title: Regular Left-orderings of Integer Lattice
Time: 11:30am
Room: 225 St Paul's College
Zoom link: https://umanitoba.zoom.us/j/65251826619 password the first 6 Fibonacci numbers (starting with 11...)
Abstract: A finite state automaton (FSA) can be viewed as a finite directed graph whose edges are labeled by symbols from an alphabet. It has a designated initial vertex and a set of accepting vertices. The regular language recognized by the FSA is the set of all words that label paths starting from the initial vertex and ending at an accepting vertex.
A group G is left-orderable if there is a sub-semigroup P, called a positive cone, such that for every element g in G, either g is in P, or g is identity or g^{-1} is in P. We call such P a left-ordering of G, and say this left-ordering is regular if there is a FSA M, with alphabet \Sigma and language L(M) recognized by M, and there is a homomorphism \phi from \Sigma^*, the free subgroup generated by \Sigma, to G, such that \phi(L(M))=P.
For each integer n, the integer lattice \mathbb Z^n is left-orderable, and it has many left-orderings. We characterize all the regular left-orderings of \mathbb Z^n.
This is a joint work with Danna Kapoostinsky and Colin Krisko.
Speaker: Ben Moore (UManitoba)
Title: Flow-critical graphs
Time: 11:30am
Room: TBA
Zoom link: TBA
Abstract: Tutte boldly conjectured that every 4-edge-connected graph admits an orientation such that every vertex has indegree - outdegree divisible by three. If true, this is a wide-reaching generalization of the fact that triangle-free planar graphs are 3-colourable. In a breakthrough result in 2013, thomassen proved that 8-edge-connected suffices, and then later he reduced this to 6-edge-connected.
I'll show that we can find orientations such that the indegree - outdegree is any prescribed value for any vertex, so long as the entire sum is divisible by 3, with one vertex preoriented, and with the graph being mostly 5-edge-connected, which is a significant strengthening of the theorem of Thomassen.
This is joint work with Soffia arnadottir, Zdenek Dvorak, Bernard Lidicky, Evelyne Smith Roberge, Robert Samal