Organizers : Jeff Kahn, Bhargav Narayanan, and Corrine Yap
Date: April 18, 2022
Speaker: Eyal Lubetzky (Courant Inst. at NYU)
Title: Threshold for stacked triangulations
Abstract: The K_4^3 bootstrap percolation process is defined as follows: start with an initial set of "infected'' triangles Y, where each of the {n \choose 3} triangles with vertices [n]={1,2,…,n} appears independently with probability p; then repeatedly add to it a new triangle {a,b,c} if there exists a tetrahedron in which this is the only missing face (i.e. if for some x the 3 triangles {a,b,x},{a,x,c},{x,b,c} are already infected). Let Y_\infty denoted the final state of the process. What is the critical probability p(n) so that Y_\infty would typically contain a specific triangle {1,2,3}? How many triangles would Y_\infty typically have below that threshold? When would Y_\infty typically contain all triangles?
Equivalently, a stacked triangulation of a triangle with labels in [n], a.k.a. an Appolonian Network, is one obtained by repeatedly subdividing a triangle {a,b,c} into 3 new triangles {a,b,x},{a,x,c},{x,b,c} via a label x in [n]. The above questions would amount to asking, e.g., about the critical probability so that the random simplicial complex Y_2(n,p) would typically contain the faces of a stacked triangulation of every triangle {a,b,c}.
We consider these questions for a general dimension d \geq 2, and our results identify the critical threshold p_c for stacked triangulations: we show that p_c is asymptotically (C(d) n)^(-1/d), where the constant C(d) is the growth rate of the Fuss--Catalan numbers of order d. The proof hinges on a second moment argument in the supercritical regime, and on Kalai's algebraic shifting in the subcritical regime.
Joint work with Yuval Peled.
Date: March 28, 2022
Speaker: Simi Haber (Bar-Ilan)
Title: Logical and natural properties of random graphs
Abstract: A graph property is first order expressible if it can be written as a formal sentence using the universal and existential quantifiers with variables ranging over the vertices of the graph, the usual connectives and the relations = and ~, where x~y stands for adjacency.
First order expressible properties have been studied using random models, that is, by looking on the possible behavior of first order properties given a probability space of graphs, e.g., G(n,p). For example, it is known that in G(n,1/2) every first order expressible graph property has limiting probability zero or one, a phenomenon called a 0-1 law. Since many natural graph properties are not first order expressible, there has been an effort to extend first order logic while maintaining a 0-1 law. Along the years a number of very attractive and surprising results have been obtained. I will present some of these results and two tools enabling a new taxonomy of graph properties.
No background in logic is assumed. Based on joint works with Saharon Shelah.
Date: March 21, 2022
Speaker: Leonardo Coregliano (IAS)
Title: Ramsey's Theorem in the countable and the approximate Erdős-Hajnal property
Abstract: The celebrated Erdős-Hajnal Conjecture says that in any proper hereditary class of finite graphs we are guaranteed to have a clique or anti-clique of size $n^c$, which is a much better bound than the logarithmic size that is provided by Ramsey's Theorem in general. On the other hand, in uncountable cardinalities, the model-theoretic property of stability guarantees a uniform set much larger than the bound provided by the Erdős-Rado Theorem in general. However, in the case of countable structures balanced between these two, all structures seem to behave in the same way since the infinite version of Ramsey's Theorem already yields a uniform set of the maximum possible cardinality.
By instead considering a different notion of large sets, namely, that of positive upper density and ignoring negligible errors, we show that the same phenomenon happens in the countable: a countable graph has a large almost clique or a large almost anti-clique if and only if it has a large almost stable set. Similarly, in the countable we can consider a variant Erdős-Hajnal property: we say that a hereditary class of finite graphs $C$ has the approximate Erdős-Hajnal property (AEHP) if every countable graph whose finite induced subgraphs are all in $C$ must contain a large almost clique or a large almost anti-clique. Surprisingly, AEHP has a simple characterization as precisely those classes that avoid some recursive blow-up of the 4-cycle.
In this talk, I will explain how these problems are reduced to problems for limits of dense graph sequences (graphons) and show how the corresponding graphon problems have very clean combinatorial proofs. No background knowledge in model theory or in the theory of graphons will be required.
This talk is based on joint work with Maryanthe Malliaris.
Date: March 7, 2022
Speaker: Colin Defant (Princeton)
Title: Triangular-Grid Billiards and Plabic Graphs
Abstract: Given a polygon P in the triangular grid, we define a rigid billiards system by allowing beams of light to bounce around inside of P so that each beam always meets the midpoint of a unit-length boundary segment at a 60-degree angle. This basic setup seems ripe for investigation; we will focus on some natural extremal questions concerning how large P must be relative to the number c of light-beam trajectories. Our main theorem states that the (appropriately normalized) area of P is at least 6c-6 and that the (appropriately normalized) perimeter of P is at least (7c-3)/2. This talk will sketch some of the geometric aspects of the proof of this result. We will also briefly discuss how one can reformulate these inequalities in the language of Postnikov's plabic graphs. This talk is based on joint work with Pakawut Jiradilok.
Date: February 28, 2022
Speaker: Boris Bukh (Carnegie Mellon)
Title: Sharp density bounds on the finite field Kakeya problem
Abstract: A set is Kakeya if it contains a line in every direction. We prove that every Kakeya set in the n-space over F_q has at least 2^{-n+1}*q^n elements. This is sharp up to the lower-order terms. Joint work with Ting-Wei Chao.
Date: February 21, 2022
Speaker: Corrine Yap (Rutgers)
Title: Multicolored hypergraph Ramsey numbers
Abstract: A central open problem in Ramsey theory is to determine the behavior of r_3(t), the minimum n such that any 2-coloring of the complete 3-uniform hypergraph on n vertices contains a monochromatic complete subgraph on t vertices. In the 1960's, Erdős, Hajnal, and Rado showed that r_3(t) is bounded between exponential and double-exponential in t, but the correct behavior remains unknown. Erdős and Hajnal surprisingly showed that the double-exponential bound is correct if we use four colors instead of two. This raises the question: how does the number of colors influence the growth of the Ramsey number? Generalizing a result of Conlon, Fox, and Rödl, we construct a family of hypergraphs with arbitrarily large tower gaps between the 2-color and q-color Ramsey numbers. We utilize results analogous to the Erdős-Hajnal stepping-up lemma, for Ramsey numbers where we relax the "monochromatic" condition to "spanning few colors." Joint work with Quentin Dubroff, António Girão, and Eoin Hurley,
Date: January 5, 2022 at 11:30AM via Zoom
Speaker: Fan Wei (Princeton)
Title: Regularity lemma: Discrete and Continuous Perspectives
Abstract: Szemerédi's regularity lemma is a game-changer in extremal combinatorics and provides a global perspective to study large combinatorial objects. It has connections to number theory, discrete geometry, and theoretical computer science. One of its classical applications, the removal lemma, is the essence for many property testing problems, an active field in theoretical computer science. Unfortunately, the bound on the sample size from the regularity method typically is either not explicit or is enormous. For testing natural permutation properties, we show one can avoid the regularity proof and yield a tester with polynomial sample size. For graphs, we prove a stronger, "L_infty'' version of the graph removal lemma, where we conjecture that the essence of this new removal lemma for cliques is indeed the regularity-type proof. The analytic interpretation of the regularity lemma also plays an important role in graph limits, a recently developed powerful theory in studying graphs from a continuous perspective. Based on graph limits, we developed a method combining with both analytic and spectral methods, to answer and make advances towards some famous conjectures on a common theme in extremal combinatorics: when does randomness give nearly optimal bounds? These works are based on joint works with Jacob Fox, Dan Kral', Jonathan Noel, Sergey Norin, and Jan Volec.