Spring 2018 | Combinatorics and Probability Seminar

January 25: Érika Roldán Roa (OSU and CIMAT)

Title: Polyominoes with maximally many holes

Abstract: A polyomino is a finite collection of squares with vertices in the
lattice $\mathbb{Z}^2$ and with a connected interior. Given a number $n\ge 1$ ,
what is the maximum number $f(n)$ of holes that a polyomino
with $n$ squares can enclose? We find $f(n)$ exactly for infinitely
many $n$ . The main construction is a recursive sequence that leads to
fractal-like polyominoes.

February 1: (no seminar)

Title: TBD

Abstract:

February 8: Sam Davanloo Tajbakhsh (OSU Industrial and Systems Engineering)

Title: Fitting Gaussian random fields to large data sets

Abstract:

Fitting a Gaussian Random Field (GRF) model to spatial data by maximizing the likelihood function suffers from nonconvexity. The problem is aggravated for anisotropic GRFs where the number of covariance function parameters increases with the domain dimension. In this work, we propose a new two-step GRF fitting procedure when the process is second-order stationary. First, a convex likelihood problem regularized with a weighted $\ell_1$ norm, utilizing the available distance information between observation locations, is solved to get a sparse precision (inverse covariance) matrix. Second, the GRF covariance function parameters are estimated by solving a least-square problem. Theoretical error bounds for the proposed estimator are provided; moreover, convergence of the estimator is shown as the number of samples per location increases.

February 15: TBD

Title: TBD

Abstract:

February 22: TBD

Title: TBD

Abstract:

March 1: TBD

Title: TBD

Abstract:

March 8: David Sivakoff (OSU)

Title: Polluted Bootstrap Percolation in Three Dimensions

Abstract: In r-neighbor bootstrap percolation, the vertices of Z^d are initially occupied independently with probability p and empty otherwise. Occupied vertices remain occupied forever, and empty vertices iteratively become occupied when they have at least r occupied neighbors. It is a classic result of van Enter (r=d=2) and Schonmann (d>2 and r between 2 and d) that every vertex in Z^d eventually becomes occupied for any initial density p>0. In the polluted bootstrap percolation model, vertices of Z^d are initially closed with probability q, occupied with probability p and empty otherwise.

The r-neighbor bootstrap rule is the same, but now closed vertices act as obstacles, and remain closed forever. This model was introduced 20 years ago by Gravner and McDonald, who studied the case d=r=2 and proved a phase transition exists for this model as p and q tend to 0. We prove a similar phase transition occurs when d=r=3, and we identify the polynomial scaling between p and q at which this transition occurs for the modified bootstrap percolation model. For one direction, our proof relies on duality methods in Lipschitz percolation to find a blocking structure that prevents occupation of the origin. The other direction follows from a rescaling argument, and the recent results of Holroyd and Gravner for d>r=2. This talk will be based on joint work with Holroyd and Gravner.

March 15: (Spring break)

Title: TBD

Abstract:

March 22: Gabor Lippner (Northeastern University) (moved to March 22)

Title: Measurable Graph Theory

Abstract: “Graphings” are a natural generalization of finite graphs on probability measure spaces. These objects arise naturally as limits of finite graphs, as well as from the study of invariant random processes on discrete groups.

Measurable graph theory studies graphings from the perspective of classical graph theory. It lies at the crossroads of ergodic theory and discrete mathematics. I will explain how to generalize standard notions (matchings, chromatic number, expansion, etc) to graphings and survey recent results on the surprising behavior of these notions in the measurable setting.

March 29: Oanh Nguyen (Princeton)

Title: Roots of random functions

Abstract: In this talk, we will discuss recent progress in the study of random functions with a focus on a general framework to prove some universality properties of the roots of random functions. We illustrate how to apply this framework to some popular models of random functions such as random Kac polynomials, random trigonometric polynomials, random Taylor series, and so on.

April 5: TBD

Title: TBD

Abstract:

April 12: TBD

Title: TBD

Abstract:

April 19: TBD

Title: TBD

Abstract:

April 26: Matthew Junge (Duke University)

Title: Chase-Escape

Abstract: Imagine mussels and barnacles spreading across the surface of a rock. Barnacles move to adjacent unfilled spots. Mussels too, but they can only attach to barnacles. Barnacles with a mussel on top no longer spread. What conditions on the rock geometry (i.e. graph) and spreading rates (i.e. exponential clocks) ensure that barnacles can survive? Chase-escape can be formalized in terms of competing Eden growth models; one on top of the other. New, tantalizing open problems will be presented. Joint work with Rick Durrett and Si Tang.

June 12: Philip Matchett Wood (University of Wisconsin)

Title: Limiting eigenvalue distribution for the non-backtracking matrix of an Erdos-Renyi random graph

Abstract: A non-backtracking random walk on a graph is a directed walk with the constraint that the last edge crossed may not be immediately crossed again in the opposite direction. This talk will give a precise description of the eigenvalues of the adjacency matrix for the non-backtracking walk when the underlying graph is an Erdos-Renyi random graph on $n$ vertices, where edges present independently with probability $p$ . We allow $p$ to be constant or decreasing with $n$ , so long as $p \sqrt{n}$

tends to infinity. The key ideas in the proof are partial derandomization, applying the Tao-Vu Replacement Principle in a novel context, and showing that partial derandomization may be interpreted as a perturbation, allowing one to apply the Bauer-Fike Theorem.

Joint work with Ke Wang at HKUST (Hong Kong University of Science and Technology).