Organizers : Jeff Kahn, Bhargav Narayanan, and Quentin Dubroff
Date: May 1, 2023
Speaker: Justin Gilmer (Google)
Title: A constant lower bound for Frankl's union-closed sets conjecture.
Abstract: A finite set system is union-closed if for every pair of sets in the system their union is also in the system. Frankl in 1979 conjectured that for any such system there exists an element which is contained in ½ of the sets in that system (the only exception being the family containing just the empty set). In this talk I will discuss how a simple insight regarding the contrapositive of Frankl's conjecture eventually led to the discovery of an information theoretic approach on the problem and a proof of the first constant lower bound.
Date: April 24, 2023
Speaker: Shivam Nadimpalli (Columbia University)
Title: Influences for Convex Sets
Abstract: We introduce a new notion of influence—called "convex influence"—for convex sets over Gaussian space which has many of the properties of influences of Boolean functions over the hypercube. Our main results for convex influences give Gaussian space analogues of many important results on influences for monotone Boolean functions, including the Kahn-Kalai-Linial theorem, a sharp threshold theorem of Kalai, and a quantitative correlation inequality due to Talagrand. Time permitting, we will also discuss a recent application of convex influences to the problem of testing convex truncation, a natural algorithmic task in high-dimensional statistics.
Based on joint works with Anindya De and Rocco A. Servedio.
Date: April 17, 2023
Speaker: Jacob Richey (University of British Columbia)
Title: Entropy and letter density for shifts of finite type
Abstract: Given an iid binary string conditioned to not have 1001 as a substring, how many 1s and 0s does it typically have? More generally, given a finite set of 'forbidden' patterns over a finite alphabet, we can study the associated shift of finite type, i.e. all strings avoiding the forbidden set. Which forbidden sets are the most/least restrictive, and which give a higher/lower density of 1s? I will present old and new results, and many unanswered questions. Combinatorics, probability, and symbolic dynamics will each play a role.
Date: April 10, 2023
Speaker: Rose McCarty (Princeton)
Title: 𝛿-boundedness
Abstract: There are many classical constructions of graphs with arbitrarily large minimum degree and without big bicliques. A class of graphs is 𝛿-bounded if, essentially, it avoids all such constructions. We give an overview of this area and discuss a very recent theorem which is joint work with Xiying Du. The theorem says that for any such class, the minimum degree 𝛿 is at most triply exponential in the size of the largest balanced biclique.
Date: April 3, 2023
Speaker: Yuwen Wang (University of Innsbruck)
Title: Expected hitting times on finite graphs
Abstract: Given two vertices a and b on a finite graph, the hitting time is how long a simple random walk starting at a reaches b. We give asymptotic estimates for expected hitting times for a large class of lattice-like graphs. Joint work with Laurent Saloff-Coste.
Date: March 27, 2023
Speaker: Benjamin Gunby (Rutgers)
Title: Antichain Codes
Abstract: Let S be a subset of the Boolean cube that is both an antichain and a distance-r code. How large can S be? I will discuss the solution to this problem and its connections with combinatorial proofs of anticoncentration theorems. Based on joint work with Xiaoyu He, Bhargav Narayanan, and Sam Spiro.
Date: March 6, 2023
Speaker: Amzi Jeffs (Carnegie Mellon)
Title: Enumerating interval graphs and d-representable complexes
Abstract: How many different ways can we arrange n convex sets in R^d? One answer is provided by counting the number of d-representable complexes on vertex set [n]. We show that there are exp(Theta(n^d log n)) many such complexes, and provide bounds on the constants involved. As a consequence, we show that d-representable complexes comprise a vanishingly small fraction of d-collapsible complexes. In the case d=1 our results are more precise, and improve the previous best estimate for the number of interval graphs. These results are joint work with Boris Bukh.
Date: February 27, 2023
Speaker: Will Perkins (Georgia Tech)
Title: On the evolution of triangle-free graphs in the ordered regime
Abstract: Erdős-Kleitman-Rothschild proved that the number of triangle-free graphs on n vertices is asymptotic to the number of bipartite graphs; or in other words, a typical triangle-free graph is a random subgraph of a nearly balanced complete bipartite graph. Osthus-Promel-Taraz extended this result to much lower densities: when m >(\sqrt{3}/4 +eps) n^{3/2} \sqrt{\log n}, a typical triangle-free graph with m edges is a random subgraph of size m from a nearly balanced complete bipartite graph (and this no longer holds below this threshold).
What do typical triangle-free graphs at sparser densities look like and how many of them are there? We consider what we call the "ordered" regime, in which typical triangle-free graphs are not bipartite but do align closely with a nearly balanced bipartition. In this regime we prove asymptotic formulas for the number of triangle-free graphs and give a precise probabilistic description of their structure. This leads to further results such as determining the threshold at which typical triangle-free graphs are q-colorable for q >=3, determining the threshold for the emergence of a giant component in the complement of a max-cut, and many others.
This is joint work with Matthew Jenssen and Aditya Potukuchi.
Date: February 20, 2023
Speaker: Or Zamir (Princeton/IAS)
Title: Random k-out subgraphs
Abstract: Each vertex of an arbitrary simple graph on n vertices chooses k random incident edges. What is the expected number of edges in the original graph that connect different connected components of the sampled subgraph? We prove that the answer is O(n/k), when k ≥ c log n, for some large enough c. We conjecture that the same holds for smaller values of k, possibly for any k ≥ 2. Such a result is best possible for any k ≥ 2.
We give applications of this sampling lemma for models of distributed algorithms.
Based on joint work with Jacob Holm, Valeria King, Mikkel Thorup and Uri Zwick.
Date: February 13, 2023
Speaker: Matija Bucic (Princeton/IAS)
Title: Unit and distinct distances in typical norms
Abstract: Erdős' unit distance problem and Erdős' distinct distances problem are among the most classical and well-known open problems in all of discrete mathematics. They ask for the maximum number of unit distances, or the minimum number of distinct distances, respectively, determined by n points in the Euclidean plane. The question of what happens in these problems if one considers normed spaces other than Euclidean space has been raised in the 1980s by Ulam and Erdős and attracted a lot of attention over the years. We give an essentially tight answer to both questions for almost all norms on R^d, in a certain Baire categoric sense.
Our results settle, in a strong and somewhat surprising form, problems and conjectures of Brass, of Matousek, and of Brass--Moser--Pach. The proofs combine combinatorial, probabilistic and geometric ideas with tools from Linear Algebra, Topology and Algebraic Geometry.
Joint work with: Noga Alon and Lisa Sauermann.
Date: February 6, 2023
Speaker: Domagoj Bradač (ETH Zurich)
Title: The Turán number of the grid
Abstract: For a positive integer t, let F_t denote the graph of the t by t grid. Motivated by a 50-year-old conjecture of Erdős about Turán numbers of r-degenerate graphs, we prove that there exists a constant C=C(t) such that ex(n,F_t) < Cn^{3/2}. This bound is tight up to the value of C. Our original proof of this result relied on an intricate argument using the tensor power trick. In this talk I will present a simplified version of the proof. Based on joint work with Oliver Janzer, Benny Sudakov and István Tomon.
Date: January 30, 2023
Speaker: Ron Peled (Tel Aviv University)
Title: Site percolation on planar graphs and circle packings
Abstract: Color each vertex of an infinite graph blue with probability p and red with probability 1-p, independently among vertices. For which values of p is there an infinite connected component of blue vertices? The talk will focus on this classical percolation problem for the class of planar graphs.
Recently, Itai Benjamini made several conjectures in this context, relating the percolation problem to the behavior of simple random walk on the graph. We will explain how partial answers to Benjamini's conjectures may be obtained using the theory of circle packings. Among the results is the fact that the critical percolation probability admits a universal lower bound for the class of recurrent plane triangulations.
Open problems will be emphasized. No previous knowledge on percolation or circle packings will be assumed.