Organizers : Jeff Kahn, Bhargav Narayanan, Swee Hong Chan, and Natalya Ter-Saakov
Date: December 9, 2024 at 2:00pm
Speaker: Luis Ferroni (IAS)
Title: Chow functions for partially ordered sets
Abstract: In a landmark paper in 1992, Stanley developed the foundations of what is now known as the Kazhdan--Lusztig--Stanley (KLS) theory. To each kernel in a graded poset, he associates special functions called KLS polynomials. This unifies and puts a common ground for i) the Kazhdan--Lusztig polynomial of a Bruhat interval in a Coxeter group, ii) the toric g-polynomial of a polytope, iii) the Kazhdan-Lusztig polynomial of a matroid. In this talk I will introduce a new family of functions, called Chow functions, that encode various deep cohomological aspects of the combinatorial objects named before. In the three settings mentioned before, the Chow function describes i) a descent-like statistic enumerator for paths in the Bruhat graph, ii) the enumeration of chains of faces of the polytope, iii) the Hilbert series of the matroid Chow ring. This is joint work with Jacob P. Matherne and Lorenzo Vecchi.
Date: December 2, 2024 at 2:00pm
Speaker: Jonathan Tidor (Stanford)
Title: Ramsey and Turán numbers of sparse hypergraphs
Abstract: The degeneracy of a graph is a measure of sparseness that gives important information about its Turán- and Ramsey-type properties. I will talk about the extension of this problem to hypergraphs. The typical notion of hypergraph degeneracy does not give any information about either the Ramsey or Turán numbers of hypergraphs; instead we define a notion called skeletal degeneracy. We prove the hypergraph generalization of the Burr--Erdős conjecture: hypergraphs of bounded skeletal degeneracy have Ramsey number linear in their number of vertices. Furthermore, we give good bounds on the Turán exponent of partite hypergraphs in terms of their skeletal degeneracy.
Based on joint work with Jacob Fox, Maya Sankar, Michael Simkin, and Yunkun Zhou.
Date: November 25, 2024 at 2:00pm
Speaker: Mehtaab Sawhney (Columbia)
Title: On Perfectly Friendly Bisections of Random Graphs
Abstract: We prove that if G~G(n,1/2) then with high probability there exists a equipartition such that each vertex has more neighbors across the partition than within their own part. The proof involves tools ranging from isoperimetric results on vertex transitive graphs to switchings to degree enumeration formulas and the second moment method.
Based on joint work with Dor Minzer and Ashwin Sah.
Date: November 18, 2024 at 2:00pm
Speaker: Sam Spiro (Rutgers)
Title: Extremal Problems for Random Objects
Abstract: Broadly speaking, extremal combinatorics studies how ``large'' combinatorial objects can be, such as determining the maximum number of edges that a graph with a given set of properties can have. In contrast, the field of probabilistic combinatorics studies properties of random discrete objects, such as random graphs and random permutations. In this talk, we study several problems at the intersection of these areas. In particular, we consider the maximum expected score one can obtain in a certain card guessing game, as well as the problem of finding large $F$-free subgraphs of random graphs.
Date: November 11, 2024 at 2:00pm
Speaker: Hanbaek Lyu (UW Madison)
Title: Large random matrices with given margins
Abstract: We study large random matrices with i.i.d. entries conditioned to have prescribed row and column sums (margin). This problem has rich connections to relative entropy minimization, Schr\"{o}dinger bridge, the enumeration of contingency tables, and random graphs with given degree sequences. We show that such margin-constrained random matrix is sharply concentrated around a certain deterministic matrix, which we call the typical table. Typical tables have dual characterizations: (1) the expectation of the random matrix ensemble with minimum relative entropy from the base model constrained to have the expected target margin, and (2) the expectation of the maximum likelihood model obtained by rank-one exponential tilting of the base model. The structure of the typical table is dictated by two dual variables, which give the maximum likelihood estimates of the tilting parameters. Based on these results, for a sequence of "tame" margins that converges in $L^{1}$ to a limiting continuum margin as the size of the matrix diverges, we show that the sequence of margin-constrained random matrices converges in cut norm to a limiting kernel, which is the $L^{2}$-limit of the corresponding rescaled typical tables. The rate of convergence is controlled by how fast the margins converge in $L^{1}$. We also propose a Sinkhorn-type algorithm for computing typical tables, which speicalizes to the classical Sinkhorn algorithm for the Poisson base measure. We derive several new results for random contingency tables from our general framework.
Based on a joint work with Sumit Mukherjee.
Date: November 4, 2024 at 2:00pm
Speaker: Jinyoung Park (NYU)
Title: Lipschitz functions on expanders
Abstract: We will discuss the typical behavior of M-Lipschitz functions on d-regular expander graphs, where an M-Lipschitz function means any two adjacent vertices admit integer values differ by at most M. While it is easy to see that the maximum possible height of an M-Lipschitz function on an n-vertex expander graph is about C*M*log n, where C depends (only) on d and the expansion of the given graph, it was shown by Peled, Samotij, and Yehudayoff (2012) that a uniformly chosen random M-Lipschitz function has height at most C'*M*loglog n with high probability, showing that the typical height of an M-Lipschitz function is much smaller than the extreme case. Peled-Samotij-Yehudayoff's result holds under the condition that, roughly, any "not-so-large" vertex sets expand by about M*log(dM). We will show that the same result holds under a much weaker condition assuming that d is large enough. This is joint work with Robert Krueger and Lina Li.
Date: October 28, 2024 at 2:00pm
Speaker: Yuval Wigderson (ETH Zürich)
Title: Spectral bounds on the independence number
Abstract: Spectral graph theory provides us with a wide array of surprising results which relate graph-theoretic parameters to linear-algebraic parameters of associated matrices. Among the most well-known and useful of these is Hoffman's ratio bound, which gives an upper bound on the independence number of a graph in terms of its eigenvalues.
A closely related result is Cvetković's inertia bound, another inequality relating the independence number and the eigenvalues of a graph. Despite its similarity to the ratio bound, the inertia bound is much less well-understood—until a few years ago, it was unknown whether this simple inequality is always an equality! In this talk, I will survey what is known about these two bounds, and will present a powerful new approach to answering such questions.
Joint work with Matthew Kwan.
Date: October 21, 2024 at 2:00pm
Speaker: Alan Yan (Harvard)
Title: Cutoff for the Biased Random Transposition Shuffle
Abstract: The biased random transposition shuffle is a natural generalization of the classical random transposition shuffle studied by Diaconis and Shahshahani. In this variation, rather than selecting two cards uniformly at random and swapping them, two cards are still chosen, but with a higher probability of selecting from one half of the deck over the other. By diagonalizing the transition matrix of the biased random transposition shuffle, we show that it exhibits total variation cutoff with window N. We also show that the limiting distribution of the number of fixed cards near the cutoff time is Poisson. Compared to the case of random transpositions, our proofs require new tools from the representation theory of the symmetric group and the combinatorics of hive models. Joint work with Evita Nestoridi.
Date: October 7, 2024 at 2:00pm
Speaker: Tung H, Nguyen (Princeton)
Title: Induced subdivisions and polylogarithmic chromatic number
Abstract: We discuss a proof that for every graph H, every n-vertex graph with no induced subdivision of H and with bounded clique number has chromatic number at most polylog(n). This extends a result of Fox and Pach that similar polylogarithmic bounds hold for all string graphs, and is close to optimal as there are triangle-free n-vertex string graphs with chromatic number at least loglog n. Joint work with Alex Scott and Paul Seymour.
Date: September 30, 2024 at 2:00pm
Speaker: Matt Larson (Princeton/IAS)
Title: Signed permutohedra
Abstract: Postnikov has shown that generalized permutohedra, polytopes whose edges are parallel to vectors of the form e_i - e_j, have remarkable formulas for their volumes and lattice point counts. Additionally, generalized permutohedra can be written as signed Minkowski sums of simplices. I will discuss a generalization of these results to signed generalized permutohedra, polytopes whose edges are parallel to vectors of the form e_i - e_j, e_i + e_j, or e_i. Joint work with Chris Eur, Alex Fink, and Hunter Spink.
Date: September 23, 2024 at 2:00pm
Speaker: Nikita Gladkov (UCLA)
Title: Inequalities for connectivity events in Bernoulli percolation
Abstract: Events such as "two vertices are connected by an open path" naturally emerge in Bernoulli percolation. In this talk, we will examine the dependencies between these events for various vertex pairs and derive key FKG-type inequalities governing their probabilities.
Date: September 16, 2024
Speaker: Imre Leader (Cambridge)
Title: Turan densities for daisies and hypercubes
Abstract: The Turan problem for hypercubes asks: how few vertices of the n-dimensional cube can we take so that they meet every d-dimensional subcube? A longstanding conjecture states that the best one can do (asymptotically) is 1/(d+1) of all vertices, by taking every (d+1)th layer of the cube. In this talk we will explain the connection to Turan questions for 'daisy’ hypergraphs, and present a disproof of the conjecture. This is joint work with David Ellis and Maria Ivan.