Seminar

Title: A covering graph perspective on Huang’s theorem 

Abstract:

Just about a year ago, Hao Huang resolved the sensitivity conjecture by proving that any induced subgraph on more than half the vertices of the hypercube $Q_n$ has maximum degree at least $\sqrt(n)$. The key ingredient in his proof is a special $\pm 1$ signing of the adjacency matrix of $Q_n$.

Title: Formulas for Macdonald polynomials arising from the ASEP

Abstract:

The asymmetric simple exclusion process (ASEP) is a one-dimensional model of hopping particles that has been extensively studied in statistical mechanics, probability, and combinatorics. It also has remarkable connections with orthogonal symmetric polynomials in many variables such as Macdonald and Koornwinder polynomials.

Title: Factorial Schur Functions and Quantum Intergrability

Abstract:

I will introduce factorial Schur functions as they relate to my Master's thesis. Factorial Shur functions are a generalization of Schur functions with a second family of "shift" parameters. In 2009, Zinn-Justin reproved the answer to a tiling problem (the puzzle rule) with a toy fermionic model, using techniques from physics to extract the result.

Title: Number-theoretic methods in quantum computing

Abstract:

An important problem in quantum computing is the so-called \emph{approximate synthesis problem}: to find a quantum circuit, preferably as short as possible, that approximates a given target operation up to given $\epsilon$. For nearly two decades, from 1995 to 2012, the standard solution to this problem was the Solovay-Kitaev algorithm, which is based on geometric ideas. This algorithm produces circuits of size $O(\log^c(1/\epsilon))$, where $c$ is a constant approximately equal to $3.97$. It was a long-standing open problem whether the exponent $c$ could be reduced to $1$.

Title: 2-Connected Chord Diagrams and Applications in QFT

Abstract:

A functional equation for 2-connected chord diagrams is derived, then is used to calculate asymptotic information for the number of 2-connected chord diagrams by means of alien derivatives applied to factorially divergent power series.

Title: Discrete diffusion on graphs and real hyperplane arrangements

Abstract:

In 2016, Duffy, Lidbetter, Messinger, and Nowakowski introduced the following variation of a chip-firing model on a graph. At time zero, there is an integer number of "chips" at each vertex. Time proceeds in discrete steps.  At each step, each edge is examined (in parallel) -- one chip is moved from the greater end to the lesser end if the ends are not equal.

Title: Widths in even-hole-free graphs

Abstract:

Historically, the study of even-hole-free graphs is motivated by the analogy with perfect graphs. The decomposition theorems that are known for even-hole-free graphs are seemingly more powerful than the ones for perfect graphs: the basic classes and the decompositions are in some respect more restricted. But strangely, in an algorithmic perpective, much more is known for perfect graphs. 

Title: Sandpiles and representation theory

Abstract:

For an undirected graph, its sandpile group is an interesting isomorphism invariant-- it is a finite abelian group that describes the integer cokernel of the graph's Laplacian matrix.

Title: Graph coloring of graphs with large girth is hard for the Nullstellensatz

Abstract:

In this talk we will discuss a method to solve combinatorial problems using hierarchies of systems of linear equations using Hilbert's Nullstellensatz. In particular, we will study the behaviour of these hierarchies for deciding the non-$k$-colorabilty of graphs.

Title: An Upper Bound on Graphical Partitions

Abstract:

An integer partition is called graphical if it can be realized as the size-ordered degree sequence of a simple graph (with no loops or multiple edges).  In his 1736 paper on the Königsberg bridge problem, arguably the origin of graph theory, Euler gave a necessary condition for a partition to be graphical: its sum must be even.