Tue, 17 Oct 2023

14:00 - 15:00
Online

$k$-blocks and forbidden induced subgraphs

Maria Chudnovsky
(Princeton)
Further Information

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

Abstract

A $k$-block in a graph is a set of $k$ vertices every two of which are joined by $k$ vertex disjoint paths. By a result of Weissauer, graphs with no $k$-blocks admit tree-decompositions with especially useful structure. While several constructions show that it is probably very difficult to characterize induced subgraph obstructions for bounded tree width, a lot can be said about graphs with no $k$-blocks. On the other hand, forbidding induced subgraphs places significant restrictions on the structure of a $k$-block in a graphs. We will discuss this phenomenon and its consequences in the study of tree-decompositions in classes of graphs defined by forbidden induced subgraphs.

Tue, 05 Mar 2024
13:00
L3

Double scaled SYK and the quantum geometry of 3D de Sitter space

Herman Verlinde
(Princeton)
Abstract

In this talk, I describe an exact duality between the double scaling limit of the SYK model and quantum geometry of de Sitter spacetime in three dimensions. The duality maps the so-called chord rules that specify the exact SYK correlations functions to the skein relations that govern the topological interactions between world-line operators in 3D de Sitter gravity.

This talk is part of the series of Willis Lamb Lectures in Theoretical Physics. Herman Verlinde is the Lamb Lecturer of 2024.

Tue, 09 May 2023

14:00 - 15:00
L5

Colouring and domination in tournaments

Paul Seymour
(Princeton)
Abstract

"Colouring" a tournament means partitioning its vertex set into acylic subsets; and the "domination number" is the size of the smallest set of vertices with no common in-neighbour. In some ways these are like the corresponding concepts for graphs, but in some ways they are very different. We give a survey of some recent results and open questions on these topics.

Joint with Tung Nguyen and Alex Scott.

Tue, 07 Mar 2023

14:00 - 15:00
Virtual

A loglog step towards the Erdős-Hajnal conjecture

Paul Seymour
(Princeton)
Further Information

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

Abstract

In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $|G|^c$ replaced by $2^{c\sqrt{\log |G|}}$. Until now, there has been no improvement on this result (for general $H$). We recently proved a strengthening: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $2^{c\sqrt{\log |G| \log\log|G|}}$. This talk will outline the proof. Joint work with Matija Bucić, Tung Nguyen and Alex Scott.

Mon, 17 Jan 2022

15:30 - 16:30
Virtual

The link surgery formula and plumbed 3-manifolds

Ian Zemke
(Princeton)
Abstract

Lattice homology is a combinatorial invariant of plumbed 3-manifolds due to Nemethi. The definition is a formalization of Ozsvath and Szabo's computation of the Heegaard Floer homology of plumbed 3-manifolds. Nemethi conjectured that lattice homology is isomorphic to Heegaard Floer homology. For a restricted class of plumbings, this isomorphism is known to hold, due to work of Ozsvath-Szabo, Nemethi, and Ozsvath-Stipsicz-Szabo. By using the Manolescu-Ozsvath link surgery formula for Heegaard Floer homology, we prove the conjectured isomorphism in general. In this talk, we will talk about aspects of the proof, and some related topics and extensions of the result.

Fri, 27 May 2022

15:00 - 16:00
L2

The nonlinear stability of Kerr for small angular momentum

Sergiu Klainerman
(Princeton)
Abstract

I will report on my most recent results  with Jeremie Szeftel and Elena Giorgi which conclude the proof of the nonlinear, unconditional, stability of slowly rotating Kerr metrics. The main part of the proof, announced last year, was conditional on results concerning boundedness and decay estimates for nonlinear wave equations. I will review the old results and discuss how the conditional results can now be fully established.

Fri, 11 Jun 2021

14:00 - 15:00

Geometric Methods for Machine Learning and Optimization

Melanie Weber
(Princeton)
Abstract

Many machine learning applications involve non-Euclidean data, such as graphs, strings or matrices. In such cases, exploiting Riemannian geometry can deliver algorithms that are computationally superior to standard(Euclidean) nonlinear programming approaches. This observation has resulted in an increasing interest in Riemannian methods in the optimization and machine learning community.

In the first part of the talk, we consider the task of learning a robust classifier in hyperbolic space. Such spaces have received a surge of interest for representing large-scale, hierarchical data, due to the fact that theyachieve better representation accuracy with fewer dimensions. We present the first theoretical guarantees for the (robust) large margin learning problem in hyperbolic space and discuss conditions under which hyperbolic methods are guaranteed to surpass the performance of their Euclidean counterparts. In the second part, we introduce Riemannian Frank-Wolfe (RFW) methods for constrained optimization on manifolds. Here, we discuss matrix-valued tasks for which such Riemannian methods are more efficient than classical Euclidean approaches. In particular, we consider applications of RFW to the computation of Riemannian centroids and Wasserstein barycenters, both of which are crucial subroutines in many machine learning methods.

Tue, 04 May 2021
16:00

Gluon Scattering in AdS from CFT

Xinan Zhou
(Princeton)
Abstract

In this talk, I will discuss AdS super gluon scattering amplitudes in various spacetime dimensions. These amplitudes are dual to correlation functions in a variety of non-maximally supersymmetric CFTs, such as the 6d E-string theory, 5d Seiberg exceptional theories, etc. I will introduce a powerful method based on symmetries and consistency conditions, and show that it fixes all the infinitely many four-point amplitudes at tree level. I will also point out many interesting properties and structures of these amplitudes, which include the flat space limit, Parisi-Sourlas-like dimensional reduction, hidden conformal symmetry, and a color-kinematic duality in AdS. Along the way, I will also review some earlier progress and the relation with this work. I will conclude with a brief discussion of various open problems. 

Tue, 16 Feb 2021
15:30
Virtual

Some unusual extremal problems in convexity and combinatorics

Ramon van Handel
(Princeton)
Further Information

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

Abstract

It is a basic fact of convexity that the volume of convex bodies is a polynomial, whose coefficients contain many familiar geometric parameters as special cases. A fundamental result of convex geometry, the Alexandrov-Fenchel inequality, states that these coefficients are log-concave. This proves to have striking connections with other areas of mathematics: for example, the appearance of log-concave sequences in many combinatorial problems may be understood as a consequence of the Alexandrov-Fenchel inequality and its algebraic analogues.

There is a long-standing problem surrounding the Alexandrov-Fenchel inequality that has remained open since the original works of Minkowski (1903) and Alexandrov (1937): in what cases is equality attained? In convexity, this question corresponds to the solution of certain unusual isoperimetric problems, whose extremal bodies turn out to be numerous and strikingly bizarre. In combinatorics, an answer to this question would provide nontrivial information on the type of log-concave sequences that can arise in combinatorial applications. In recent work with Y. Shenfeld, we succeeded to settle the equality cases completely in the setting of convex polytopes. I will aim to describe this result, and to illustrate its potential combinatorial implications through a question of Stanley on the combinatorics of partially ordered sets.

Tue, 26 Jan 2021
15:30
Virtual

Random friends walking on random graphs

Noga Alon
(Princeton)
Further Information

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

Abstract

Let $X$ and $Y$ be two $n$-vertex graphs. Identify the vertices of $Y$ with $n$ people, any two of whom are either friends or strangers (according to the edges and non-edges in $Y$), and imagine that these people are standing one at each vertex of $X$. At each point in time, two friends standing at adjacent vertices of $X$ may swap places, but two strangers may not. The friends-and-strangers graph $FS(X,Y)$ has as its vertex set the collection of all configurations of people standing on the vertices of $X$, where two configurations are adjacent when they are related via a single friendly swap. This provides a common generalization for the famous 15-puzzle, transposition Cayley graphs of symmetric groups, and early work of Wilson and of Stanley.
I will describe several recent results and open problems addressing the extremal and typical aspects of the notion, focusing on the result that the threshold probability for connectedness of $FS(X,Y)$ for two independent binomial random graphs $X$ and $Y$ in $G(n,p)$ is $p=p(n)=n-1/2+o(1)$.
Joint work with Colin Defant and Noah Kravitz.

Subscribe to Princeton