UPCOMING SEMINARS
October 29, 2021 - 'Ramsey and Density Results for Approximate Arithmetic Progressions'
Speaker: Marcelo Sales (Emory)
When: October 29th, 2021 via ZOOM at 2:30pm
Abstract:
Let AP_k = {a,a+d,…,a+(k−1)d} be an arithmetic progression of length k. For a given ε > 0, we call a set AP_k(ε) = {x0,…,xk−1} an ε-approximate arithmetic progression of length k if for some a and d,
|xi −(a+id)|<εd
holds for all i ∈ {0,1…,k−1}. In this talk we discuss numerical aspects of Van der Waerden and Szemer edi type of results in which arithmetic progressions are replaced by their ε-approximation.
Seminar Category: Combinatorics
PAST SEMINARS
October 22, 2021 - Maximizing Five Cycles in K_r-free Subgraphs
Speaker: Kyle Murphy (Dakota State)
When: October 22nd, 2021 via ZOOM at 3:30pm
Abstract: Recently, Palmer and Gerbner defined the term $F$-Tur\’an Good to describe a graph $H$ which is unique maximized by the Tur\’an graph for all sufficiently large $F$-free graphs. Along with Bernard Lick\’y we used the flag algebra method to prove that $C_5$ is $K_{r+1}$-Tur\’an Good for $r \geq 3$. In this talk, I will discuss this result, in addition to giving a brief introduction to the flag algebra method.
Seminar Category: Combinatorics
October 19, 2021 - 'Huntington Varieties'
Speaker: Ranganathan Padmanabhan (University of Manitoba)
When: October 19, 2021 via ZOOM at 2:40pm
Abstract:
A variety KK of lattices is called Huntington if every uniquely complemented lattice in KK is distributive. In 1904, E.V. Huntington conjectured that every uniquely complemented lattice was distributive. In fact, the conjecture had been verified for several special classes of lattices. However, in 1945, Dilworth shattered this conjecture by proving that any lattice can be embedded into a uniquely complemented lattice. In 1981, Adams and Sichler strengthened the original embedding theorem of Dilworth by showing the existence of continuumly many varieties in which each lattice can be embedded in a uniquely complemented lattice of the same variety!
In spite of these deep theorems, it is still hard to find “nice” and “natural” examples of uniquely complemented lattices that are not Boolean. The reason is that uniquely complemented lattices having a little extra structure most often turn out to be distributive. This seems to be the essence of Huntington’s original conjecture. Accordingly, we plan to attack the problem backwards: that is, by finding additional (albeit, mild) conditions that, if added, would solve the problem in the affirmative. Many such conditions were already discovered during 1930’s and 40’s. The most notable among such conditions – due to Birkhoff and von Neumann – is modularity which is the only known variety defining a Huntington variety. Here we present several lattice implications forcing a uniquely complemented lattice to be distributive. Since some of these sentences are consequences of modularity, we obtain generalizations of the classical result of Birkhoff and von Neumann that every uniquely complemented modular lattice is a Boolean algebra. In particular, we prove that every uniquely complemented lattice in the least nonmodular variety containing the variety of all modular lattices is distributive. Finally we show that there are continuumly many non-modular Huntington varieties of lattices.
Seminar Category: Rings and Modules
October 15, 2021 - Continuous-Time Quantum Walks and Twin Vertices
Speaker: Hermie Monterde (Manitoba, Math)
When: October 15th, 2021 via ZOOM
Abstract: Undirected graphs are used to model quantum spin networks, with the vertices and edges representing the qubits and their interactions, respectively. Each of these qubits has an associated quantum state that contains information, and in order to construct an operational quantum computer, two tasks must be performed: the accurate transmission of quantum states from one location in the quantum computer to another, and the generation of entanglements between quantum states.
Let G be an undirected graph, and M be a Hermitian matrix associated with G. By axioms of quantum mechanics, the matrix U(t)=e^{itM} governs the evolution of the quantum system represented by G at any time t and determines a continuous-time quantum walk on X. The entries of U(t) give information about the probability of state transfer between any two vertices of G at time t. In particular, if |U(\tau)_{j,k}|^2=1, then we say that perfect state transfer occurs from vertex j to vertex k at time \tau, while if |U(\tau)_{j,k}|^2 can be made arbitrarily close to 1 by appropriate choices of \tau, then we say that pretty good state transfer occurs from j to k. On the other hand, if entries on the jth and kth columns of U(t) are zero at time \tau except for those indexed by j and k, then we say that fractional revival occurs between vertices j and k at time \tau.
In this talk, we look at the properties perfect state transfer, pretty good state transfer and fractional revival, as well as determine which of these quantum phenomena occur between twin vertices in an undirected graph.
Seminar Category: Combinatorics
October 5, 2021 - Resultant-Based Methods for Skew Elimination
Speaker: Raqeeb Rasheed (University of Manitoba)
When: October 5, 2021 via ZOOM
Abstract: This talk is about resultant-based methods for elimination of indeterminates of skew polynomial systems. We define the concept of resultant for bivariate skew polynomials via Dieudonné determinant and then applying a modular technique to improve the efficiency of the method. Then the general case can be expressed recursively.
Seminar Category: Rings and Modules
October 1, 2021 - Algorithms for Burning Graph Families
Speaker: Shahin Kamali (Manitoba, CS)
When: October 1, 2021 via ZOOM
Abstract: Graph burning is a simple model for the spread of social influence in networks. The objective is to measure how quickly a “fire”, e.g., a piece of fake news, can be spread in a network. The burning process takes place in discrete rounds. In each round, a new fire breaks out at a vertex, while the old fires extend to their neighbours and burn them. A burning schedule selects where the new fire breaks out at each round, and the burning problem asks for a schedule that burns all vertices in a minimum number of rounds. In this talk, we review some recent algorithmic results for burning families of graphs that include graphs of bounded path-width, tree-width, pathlength, and certain families of dense graphs.
Seminar Category: Combinators Seminars
September 24, 2021 - Fidelity of Quantum State Transfer on Paths with Potentials
Speaker: Christopher van Bommel (Manitoba, Math)
When: September 24, 2021 via ZOOM
Abstract: Quantum computing is believed to provide many advantages over traditional computing, particularly considering the speed at which computations can be performed. One of the challenges that needs to be resolved in order to construct a quantum computer is the transmission of information from one part of the computer to another. This transmission can be implemented by spin chains, which can be modeled as a graph, and analyzed using algebraic graph theory. The goal of quantum communication is to transmit information with a high level of accuracy, or fidelity. We consider a continuous time quantum walk on an unweighted path on n vertices, to which a loop (potential) of weight w has been added at each end vertex and discuss the fidelity that can be achieved.
This talk is based on joint work with Steve Kirkland.