The Erdos-Hajnal conjecture states that for every graph H there exists c > 0 such that every n-vertex graph G either contains H as an induced subgraph, or has a clique or stable set of size at least n^c. I will talk about a proof of this conjecture for the case H = C5 (a five-cycle), and related results. The proof is based on an extension of a lemma about bipartite graphs due to Pach and Tomon. This is joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour.
Emergent Research: The PIMS Postdoctoral Fellow Seminar
Abstract:
This talk introduces a probabilistic approach to numerically compute geometric convergence rates in discrete or continuous stochastic systems. Choosing appropriate coupling mechanisms and combining them together, works well in many settings, especially in high-dimensions. Using this approach, it is observed that the rate of geometric ergodicity of a randomly perturbed system can, to some extent, reveal the degree of chaoticity of the unperturbed system. Potential applications of the coupling method and the visualization of higher dimensional non-convex functions, e.g., the loss functions of neural networks, will be discussed.
Emergent Research: The PIMS Postdoctoral Fellow Seminar
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 ideal situation is that of perfect state transfer, where there exists a time interval during which the information is perfectly moved from one location to another. As perfect state transfer is relatively rare, we also consider pretty good state transfer, where for any desired level of accuracy, there exists a time interval during which the information transfer achieves this accuracy. We will discuss determining whether graphs admit perfect or pretty good state transfer.
Comparisons are constantly being made between the 1918 influenza pandemic and the present COVID-19 pandemic. We will discuss our previous work on influenza pandemics, and the tools we have used to understand the temporal patterns of those outbreaks. Applying similar tools to the COVID-19 pandemic is easier in some respects and harder in others. We will describe our current approach to modelling the spread of COVID-19, and some of the challenges and limitations of epidemic forecasting.
Recently there has been a lot of progress in classifying phases of gapped quantum many-body systems. From the mathematical viewpoint, a phase of a quantum system is a connected component of the “space” of gapped quantum systems, and it is natural to study the topology of this space. I will explain how to probe it using generalizations of the Berry curvature. I will focus on the case of lattice systems where all constructions can be made rigorous. Coarse geometry plays an important role in these constructions.
Suppose mu is a probability measure which is shift invariant on {0,1}^{Z^d} and we know that for almost every configuration x in {0,1}^{Z^d} there are connected components of 1s which are infinite. In this talk, we will follow a paper by Burton and Keane (generalising results by Aizenman, Kesten and Newman) to give an elegant proof of the fact that, under fairly general conditions (say full support), the number of connected components of infinite cardinality is at exactly one.
Measuring the impact of scientific articles is important for evaluating the research output of individual scientists, academic institutions, and journals. While citations are raw data for constructing impact measures, there exist biases and potential issues if factors affecting citation patterns are not properly accounted for. In this work, we address the problem of field variation and introduce an article-level metric useful for evaluating individual articles’ visibility. This measure derives from joint probabilistic modeling of the content in the articles and the citations among them using latent Dirichlet allocation (LDA) and the mixed membership stochastic blockmodel (MMSB). Our proposed model provides a visibility metric for individual articles adjusted for field variation in citation rates, a structural understanding of citation behavior in different fields, and article recommendations that take into account article visibility and citation patterns.
Accessibility is a fundamental tool when working with partially hyperbolic systems. For instance, in the 1970s it was used as a tool to show certain systems were transitive, and in the 1990s it was used to establish stable ergodicity. We will review the general notion and how it applies in these settings. We will also review the result from 2003 by Dolgopyat and Wilkinson on the C^1 density of stably transitive systems.