Seminar

Title: Non-Commutative Algebras and Graphs

Abstract:

I will discuss some of the non-commutative algebras that arise naturally in graph theory.

Title: Feynman graphs, ribbon graphs and tensor graphs

Abstract:

In this talk I will define the so-called Feynman graphs, which are a particular class of graphs appearing in quantum field theory.

Title: Optimization and Cryptography in Generalized Physical Theories 

Abstract:

In this talk, I will discuss three important cryptographic tasks in the quantum and post-quantum world. I will discuss the impossibility of bit-commitment and coin-flipping, and also the possibility of physically unforgeable money in the framework of Generalized Physical Theories (GPTs).

Title: The combinatorics of nearest and furthest values

Abstract:

A classical problem asks us to find, for each element $A[i]$ of an array of integers, the position of the nearest smallest element.

Title: Counting subdivergence-free gluing of trees

Abstract:

If we take two rooted trees with the same number of leaves and form a graph by gluing the leaves of one tree to the other, then we say the graph is subdivergence-free if no 2-edge cut have been generated.

Title: Bijections among symmetric tableaux via folding and mixed insertion

Abstract:

A standard Young tableau with entries $-M < \cdots -1 < 1 < \cdots < M$ can be "folded" by performing certain conversions and rectifications in sequence.

Title: Stable marraige with general preferences

Abstract:

This week, we discuss a generalization of the standard stable marriage problem, in which one side has a complete, totally ordered, strict preference list while the other has preferences given in terms of arbitrary binary relations.

Title: Kemeny's Constant for Markov Chains

Abstract:

Markov chains are a much-studied class of stochastic processes, and it is well-known that if the transition matrix A associated with a Markov chain possesses a certain property (called primitivity), then the long-term behaviour of the Markov chain is described by a particular eigenvector of A, known as the stationary distribution vector.

Title: New and Simple Algorithms for Stable Flow Problems

Abstract:

In the previous reading group talk we defined stable flows and saw that they always exist by a reduction to the stable allocation problem.

Title: Graphs in algebra and algebra in graphs

Abstract:

How do algebraic properties of a graph relate to its graph theoretic properties? What are algebraic properties of graphs? What does the spectrum of a graph tell us about its structure? What is a Cayley graph?