Organizers : Jeff Kahn, Bhargav Narayanan, and Quentin Dubroff
Date: November 27, 2023
Speaker: Michail Sarantis (CMU)
Title: On the zeroes of hypergraph independence polynomials
Abstract: We prove that the multivariate independence polynomial of any hypergraph of maximum degree $\Delta$ has no zeroes on the complex polydisc of radius $\sim\frac{1}{e\Delta}$, centered at the origin. Up to logarithmic factors in $\Delta$, the result is optimal, even for graphs with all edge sizes greater than $2$. As a corollary, we get an FPTAS for approximating the independence polynomial in this region of the complex plane.
We furthermore prove the corresponding radius for the $k$-uniform linear hypertrees is $\Omega(\Delta^{-1/(k-1)})$, a significant discrepancy from the graph case.
Joint work with David Galvin, Gwen McKinley, Will Perkins and Prasad Tetali.
Date: November 20, 2023
Speaker: Quentin Dubroff (Rutgers)
Title: On the H-space of a random graph
Abstract: The edge space of a graph G is the vector space of functions from E(G) to F_2 (the two-element field) with members naturally identified with subgraphs of G, and the H-space is the subspace spanned by copies of the graph H. We are interested in understanding when the random graph is likely to have the most generic possible H-space. For example, if H is a triangle, we want to know when it is likely that every cycle is in the H-space (i.e. when the triangle space is likely the same as the cycle space). We give an essentially complete answer for strictly 2-balanced graphs, showing that a simple necessary condition in fact characterizes when the H-space is as generic as possible. Joint with Jeff Kahn.
Date: November 13, 2023
Speaker: Matthew Junge (CUNY)
Title: The frog model on trees
Abstract: The frog model describes random activation and spread. Think combustion or an epidemic. I have studied these dynamics on d-ary trees for ten years. I will discuss our progress and what remains.
Date: November 6, 2023
Speaker: Dmitrii Zakharov (MIT)
Title: Erdos-Ginzburg-Ziv problem in large dimension
Abstract: For a given prime p and a dimension n, the Erdos-Ginzburg-Ziv problem asks about the smallest number s such that any subset in F_p^n of size s contains p vectors with zero sum. We drastically improve previous upper bounds in the case when p is fixed and n is large. In particular, we overcome a certain 'multicolor' barrier of the slice rank method for this problem which appears in many applications of the slice rank polynomial method. The proof combines the slice rank method with a generalization of the Balog-Szemeredi-Gowers Theorem due to Borenstein and Croot.
Joint work with Lisa Sauermann.
Date: October 30, 2023
Speaker: Charles Kenney (Rutgers)
Title: Asymptotics for Palette Sparsification
Abstract: Let G be a graph on n vertices with maximum degree D. If we sample a list of (1+o(1)) ln(n) colors uniformly at random from {1,2,...,D+1}, independently for each vertex of G, then with high probability there is a proper coloring of G from these lists. This confirms a conjecture that Assadi expressed at this seminar in 2021. We overview the proof, discuss connections to other problems, and conclude with a couple conjectures of our own.
Joint work with Jeff Kahn.
Date: October 23, 2023
Speaker: Hung-Hsun Hans Yu (Princeton) and Ting-Wei Chao (CMU)
Title: Tight Bound and Structural Theorem for Joints
Abstract: The joints problem asks to determine the maximum number of joints N lines can form, where a joint in a d-dimensional space is a point on d lines in linearly independent directions. Recently, we determined the maximum exactly for k choose d-1 lines in d-dimensional space, namely k choose d. What is more important is that we are able to prove a structural result determining all optimal configurations, and this is the first success of the polynomial method in this direction. It turns out that our result implies a conjecture of Bollobás and Eccles as an immediate corollary regarding a generalization of the Kruskal–Katona theorem. In this talk, we will talk about the connection to that conjecture and also give a high-level overview of the key ideas.
Date: October 9, 2023
Speaker: Cosmin Pohoata (Emory)
Title: A new upper bound for the Heilbronn triangle problem
Abstract: We discuss a new upper bound for the Heilbronn triangle problem, showing that for sufficiently large $n$ in every configuration of $n$ points chosen inside a unit square there exists a triangle of area less than $n^{-8/7-1/2000}$. This is joint work with Alex Cohen and Dmitrii Zakharov.
Date: October 2, 2023
Speaker: Prateek Vishwakarma (PIMS)
Title: Inequalities for totally nonnegative matrices: Gantmacher--Krein, Karlin, and Laplace
Abstract: A real linear combination of products of minors which is nonnegative over all totally nonnegative (TN) matrices is called a determinantal inequality for these matrices. It is referred to as multiplicative when it compares two collections of products of minors and additive otherwise. Set theoretic operations preserving the class of TN matrices naturally translate into operations preserving determinantal inequalities in this class. We introduce index-row (and index-column) operations that act directly on all determinantal inequalities for TN matrices, and yield further inequalities for these matrices. These operations assist in revealing novel additive inequalities for TN matrices embedded in the classical identities due to Laplace [Mem. Acad. Sciences Paris 1772] and Karlin (1968). In particular, for any square TN matrix $A,$ these derived inequalities generalize -- to every $i^{\mbox{th}}$ row of $A$ and $j^{\mbox{th}}$ column of ${\rm adj} A$ -- the classical Gantmacher--Krein fluctuating inequalities (1941) for $i=j=1.$ Furthermore, our index-row/column operations reveal additional undiscovered fluctuating inequalities for TN matrices.
The introduced index-row/column operations naturally birth an algorithm that can detect certain determinantal expressions that do not form an inequality for TN matrices. However, the algorithm completely characterizes the multiplicative inequalities comparing products of pairs of minors. Moreover, the underlying index-row/column operations add that these inequalities are offshoots of certain "complementary/higher'' ones. These novel results seem very natural, and in addition thoroughly describe and enrich the classification of these multiplicative inequalities due to Fallat--Gekhtman--Johnson [Adv. Appl. Math. 2003] and later Skandera [J. Algebraic Comb. 2004] (and revisited by Rhoades--Skandera [Ann. Comb. 2005, J. Algebra 2006]).
This is joint work with Shaun M. Fallat.
Date: September 25, 2023
Speaker: Noah Kravitz (Princeton)
Title: The structure of Lonely Runner spectra
Abstract: Dirichlet's Theorem says that for any real number t, there is some natural number v in {1,2,...,n} such that tv is within 1/(n+1) of an integer. The Lonely Runner Conjecture of Wills and Cusick asserts that the constant 1/(n+1) in this theorem cannot be improved by replacing {1,2,...,n} with a different set of n nonzero real numbers. The conjecture, although now more than 50 years old, remains wide open for n larger than 6. In this talk I will describe the "Lonely Runner spectra" that arise when one considers the "inverse problem" for the Lonely Runner Conjecture, and I will explain the (a priori surprising) "hierarchical" relations among these spectra. Based on joint work with Vikram Giri.
Date: September 18, 2023
Speaker: Nicholas Sieger (UCSD)
Title: A Random Graph Model for Clustering Graphs
Abstract: We introduce a random graph model for clustering graphs with a given degree sequence. Unlike many previous random graph models, we incorporate clustering effects into the model. We show that random clustering graphs can construct graphs with a power-law expected degree sequence, small diameter, and any desired clustering coefficient. Our results follow from a general theorem on subgraph counts which may be of independent interest.