Spring 2017 | Combinatorics and Probability Seminar

Title: Combinatorial aspects of complicated configuration spaces

Abstract: The topology of the configuration space of n points in the plane is well understood. We introduce and overview a well known poset (or regular CW complex) which serves as a combinatorial model for configuration space. This is sometimes called the Salvetti complex, and earlier versions appeared implicitly in work of Fox-Neuworth, Deligne, and others.

Bob MacPherson and I recently generalized this cell complex to give a combinatorial model for the configuration space of n non overlapping disks of unit diameter in a strip of width w. We use this to compute the asymptotics of the Betti numbers as n tends to infinity.

The focus of the talk will be on the combinatorial aspects of the work, particularly the structure of the poset itself and time permitting, the essence of a discrete Morse theory argument that gives upper bounds on the Betti numbers.

January 19

Title:

January 26 Ramon van Handel (Princeton)

Title: Chaining, interpolation, and convexity

Abstract: A significant achievement of modern probability theory is the development of sharp connections between the boundedness of random processes and the geometry of the underlying index set. In particular, the generic chaining method of Talagrand provides in principle a sharp understanding of the suprema of Gaussian processes. The multiscale geometric structure that arises in this method is however notoriously difficult to control in any given situation. In this talk, I will exhibit a surprisingly simple but very general geometric construction, inspired by real interpolation of Banach spaces, that is readily amenable to explicit computations and that explains the behavior of Gaussian processes in various interesting situations where classical entropy methods are known to fail.

February 2

Title:

February 9 Tom Needham (OSU)

Title: Random triangles and polygons in the plane

Abstract: We consider some basic questions in geometric probability regarding planar polygons. First we determine the probability that a random triangle is obtuse, a question first raised by Lewis Carroll. The probability measure on triangle space comes from identifying it with a compact Riemannian manifold with a transitive isometry group (namely, the standard 2-sphere!). More generally, a probability measure on polygon space is obtained by a natural correspondence between the space of similarity classes of planar n-gons and the Grassmann manifold of 2-planes in real n-space which was first proposed by Allen Knutson and Jean-Claude Hausmann. Several aspects of the geometry of the Grassmannian correspond to properties of polygons; for example, convex polygons are identified with the positive Grassmannian. We use this fact to give a new answer to Sylvester’s four-point problem. This is joint work with Jason Cantarella, Clayton Shonkwiler and Gavin Stewart.

February 16 Aurel Stan (OSU)

Title:

February 23 Eric Katz (OSU)

Title: The Higher Cycle Operations on Graphs

Abstract: The cycle pairing on leafless graphs takes a pair of cycles to their oriented intersection. While purely combinatorial, it arose in Picard-Lefschetz theory, a branch of both algebraic geometry and analysis, as a way of studying monodromy of families of algebraic curves, variations of Hodge structures, and asymptotics of period integrals. The cycle pairing, once properly packaged, determines a graph up to two moves by the graph Torelli theorem of Caporaso and Viviani, which makes use of a classical theorem of Whitney. In this talk, we introduce the higher cycle operations, a mildly non-Abelian extension which reflects not just the edges in a cycle but their relative ordering. We relate this cycle pairing to asymptotics of iterated integrals and variations of Hodge structures on the fundamental group. We discuss the recent proof of the higher graph Torelli theorem with Raymond Cheng which is an analogue of the unipotent Torelli theorem of Hain and Pulte.

March 2 Matthew Junge (Duke)

Title: The bullet problem with discrete speeds

Abstract: Bullets are fired along the real line each second with independent uniformly random speeds from [0,1]. When two bullets collide they mutually annihilate. The still open bullet problem asks if the first bullet is never annihilated with positive probability. We establish a phase transition for survival of the first bullet in the variant where speeds are uniformly sampled from a discrete set. Joint with Brittany Dygert, Christoph Kinzel, Annie Raymond, Erik Slivken, and Jennifer Zhu.

March 9 Lutz Warnke (Georgia Tech)

Title: Upper tails for arithmetic progressions in random subsets

Abstract: We study the upper tail $\mathbb{P}(X \ge (1+\epsilon) \mathbb{E} X)$ for random variables such as the number of arithmetic progressions of a given length in a random subset of $[n]= \{ 1,2,\ldots,n \}$ . For arithmetic progressions and Schur triples we establish exponentially small bounds for $\mathbb{P}(X \ge (1+\epsilon) \mathbb{E} X)$ which are best possible up to constant factors in the exponent (improving results of Janson and Rucinski). The proofs are phrased in the language of random induced subhypergraphs, and exploit certain structural properties of the underlying k-uniform hypergraphs (encoding arithmetic progressions or Schur triples).

March 16 (Spring Break)

March 23 Parisa Fatheddin (AFIT)

Title: Asymptotic Behavior of a Class of SPDEs

Abstract: We consider a class of stochastic partial differential equations (SPDEs) that can be used to represent two commonly studied population models: super-Brownian motion and Fleming-Viot Process. After introducing these models, we establish their asymptotic limits by means of Large and Moderate deviations, Central Limit Theorem and Law of the Iterated Logarithm. These results were achieved by joint work with Prof. P. Sundar and Prof. Jie Xiong.

March 30 Hanbaek Lyu (OSU)

Title: Phase transition in a random soliton cellular automaton

Abstract: In 1990, Takahashi and Satsuma proposed a $1+1$ dimensional cellular automaton of filter type called the soliton cellular automaton, also known as the box-ball system. The model describes $N$ solitary waves interacting like particles, which converges to a state where the $N$ solitons are non-interacting. A time-invariant Young diagram can be constructed from the initial state, whose columns correspond to length of solitons.

We consider the model with a random initial configuration. We give multiple constructions of the time-invariant Young diagram in terms of familiar objects like birth-and-death chains and Galton-Watson forests. Using these ideas, we establish limit theorems showing that if the first $n$ boxes are occupied independently with probability $p\in(0,1)$ , then the number of solitons is of order $n$ for all $p$ , and the length of the longest soliton is of order $\log n$ for $p<1/2$ , order $\sqrt{n}$ for $p=1/2$ , and order $n$ for $p>1/2$ . Additionally, we uncover a condensation phenomenon in the supercritical regime: For each fixed $j\geq 1$ , the top $j$ soliton lengths have the same order as the longest for $p\leq 1/2$ , whereas all solitons except the longest one have order at most $\log n$ for $p>1/2$ .

This is a joint work with Lionel Levine and John Pike.

April 6 Puck Rombach (UCLA)

Title: Guessing numbers of graphs

Abstract: The guessing number problem is the following. What is the largest family of colorings of a graph such that the color of each vertex is determined by its neighborhood? This problem is equivalent to finding protocols for network coding. I will discuss results on general graphs, and recent asymptotic results for odd cycles, which is joint work with Ross Atkins and Fiona Skerman.

April 13

Shankar Bhamidi will be giving the Statistics Seminar at 3:00PM. This will likely interest many of the regular attendees:

Statistics seminar

Shankar Bhamidi

April 20 Wesley Pegden (CMU)

Title: Diffusion limited aggregation in the Boolean lattice.

Abstract:

In the Diffusion Limited Aggregation (DLA) process on on $\mathbb{Z}^2$ ,
particles aggregate to cluster initialized as a singleton containing the
origin, by arrivals on random walks “from infinity”. The scaling limit
of the result, empirically, is a fractal with dimension strictly less
than $2$ . Very little has been shown rigorously about the process, however.

Motivated by interest in the impact of high dimensionality on this
kind of process, We study an analogous model in the Boolean lattice. We
will see that precise and surprising characteristics of this model can
be proved rigorously.

April 27 Shaked Koplewitz (Yale)

Title: Surjectivity and cokernels of random matrices, and the Cohen Lenstra Heuristics.

Abstract: In this talk, we discuss the probability that random integer matrices are surjective and, more generally, the distribution of their cokernels. We begin with the simplest case – matrices over finite fields, p-adics, and the profinite completion of the integers, where the cokernels are well-known and simple to calculate. We show that a wide variety of other random matrix models also have similar cokernel distributions, following the general philosophy that, when generating random groups, you should generally expect them to follow Cohen-Lenstra heuristics. As such, we can extend the results for p-adic matrices to more general models.

May 4 Arnab Sen (Minnesota)

Title: Majority dynamics on the infinite 3-regular tree

Abstract: The majority dynamics on the infinite 3-regular tree can be described as follows. Each vertex of the tree has an i.i.d. Poisson clock attached to it, and when the clock of a vertex rings, the vertex looks at the spins of its three neighbors and flips its spin, if necessary, to come into agreement with majority of its neighbors. The initial spins of the vertices are taken to be i.i.d. Bernoulli random variables with parameter p. In this talk, we will discuss a couple of new results regarding this model. In particular, we will show that the limiting proportion of ‘plus’ spins in the tree is continuous with respect to the initial bias p. A key tool in our argument is the mass transport principle. The talk is based on an ongoing work with M. Damron.