Seminar time: Thursdays 10:20-11:15am.
September 23: Francisco Martinez Figueroa (Ohio State)
Title: Chromatic number of generalized Borsuk Graphs.
Abstract: The Borsuk graph is the graph with vertex set the sphere S^d, and edges {x,y} whenever x and y are epsilon-almost antipodal. It is well known that when epsilon is small, its chromatic number is d+2, which follows from the topology of S^2 via Borsuk-Ulam’s Theorem. Given a finite group G acting freely over a compact space X via isometries, we define the G-Borsuk graph to be the graph with vertex set X and edges {x,y} whenever there exists a non-identity g in G such that d(x,gy)<epsilon. The chromatic number of such graph is determined by the topology of X. In this talk we’ll show some upper bounds for this chromatic number depending only on |G| and dim(X). Our bounds are tight when dim(X)=1, and we exhibit some tight results in dimensions 2 and 3 when G=Z_m, for small values of m. We will also discuss random G-Borsuk graphs, which are finite induced subgraphs by choosing n i.i.d. uniform vertices on X. For these, we exhibit a tight threshold for epsilon (up to a constant) such that a.a.s. the chromatic number of the random subgraph coincides with that of the whole G-Borsuk graph. This is joint work in progress with Matthew Kahle.
September 30: Miklos Racz (Princeton)
Title: Correlated stochastic block models: graph matching and community recovery
October 7: Nicholas Cook (Duke)
Title: Large deviations and regularity method for sparse random hypergraphs
Abstract: The “infamous upper tail” problem for subgraph counts in Erdős–Rényi graphs has received considerable attention since it was popularized by Janson and Rucinski, and has connections with questions in graph limit theory and statistical physics. I will survey work in this area and discuss a new approach for the more general setting of hypergraphs, based on an extension of the regularity method to sparse hypergraphs. In particular, we develop a sparse counting lemma and decomposition theorem for tensors under a novel class of norms that generalize the matrix cut norm. Time permitting, I will discuss applications to the analysis of exponential random graph models. Based on joint work with Amir Dembo and Huy Tuan Pham.
October 14: Fall Break (No seminar).
October 21: Pooya Hatami (CSE, Ohio State University)
Title: Dimension-free bounds in Communication Complexity and Idempotents of Schur Multipliers
Abstract: We discuss whether dimension-free relations exist between various communication and query measures and various norms associated with Boolean matrices and functions. In other words, we ask, whether it is possible to obtain inequalities that bound one parameter solely as a function of another parameter, without any dependence on the dimensions of the matrix.
Dimension-free bounds are also closely related to structural results, where one seeks to find local or global structural properties of Boolean matrices and functions that have low complexity. We discuss such theorems for several communication and query complexity measures as well as various matrix and operator norms. In several other cases, we show that such bounds do not exist.
We propose several open problems that in addition to applications in complexity theory, are central to the characterization of the idempotents of the algebra of Schur multipliers, and could lead to new extensions of Cohen’s celebrated idempotent theorem regarding the Fourier algebra.
Based on joint work with Lianna Hambardzumyan (McGill University) and Hamed Hatami (McGill University)
October 28: Boris Hanin (Princeton University)
Title: Random Neural Networks at Finite Width and Large Depth
Abstract: Deep neural networks are often considered to be complicated “black boxes,” for which a full systematic analysis is not only out of reach but also impossible. In this talk, which is based in part on joint work with Sho Yaida and Daniel Adam Roberts, I will make the opposite claim. Namely, that deep neural networks with random weights and biases (i.e. networks at the start of training) are solvable models. Our approach applies to networks at finite width n and large depth L, the regime in which they are used in practice. A key point will be the emergence of a notion of “criticality,” which involves a finetuning of model parameters (weight and bias variances). At criticality, neural networks are particularly well-behaved but still exhibit a tension between large values for n and L, with large values of n tending to make neural networks more like Gaussian processes and large values of L amplifying higher cumulants. Our analysis at initialization has a number of consequences for networks during and after training, which I will discuss if time permits.
November 4: Yeor Hafuta (Ohio State University)
- A Berry-Esseen theorem (optimal rates in the Central limit theorem);
- Correction terms of order 1 in the CLT;
- Higher order correction terms in the CLT, commonly known as Edgeworth expansions. For Markov chains on compact Riemannian manifolds or for functional with decaying supremum norms we obtain optimal conditions for the Edgeworth expansions of an arbitrary order r.
- We will also discuss the “universality of Edgewoth polynomials”.
November 11: Veterans day (No seminar)
November 18: Yufei Zhao (MIT, in-person talk)
Title: Second eigenvalue multiplicity of bounded degree graphsAbstract: As a key ingredient in our work on equiangular lines (which I will discuss in the colloquium), we prove (with Jiang, Tidor, Yao, & Zhang) the following theorem: every connected bounded degree n-vertex graph has adjacency matrix second eigenvalue multiplicity O(n/loglog n). While the spectral gap is intensely studied due to connections to expansion, much less is known about eigenvalue multiplicities. This is perhaps the first such result about general classes of graphs. I will present the proof of this result. I will also present a recent construction (with Haiman, Schilkraut, & Zhang) proving a (n/log n)^{1/2} lower bound. I will also present another construction giving ≳ n/loglog n eigenvalues very close to the 2nd eigenvalue, thereby demonstrating a barrier in the above method.
December 2: Kristina Wicke (Ohio State)
Title: On the Maximum Agreement Subtree Conjecture for Balanced Trees
Abstract: Leaf-labeled trees, also called phylogenetic trees, are used to represent inferred evolu- tionary histories of sets of species. However, due to different data sets and methods that are used to infer such histories, even phylogenetic trees that have been reconstructed for the same set of species often differ. To summarize the information that two or more phylogenetic trees have in common, so-called maximum agreement subtrees (MASTs) have become a popular tool. In this talk, I will introduce the concept of MASTs and give some background on their computation and combinatorial properties. I will then turn to phylogenetic trees of a particular shape, so-called balanced phylogenetic trees, and introduce a conjecture by Martin and Thatte (2013) stating that two balanced phylogenetic trees on n leaves have a MAST with at least n^2 leaves. The remainder of the talk will then be devoted to disproving this conjecture for infinitely many values of n via a family of counterexamples.
(joint work with Magnus Bordewich, Simone Linz, Megan Owen, Katherine St. John, and Charles Semple)
December 9: Chris Janjigian (Purdue)