|
Speaker: Michelle DelcourtTitle: Hypergraph Matchings Avoiding Forbidden SubmatchingsVenue: VirtualAbstract: In 1973, Erdős conjectured the existence of high girth (n,3,2)-Steiner systems. Recently, Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke proved the approximate version of Erdős’ conjecture. Just this year, Kwan, Sah, Sawhney, and Simkin proved Erdős’ conjecture. As for Steiner systems with more general parameters, Glock, Kühn, Lo, and Osthus conjectured the existence of high girth (n,q,r)-Steiner systems. We prove the approximate version of their conjecture. This result follows from our general main results which concern finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of submatchings (which we view as a hypergraph H where V(H)=E(G)). Our first main result is a common generalization of the classical theorems of Pippenger… |
|
Speaker: Yuval PeledTitle: The threshold for stacked triangulationsVenue: HybridAbstract: Consider a bootstrap percolation process that starts with a set of `infected’ triangles $Y \subseteq \binom{[n]}3$, and a new triangle f gets infected if there is a copy of K_4^3 (= the boundary of a tetrahedron) in which f is the only not-yet infected triangle. Suppose that every triangle is initially infected independently with probability p=p(n), what is the threshold probability for percolation — the event that all triangles get infected? How many new triangles do get infected in the subcritical regime? This notion of percolation can be viewed as a simplification of simple-connectivity. Namely, a stacked triangulation of a triangle is obtained by repeatedly subdividing an inner face into three faces. We ask: for which $p$… |
|
Speaker: Bernd SturmfelsTitle: Algebraic Statistics with a View towards PhysicsVenue: CMSA, 20 Garden St, G10Abstract: We discuss the algebraic geometry of maximum likelihood estimation from the perspective of scattering amplitudes in particle physics. A guiding examples the moduli space of n-pointed rational curves. The scattering potential plays the role of the log-likelihood function, and its critical points are solutions to rational function equations. Their number is an Euler characteristic. Soft limit degenerations are combined with certified numerical methods for concrete computations. **This talk will be hybrid. Talk will be held at CMSA (20 Garden St) Room G10. All non-Harvard affiliated visitors to the CMSA building will need to complete this covid form prior to arrival. LINK TO FORM |
|
Speaker: Karen YeatsTitle: Some combinatorics of Wilson loop diagramsVenue: HybridAbstract: Wilson loop diagrams can be used to study amplitudes in N=4 SYM. I will set them up and talk about some of their combinatorial aspects, such as how many Wilson loop diagrams give the same positroid and how to combinatorially read off the dimension and the denominators for the integrands. **This talk will be hybrid. Talk will be held at CMSA (20 Garden St) Room G10. All non-Harvard affiliated visitors to the CMSA building will need to complete this covid form prior to arrival. LINK TO FORM |
|
Speaker: Jaroslav TrnkaTitle: BCFW recursion relations and non-planar positive geometryVenue: VirtualAbstract: There is a close connection between the scattering amplitudes in planar N=4 SYM theory and the cells in the positive Grassmannian. In the context of BCFW recursion relations the tree-level S-matrix is represented as a sum of planar on-shell diagrams (aka plabic graphs) and associated with logarithmic forms on the Grassmannian cells of certain dimensionality. In this talk, we explore non-adjacent BCFW shifts which naturally lead to non-planar on-shell diagrams and new interesting subspaces inside the real Grassmannian. **This talk will be hybrid. Talk will be held at CMSA (20 Garden St) Room G10. All non-Harvard affiliated visitors to the CMSA building will need to complete this covid form prior to arrival. LINK TO FORM |
|
Speaker: Jan HladkyTitle: Flip processesVenue: VirtualAbstract: We introduce a class of random graph processes, which we call \emph{flip processes}. Each such process is given by a \emph{rule} which is just a function $\mathcal{R}:\mathcal{H}_k\rightarrow \mathcal{H}_k$ from all labelled $k$-vertex graphs into itself ($k$ is fixed). The process starts with a given $n$-vertex graph $G_0$. In each step, the graph $G_i$ is obtained by sampling $k$ random vertices $v_1,\ldots,v_k$ of $G_{i-1}$ and replacing the induced graph $F:=G_{i-1}[v_1,\ldots,v_k]$ by $\mathcal{R}(F)$. This class contains several previously studied processes including the Erd\H{o}s–R\’enyi random graph process and the triangle removal process. Given a flip process with a rule $\mathcal{R}$, we construct time-indexed trajectories $\Phi:\Gra\times [0,\infty)\rightarrow\Gra$ in the space of graphons. We prove that for any $T > 0$ starting with… |
|
Speaker: Francis BrownTitle: Moduli space of tropical curves, graph Laplacians and physicsVenue: VirtualAbstract: I will first review the construction of the moduli space of tropical curves (or metric graphs), and its relation to graph complexes. The graph Laplacian may be interpreted as a tropical version of the classical Torelli map and its determinant is the Kirchhoff graph polynomial (also called 1st Symanzik), which is one of the two key components in Feynman integrals in high energy physics.The other component is the so-called 2nd Symanzik polynomial, which is defined for graphs with external half edges and involves particle masses (edge colourings). I will explain how this too may be interpreted as the determinant of a generalised graph Laplacian, and how it leads to a volumetric interpretation of a certain class of Feynman… |
|
Speaker: Peleg MichaeliTitle: Greedy maximal independent sets via local limitsVenue: VirtualAbstract: The random greedy algorithm for finding a maximal independent set in a graph has been studied extensively in various settings in combinatorics, probability, computer science, and chemistry. The algorithm builds a maximal independent set by inspecting the graph’s vertices one at a time according to a random order, adding the current vertex to the independent set if it is not connected to any previously added vertex by an edge. In this talk, I will present a simple yet general framework for calculating the asymptotics of the proportion of the yielded independent set for sequences of (possibly random) graphs, involving a valuable notion of local convergence. I will demonstrate the applicability of this framework by giving short and straightforward… |
|
Speaker: Kathlén KohnTitle: Rational PolypolsVenue: VirtualAbstract: Eugene Wachspress introduced polypols as real bounded semialgebraic sets in the plane that generalize polygons. He aimed to generalize barycentric coordinates from triangles to arbitrary polygons and further to polypols. For this, he defined the adjoint curve of a rational polypol. In the study of scattering amplitudes in physics, positive geometries are real semialgebraic sets together with a rational canonical form. We combine these two worlds by providing an explicit formula for the canonical form of a rational polypol in terms of defining equations of the adjoint curve and the facets of the polypol. For the special case of polygons, we show that the adjoint curve is hyperbolic and provide an explicit description of its nested ovals…. |
|
Speaker: Igor BallaTitle: Equiangular lines and regular graphsVenue: VirtualAbstract: In 1973, Lemmens and Seidel asked to determine N_alpha(r), the maximum number of equiangular lines in R^r with common angle arccos(alpha). Recently, this problem has been almost completely settled when r is exponentially large relative to 1/alpha, with the approach both relying on Ramsey’s theorem, as well as being limited by it. In this talk, we will show how orthogonal projections of matrices with respect to the Frobenius inner product can be used to overcome this limitation, thereby obtaining significantly improved upper bounds on N_alpha(r) when r is polynomial in 1/alpha. In particular, our results imply that N_alpha(r) = Theta(r) for alpha >= Omega(1 / r^1/5). Our projection method generalizes to complex equiangular lines in C^r, which may… |
|
Speaker: Anna SeigalTitle: Invariant theory for maximum likelihood estimationVenue: VirtualAbstract: I will talk about work to uncover connections between invariant theory and maximum likelihood estimation. I will describe how norm minimization over a torus orbit is equivalent to maximum likelihood estimation in log-linear models. We will see the role played by polytopes and discuss connections to scaling algorithms. Based on joint work with Carlos Améndola, Kathlén Kohn, and Philipp Reichenbach. |
|
Speaker: Ran TesslerTitle: The Amplituhedron BCFW TriangulationVenue: VirtualAbstract: The (tree) amplituhedron was introduced in 2013 by Arkani-Hamed and Trnka in their study of N=4 SYM scattering amplitudes. A central conjecture in the field was to prove that the m=4 amplituhedron is triangulated by the images of certain positroid cells, called the BCFW cells. In this talk I will describe a resolution of this conjecture. The seminar is based on a recent joint work with Chaim Even-Zohar and Tsviqa Lakrec. |
|
Speaker: Jacob BourjailyTitle: Adventures in Perturbation TheoryVenue: VirtualAbstract: Recent years have seen tremendous advances in our understanding of perturbative quantum field theory—fueled largely by discoveries (and eventual explanations and exploitation) of shocking simplicity in the mathematical form of the predictions made for experiment. Among the most important frontiers in this progress is the understanding of loop amplitudes—their mathematical form, underlying geometric structure, and how best to manifest the physical properties of finite observables in general quantum field theories. This work is motivated in part by the desire to simplify the difficult work of doing Feynman integrals. I review some of the examples of this progress, and describe some ongoing efforts to recast perturbation theory in terms that expose as much simplicity (and as much physics) as… |
|
Speaker: Stefan GlockTitle: The longest induced path in a sparse random graphVenue: VirtualAbstract: A long-standing problem in random graph theory has been to determine asymptotically the length of a longest induced path in sparse random graphs. Independent work of Luczak and Suen from the 90s showed the existence of an induced path of roughly half the optimal size, which seems to be a barrier for certain natural approaches. Recently, in joint work with Draganic and Krivelevich, we solved this problem. In the talk, I will discuss the history of the problem and give an overview of the proof. |
|
Speaker: Matthew Jenssen (University of Birmingham)Title: The singularity probability of random symmetric matricesVenue: VirtualAbstract: Let M_n be drawn uniformly from all n by n symmetric matrices with entries in {-1,1}. In this talk I’ll consider the following basic question: what is the probability that M_n is singular? I’ll discuss recent joint work with Marcelo Campos, Marcus Michelen and Julian Sahasrabudhe where we show that this probability is exponentially small. I hope to make the talk accessible to a fairly general audience. |
|
Speaker: Karel Devriendt (University of Oxford)Title: Resistance curvature – a new discrete curvature on graphsVenue: VirtualAbstract: The last few decades have seen a surge of interest in building towards a theory of discrete curvature that attempts to translate the key properties of curvature in differential geometry to the setting of discrete objects and spaces. In the case of graphs there have been several successful proposals, for instance by Lin-Lu-Yau, Forman and Ollivier, that replicate important curvature theorems and have inspired applications in a variety of practical settings. In this talk, I will introduce a new notion of discrete curvature on graphs, which we call the resistance curvature, and discuss some of its basic properties. The resistance curvature is defined based on the concept of effective resistance which is a metric between the vertices… |
|
Speaker: Lutz WarnkeTitle: Prague dimension of random graphsVenue: VirtualAbstract: The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s: as a combinatorial measure of complexity, it is closely related to clique edges coverings and partitions. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order n/(log n) for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n). |
|
Speaker: Yinon SpinkaTitle: A tale of two balloonsVenue: VirtualAbstract: From each point of a Poisson point process start growing a balloon at rate 1. When two balloons touch, they pop and disappear. Will balloons reach the origin infinitely often or not? We answer this question for various underlying spaces. En route we find a new(ish) 0-1 law, and generalize bounds on independent sets that are factors of IID on trees. Joint work with Omer Angel and Gourab Ray. |
|
Speaker: Steven KarpTitle: Gradient flows on totally nonnegative flag varietiesVenue: VirtualAbstract: One can view a partial flag variety in C^n as an adjoint orbit inside the Lie algebra of n x n skew-Hermitian matrices. We use the orbit context to study the totally nonnegative part of a partial flag variety from an algebraic, geometric, and dynamical perspective. We classify gradient flows on adjoint orbits in various metrics which are compatible with total positivity. As applications, we show how the classical Toda flow fits into this framework, and prove that a new family of amplituhedra are homeomorphic to closed balls. This is joint work with Anthony Bloch. |
|
Speaker: Candida BowtellTitle: The n-queens problemVenue: VirtualAbstract: The n-queens problem asks how many ways there are to place n queens on an n x n chessboard so that no two queens can attack one another, and the toroidal n-queens problem asks the same question where the board is considered on the surface of a torus. Let Q(n) denote the number of n-queens configurations on the classical board and T(n) the number of toroidal n-queens configurations. The toroidal problem was first studied in 1918 by Pólya who showed that T(n)>0 if and only if n is not divisible by 2 or 3. Much more recently Luria showed that T(n) is at most ((1+o(1))ne^{-3})^n and conjectured equality when n is not divisible by 2 or 3. We… |