Seminar time: Thursdays 10:20-11:15am.
Location: Mathematics Tower (MW) 154.
January 25: Nathaniel Idein Harms (EPFL)
Title: Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
Abstract: We prove a characterization of the structural conditions on matrices of sign-rank 3 and unit disk graphs (UDGs) which permit \emph{constant-cost} public-coin randomized communication protocols. Therefore, under these conditions, these graphs also admit implicit representations.
The sign-rank of a matrix M in ${-1,+1}^{N \times N}$ is the smallest rank of a matrix $R$ such that $M_{i,j} = \sign(R_{i,j})$ for all $i,j \in [N]$; equivalently, it is the smallest dimension $d$ in which $M$ can be represented as a point-halfspace incidence matrix with halfspaces through the origin, and it is essentially equivalent to the {unbounded-error communication complexity. Matrices of sign-rank 3 can achieve the maximum possible bounded-error randomized communication complexity $\Theta(\log N)$, and meanwhile the existence of implicit representations for graphs of bounded sign-rank (including UDGs, which have sign-rank 4) has been open since at least 2003. We prove that matrices of sign-rank 3, and UDGs, have constant randomized communication complexity if and only if they do not encode arbitrarily large instances of the Greater-Than communication problem, or, equivalently, if they do not contain large half-graphs as semi-induced subgraphs. This also establishes the existence of implicit representations for these graphs under the same conditions.
February 8: JE Paguyo (McMaster University)
Title: Central limit theorem for crossings in randomly embedded graphs
Abstract: Let G be a graph on n vertices. A random embedding of G is the graph obtained from the graph isomorphism induced by a random permutation π of [n]. In this talk, we present a central limit theorem for the number of crossings, X, in a random embedding of a graph G whose vertices are in convex position. Our proof uses Stein’s method, which allows us to establish a convergence rate for our distributional approximation in terms of graph properties of G and the variance of X. In particular, we apply our result to random chord diagrams and give the first quantitative proof of the central limit theorem for their number of crossings, a result first proved by Flajolet and Noy using analytic combinatorics and subsequently by Feray using weighted dependency graphs. This talk is based on joint work with Octavio Arizmendi (CIMAT) and Santiago Arenas-Velilla (University of G\”{o}ttingen).
February 29 (Arnold Classic – Hotels are scarce): The OSU Colloquium is on random matrices! Time: 4:15pm-5:15pm in EA170.
Title: Combinatorics of integrable lattice models from the point of view of representation theory of p-adic groups
Abstract: Integrable lattice models is a fascinating device. On one hand, they are purely combinatorial; the weighted sums over lattice states — partition functions — have rich structure. On another hand, integrability condition guarantees that these partition functions will satisfy various recursive relations which makes it possible to compute them exactly. I will show how the same structure appears in representation theory of p-adic groups, where matrix coefficients have both combinatorial and recursive relations. I will show that colored fermionic lattice models correspond to the Whittaker functions, and colored bosonic lattice models correspond to the Spherical functions.
March 14: Spring Break (no talks)
March 21: Cesar Cuenca (Ohio State University)
Title: The Symplectic Schur Process
Abstract: We introduce a new symmetric function that plays the role of skew Schur function for symplectic groups and that leads to the construction of the “Symplectic Schur Process”. This new probability ensemble shares many desirable properties with the classical Schur process of Okounkov-Reshetikhin and we will explain some of them, including the property of having determinantal correlation functions. Finally, we discuss some applications and limits. This talk is based on joint work with Matteo Mucciconi.
March 28: Zihao Fang (Ohio State University)
Title: Cutoff for Random Walks on Contingency Tables
Abstract: Contingency tables are matrices with fixed row and column sums. It was of particular interest in math and statistics to sample contingency tables at random for various purposes, and one would like to know how efficient a sampling algorithm can be. We studied the Diaconis-Gangolli random walk as a Markov chain Monte Carlo model and observed cutoff phenomena, a sharp transition from almost deterministic to almost random in the context of mixing time. We gave cutoff time for the random walks on both 1*n and n*n contingency tables, and we generalized our method to show cutoff for a family of random walks on the torus (Z/qZ)^n. This is a joint work with Andrew Heeszel (OSU).
April 4: Karl Liechty (DePaul University)
Title: Boundary statistics for the six-vertex model with DWBC
Abstract: The six-vertex model presented on a square lattice is an important solvable model in 2d statistical mechanics. For domain wall boundary conditions, I will discuss the statistics near the boundary of a state as the size of the lattice goes to infinity. Results will be presented throughout the phase diagram of the model. This is joint work with Vadim Gorin.
April 11: David Sivakoff (Ohio State University)
Title: Supercritical neighborhood growth with one-dimensional nucleation
Abstract:
Supercritical neighborhood growth rules in two dimensions are classified by the existence of finite configurations that lead to unbounded growth. Bollobás, Smith and Uzzell proved that when the initially occupied set is random with density p, the first occupation time of the origin is polynomial in (1/p) as p → 0. We take a closer look at supercritical growth rules with +-shaped neighborhoods. These rules exhibit one-dimensional nucleation in the sense that lines begin to grow before forming two-dimensional nuclei. In many cases, we show that the first occupation time is (1/p)^(γ+o(1)) for an explicit constant γ depending on the rule. In one case, we establish a logarithmic correction to the polynomial passage time due to a growth trajectory that resembles a branching process, while in other cases the first occupation time is of pure polynomial order (1/p)^γ .
Based on joint work with Daniel Blanquicett, Janko Gravner and Luke Wilson.
April 18: Kyle Binder (Ohio State University)
Title: Higher Tor Groups of Matroids
Abstract: The Chow group of a loopless matroid is an important invariant which has been used to resolve important log-concavity results in matroid theory. Topologically, these Chow groups are the Chow groups of toric varieties associated to the Bergman fan of a matroid; algebraically, they are quotients of the Stanley—Reisner ring of the Bergman fan by the action of an ambient torus. In this talk we will generalize the Chow group of a matroid to what we call the Higher Tor Groups of a matroid. Topologically, these are the homology groups of the corresponding toric variety; algebraically, they are the Tor groups of the Stanley—Reisner ring. We will describe some of the basic properties of these Tor groups and compute the Betti numbers in the case of uniform matroids.