Search Talks

Abstract   Cographs are by definition $P_4$-free graphs, i.e. graphs avoiding the path $P_4$ as induced subgraph. In this talk, we will consider a uniform random cograph with $n$ vertices, for large $n$. We shall describe the (random) graphon limit of this object, which is constructed using a Brownian excursion. Motivated by some probabilistic work around Erdős-Hajnal conjecture, we also consider large independent sets in uniform cographs. For both aspects, cographs behave differently from most other $H$-free random graphs. Based on joint work with F. Bassino, M. Bouvel, M. Drmota, L. Gerin, M. Maazoun and A. Pierrot.

Abstract We will present out attempts thus far to develop a theory of graphon-valued stochastic processes. We will present a brief review of theory Graphons and dynamics constructed on the space of graphons. We shall construct and analyse a natural class of such processes arising from population genetics. In conclusion we shall present the challenges in our ongoing work on constructing dynamics where the edges and vertices interact with each other. This is joint work with Frank den Hollander and Adrian Roellin

Abstract In this talk, I will present the multivariate normal approximation for the centered subgraph counts in dense random graphs. The main motivation to investigate these statistics is the fact that they are key to understanding fluctuations of regular subgraph counts since they act as an orthogonal basis of a corresponding L2 space. We also identify the resulting limiting Gaussian stochastic measures by means of the theory of generalised U-statistics and Gaussian Hilbert spaces, which we think is a suitable framework to describe and understand higher-order fluctuations in dense random graph models. This is joint work with Adrian Roellin.

In this talk  will develop Rafael D. Sorkin's heuristic that a partially ordered process of the birth of spacetime atoms in causal set quantum gravity can provide an objective physical correlate of our perception of time passing. I will argue that one cannot have an external, fully objective picture of the birth process because the order in which the spacetime atoms are born is a partial order. I propose that live experience in causal set theory is an internal ``view'' of the objective birth process in which events that are neural correlates of consciousness occur. In causal set theory, what ``breathes fire'' into a neural correlate of consciousness is that which breathes fire into the whole universe: the unceasing, partially ordered process of the birth of spacetime atoms.

Zoom link: https://pitp.zoom.us/j/95170823205?pwd=QW9YM3QrZU12Ti9HTUQ4TDlVNmN5Zz09

Abstract For any given graph $H$, one may define a natural corresponding functional $\|.\|_H$ for real(or complex) valued functions by using the homomorphism density of $H$. We say that $H$ is \emph{norming} if $\|.\|_H$ is a norm. This generalises the Gowers octahedral norms, a widely used tool in extremal combinatorics to quantify quasirandomness. In 2008, Lov\'{a}sz asked what graphs are norming. This has been a central question in the theory of dense graph limits and also connects to Sidorenko's conjecture, a major open problem in extremal graph theory. For the recent few years, there have been interesting developments on the Lovász question, where algebraic combinatorics, extremal graph theory and functional analysis meet. In this talk, I will discuss some of the progress. Based on joint work with David Conlon, Frederik Garbe, Jan Hladk\'{y}, Bjarne Sch\"{u}lke, and Sasha Sidorenko.

The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d_1,...,d_n): starting with an empty n-vertex graph, it sequentially adds new random edges so that the degree of each vertex v_i remains at most d_i.  It is natural to ask whether the final graph of this process is similar to a uniform random graph with degree sequence D_n (for d-regular degree sequences D_n this was already raised by Wormald in the mid 1990s). We show that, for degree sequences D_n that are not nearly regular, the final graph of the degree-restricted random process differs substantially from a uniform random graph with degree sequence D_n.  Our proof uses the switching method, which is usually only applied to uniform random graph models -- rather than to stochastic processes. Based on joint work with Mike Molloy and Erlang Surya.

The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] posits that there exist families of Hamiltonians with all low energy states of non-trivial complexity (with complexity measured by the quantum circuit depth preparing the state). Our recent work https://arxiv.org/abs/2206.13228 (with Nikolas Breuckmann and Chinmay Nirkhe) proves this conjecture by showing that the recently discovered families of constant-rate and linear-distance QLDPC codes correspond to NLTS local Hamiltonians. This talk will provide background on the conjecture, its relevance to quantum many-body physics and quantum complexity theory, and touch upon the proof techniques.

Zoom link: https://pitp.zoom.us/j/94224635225?pwd=SUovNXA3MWlkRUJlcTIxV0pLQzQxdz09

Abstract For a given graph H we are interested in the critical value of p so that a sample of an Erdos-Renyi graph contains a copy of H with high probability,  Kahn and Kalai in 2006 conjectured that it should be given (up to a logarithm) by the minimum p so that in expectation all subgraphs H' of H appear in G(n,p). In this work, we will present a proof of a modified version of this conjecture. Our proof is based on a powerful "spread lemma", which played a key role in the recent breakthroughs on the sunflower conjecture and the proof of the fractional Kahn-Kali conjecture. Time permitting, we will discuss a new proof of the spread lemma using Bayesian inference tools. This is joint work with Elchanan Mossel, Jonathan Niles-Weed and Nike Sun

Abstract It is well known that sparse random graphs (where the number of edges is of the order of the number of vertices) contain only a small number of triangles. On the other hand, many networks observed in real life are sparse but contain a large number of triangles. Motivated by this discrepancy we ask the following two questions: How (un)likely is it that a sparse random graph contains a large number of triangles? What does the graph look like when it contains a large number of triangles? We also ask a related question: What is the probability that in a sparse random graph a large number of vertices are part of some triangle? We discuss these questions, as well as some applications to exponential random graph models.