Organizers : Jeff Kahn, Bhargav Narayanan, and Corrine Yap
Date: November 28, 2022
Speaker: Fernando Granha Jeronimo (IAS)
Title: Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
Abstract: Expander graphs are fundamental objects in theoretical computer science and mathematics. They have numerous applications in diverse fields such as algorithm design, complexity theory, coding theory, pseudorandomness, group theory, etc.
In this talk, we will describe an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, $d \leq 1/\lambda^{2+o(1)}$) trade-off between (any desired) spectral expansion $\lambda$ and degree $d$. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost Ramanujan expanders from arbitrary expanders.
This transformation preserves structural properties of the original graph, and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost Ramanujan expanding generators. Similarly, one can obtain almost optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc., from existing (suboptimal) constructions of such objects.
Our results generalize Ta-Shma's technique in his breakthrough paper [STOC 2017] used to obtain explicit almost optimal binary codes. Specifically, our spectral amplification extends Ta-Shma's analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way.
Joint work with: Tushant Mittal, Sourya Roy and Avi Wigderson
Date: November 21, 2022
Speaker: Cosmin Pohoata (IAS)
Title: Convex polytopes from fewer points
Abstract: Finding the smallest integer N=ES_d(n) such that in every configuration of N points in R^d in general position there exist n points in convex position is one of the most classical problems in extremal combinatorics, known as the Erdős-Szekeres problem. In 1935, Erdős and Szekeres famously conjectured that ES_2(n)=2^{n−2}+1 holds, which was nearly settled by Suk in 2016, who showed that ES_2(n)≤2^{n+o(n)}. We discuss a recent proof that ES_d(n)=2^{o(n)} holds for all d≥3. Joint work with Dmitrii Zakharov.
Date: November 14, 2022
Speaker: Noah Kravitz (Princeton)
Title: Logarithmically larger deletion codes
Abstract: The deletion distance between two binary words of length n is the smallest k such that the words have a common subsequence of length n-k. A set of binary words of length n is called a k-deletion code if every pair of distinct words has deletion distance greater than k, and it is natural to ask for the maximum size of such a code. A classical result of Levenshtein shows that (for fixed k) this quantity is at least \Omega_k(2^n/n^{2k}) and at most O_k(2^n/n^k). We improve the lower bound to \Omega_k(2^n logn/n^{2k}) by studying triangles in the associated "deletion graph". Joint work with Noga Alon, Gabriela Bourla, Ben Graham, and Xiaoyu He.
Date: October 31, 2022
Speaker: Noam Lifshitz (IAS)
Title: Product free sets in the alternating group
Abstract: A subset of a group is said to be product free if it does not contain the product of two elements in it. We consider how large can a product free subset of $A_n$ be?
In the talk we will completely solve the problem by determining the largest product free subset of $A_n$.
Our proof combines a representation theoretic argument due to Gowers, with an analytic tool called hypercontractivity for global functions. We also make use of a dichotomy between structure and a pseudorandomness notion of functions over the symmetric group known as globalness.
Based on a joint work with Peter Keevash and Dor Minzer
Date: October 24, 2022
Speaker: Swee Hong Chan (Rutgers)
Title: Log-concavity and cross product conjecture in order theory
Abstract: The study of log-concave inequalities has played a central role in the study of the order theory. One such inequality is Stanley's inequality, which asserts the log-concavity of the sequence $(N_k)$ of the number of linear extensions of partial order for which the rank of a fixed element x is equal to k. In this talk we will discuss various generalizations of these results together with related open problems. This talk is joint work with Igor Pak and Greta Panova, and is intended for the general audience.
Date: October 17, 2022
Speaker: Adam Sheffer (Baruch College, CUNY)
Title: A structural Szemerédi–Trotter theorem for cartesian products
Abstract: The Szemerédi–Trotter theorem can be considered as the fundamental theorem of geometric incidences. This combinatorial theorem has an unusually wide variety of applications, and is used in combinatorics, theoretical computer science, harmonic analysis, number theory, model theory, and more. Surprisingly, hardly anything is known about the structural question - characterizing the cases where the theorem is tight. We present such structural results for the case of cartesian products. This is a basic survey talk and does not require previous knowledge of the field.
Joint work with Olivine Silier. This is also a shameless advertisement of the speaker's new book "Polynomial Methods and Incidence Theory."
Date: October 10, 2022
Speaker: Himanshu Gupta (Delaware)
Title: The least Euclidean distortion constant of a distance-regular graph
Abstract: Embedding graphs into Euclidean spaces with least distortion is a topic well-studied in mathematics and computer science. Despite this research, there are just a few graphs for which the precise least distortion and a least distortion embedding is known. In 2008, Vallentin studied this problem for distance-regular graphs and obtained a lower bound for the least distortion of a distance-regular graph. In addition, he showed that this bound is tight for Hamming and Johnson graphs as well as strongly regular graphs and conjectured that his bound is always tight for distance-regular graphs. In this talk, we provide several counterexamples to this conjecture with diameter 4 and larger, but we also prove the conjecture for several families of distance-regular graphs. This is joint work with Sebastian M. Cioabă (University of Delaware), Ferdinand Ihringer (Ghent University), and Hirotake Kurihara (Yamaguchi University).
Date: October 3, 2022
Speaker: Louis DeBiasio (Miami University)
Title: Quantitative problems in infinite graph Ramsey theory
Abstract: Two well-studied problems in Ramsey theory are (1) given a graph G on n vertices, what is the smallest integer N such that there is a monochromatic copy of G in every 2-coloring of a complete graph on N vertices, and (2) given a directed acyclic graph D on n vertices, what is the smallest integer N such that there is a copy of D in every tournament on N vertices. Note that for both problems, the family of trees has turned out to be an interesting special case, each with a long history and a relatively recent resolution (for sufficiently large n).
We consider quantitative analogues of these problems in the infinite setting; that is, (1) given a countably infinite graph G what is the supremum of the set of real numbers r such that in every 2-coloring of the complete graph on the natural numbers there is a monochromatic copy of G whose vertex set has upper/lower density at least r, and (2) given a countably infinite directed acyclic graph D what is the supremum of the set of real numbers r such that in every tournament on the natural numbers there is a copy of D whose vertex set has upper/lower density at least r? As it relates to these problems, I will discuss two very surprising results.
Based on joint work with Alistair Benford, Jan Corsten, and Paul McKenney.
Date: September 26, 2022
Speaker: Sam Spiro (Rutgers)
Title: The Random Turán Problem for Bipartite Graphs
Abstract: Let G_{n,p} denote the random n-vertex graph obtained by including each edge independently and with probability p. Given a graph F, let ex(G_{n,p},F) denote the size of a largest F-free subgraph of G_{n,p}. When F is non-bipartite, the asymptotic behavior of ex(G_{n,p},F) was determined in breakthrough work independently by Conlon-Gowers and by Schacht. Much less is known when F is bipartite. In this talk we will survey the known bounds on ex(G_{n,p},F) when F is bipartite, as well as the general techniques used for these problems. We will also discuss the random Turán problem for r-partite r-uniform hypergraphs as time permits.
Date: September 19, 2022
Speaker: Michael Simkin (Harvard)
Title: The number of n-queens configurations
Abstract: The n-queens problem is to determine Q(n), the number of ways to place n mutually non-threatening queens on an n x n board. We show that there exists a constant 1.94 < a < 1.9449 such that Q(n) = ((1 + o(1))ne^(-a))^n. The constant a is characterized as the solution to a convex optimization problem in P([-1/2,1/2]^2), the space of Borel probability measures on the square.
The chief innovation is the introduction of limit objects for n-queens configurations, which we call "queenons". These from a convex set in P([-1/2,1/2]^2). We define an entropy function that counts the number of n-queens configurations approximating a given queenon. The upper bound uses the entropy method of Radhakrishnan and Linial--Luria. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queenon and whose entropy matches that found in the upper bound. The enumeration of n-queens configurations is then obtained by maximizing the (concave) entropy function over the space of queenons.
Based on arXiv:2107.13460
Date: September 12, 2022
Speaker: Jinyoung Park (Stanford)
Title: Thresholds
Abstract: Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Jeff Kahn and Gil Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will present recent progress on this topic. Based on joint work with Huy Tuan Pham.