Autumn 2017

September 7: Dustin Mixon (OSU)

Title: A semidefinite relaxation of k-means clustering


Recently, Awasthi et al proved that a semidefinite relaxation of the
k-means clustering problem is tight under a particular data model
called the stochastic ball model. This result exhibits two
shortcomings: (1) naive solvers of the semidefinite program are
computationally slow, and (2) the stochastic ball model prevents
outliers that occur, for example, in the Gaussian mixture model. This
talk will cover recent work that tackles each of these shortcomings.
First, I will discuss a new type of algorithm (introduced by Bandeira)
that combines fast non-convex solvers with the optimality certificates
provided by convex relaxations. Second, I will discuss how to analyze
the semidefinite relaxation under the Gaussian mixture model. In this
case, outliers in the data obstruct tightness in the relaxation, and
so fundamentally different techniques are required. Several open
problems will be posed throughout. This is joint work with Takayuki
Iguchi and Jesse Peterson (AFIT), as well as Soledad Villar and Rachel
Ward (UT Austin).


September 14: Elliot Paquette (OSU) Joint with ergodic theory seminar

Title: Distributional lattices in Riemannian symmetric spaces 


A Riemannian symmetric space X is a Riemannian manifold in which it is possible to reflect all geodesics through a point by an isometry of the space.  A lattice in such a space can be considered as a discrete subgroup G of isometries so that a Borel fundamental domain of the quotient space G/X has finite Riemannian volume.  Lattices mirror the structure of the ambient space in many ways: for example, X is amenable if and only if the the ambient space is amenable.  We introduce the notion of a distributional lattice, generalizing the notion of lattice, by considering measures on discrete subsets of X having finite Voronoi cells and certain distributional invariance properties.  Non-lattice distributional lattices exist in any Riemannian symmetric space: the Voronoi tessellation of a stationary Poisson point process is an example.  With an appropriate notion of amenability, the amenability of a distributional lattice is equivalent to the amenability of the ambient space.  We give some open problems related to these processes and some pretty pictures.



September 21: (Rosh Hashana)



September 28: Andrew Newman (OSU)

Title: Small simplicial complexes with prescribed torsion


By Kalai’s generalization of Cayley’s formula, it is known that for every dimension d \geq 2, there exists a constant k_d > 0 so that for every n, there is a simplicial complex X on n vertices so that the torsion subgroup of H_{d- 1}(X) has order at least \exp(k_d n^d). In this talk, I use the probabilistic method to affirmatively answer an inverse question. That is, I prove that for any d \geq 2, there is a constant C_d so that for any abelian group G there is a simplicial complex X on at most C_d \sqrt[d] {\log |G|} vertices so that the torsion subgroup of H_{d - 1}(X) is isomorphic to G.


October 5: 




October 12 (Fall break)



October 19: Bhargav Narayanan (Rutgers)

Title: Diffusion on Graphs


Diffusion on a graph G is a cellular automaton describing how integer labels on the vertices of G evolve. We view the label of a vertex as the number of chips at that vertex, and at each step, each vertex simultaneously sends one chip to each of its neighbours with fewer chips. What can we say about the trajectories of various initial configurations in this process? Here’s an amuse bouche: this firing rule may generate negative labels when started from a completely positive initial configuration, so it is not clear, a priori, if one must even have periodic behaviour necessarily!


October 26: Hannah Alpert (OSU)

Title: Discrete configuration spaces of squares and hexagons


What’s the diameter of the configuration space of several disjoint unit disks in a large square?  As the square gets bigger and the number of disks increases to preserve the density, how fast does the diameter increase?  We can answer a discrete version of this question where the square is replaced by a grid graph and the disks are replaced by distinct vertices.  Then we can ask the same question for arbitrary graphs.


November 2: Eric Foxall (U Alberta)

Title: The compulsive gambler with allowances


We consider a process in which a finite set of n agents continually receive a 1 dollar allowance and gamble their fortunes, all in, with one another at a constant rate. This is a variation on the existing compulsive gambler process; in that process, initial fortunes are prescribed and no further allowances are given out. For our process, we find that after some time the distribution of wealth settles into a pattern in which most people have only a few dollars, a few are very wealthy, and a single person possesses most of the cash currently present in the population. In addition, eventually the only way to attain first rank is by winning a bet against the current champion. Moreover, if agents play a fair game, i.e., the probability of winning a bet is proportional to the players’ fortunes, the title of champion is assumed by every player infinitely often, although it changes less and less frequently as time goes on. Finally, by examining the process from both the perspective of typical fortune, and that of large fortune, we can go one step further and obtain two distinct limiting processes as n \to \infty, with each one admitting a detailed description of its dynamics.


November 9:  (No seminar)





November 16: (Double seminar — 10:20–11:15 CH240) Shu Kanazawa (Tohoku University)

Title: Asymptotic behavior of lifetime sums of Betti numbers for random simplicial complex processes


A random simplicial complex process is a family of random simplicial complexes. The Linial–Meshulam complex process and the clique complex process were studied by Hiraoka and Shirai. They showed the exact order of the expected lifetime sum of the Betti numbers for the Linial–Meshulam complex process as the number of vertices goes to infinity. In this talk, I define more general random simplicial complex processes, including the above two models, and report that the exact order of the expected lifetime sum for them was revealed. The key to proving the results is a quantitative generalization of the Cohomology vanishing theorem. This is joint work with Masanori Hino.


November 16: (Double seminar — 11:20–12:15 CH240) Mustazee Rahman (MIT)

Title: On largest eigenvalues of bounded degree graphs


The classical Alon-Boppana Theorem gives a sharp lower bound on the
second largest eigenvalue of a regular graph. Obtaining such bounds for non-regular
graphs is more complicated. I will explain some combinatorial and topological
ideas that allows for Alon-Boppana type bounds for large, bounded degree graphs.
These bounds also apply to unimodular networks, which are a stochastic generalization
of finite graphs. In fact, the stochastic generalization plays a central role in deducing
such bounds for finite graphs.


November 23 (Thanksgiving)



November 30: Hans Parshall (OSU)

Title:  Distance sets in finite fields

Abstract: The Falconer distance problem and its variants are concerned with quantifying the following statement: sets of large Hausdorff dimension determine many distances.  We will describe a simple finite field model which avoids some technicalities while retaining connections with the original setup.  Our goal will be to highlight recent progress, including joint work with Alex Iosevich, on locating point configurations with prescribed distance structure in this model setting.  In particular, we obtain results that go beyond what is known in the Euclidean setting, leading to some natural conjectures.


December 7: Kyle Luh (Harvard)

Title: Embedding Large Graphs in Random Graphs



Embedding Large Graphs in Random Graphs

SpeakerKyle Luh (Harvard University)

Abstract: In this talk, we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let Δ5, ε>0 and let H be a graph on (1ε)n vertices and with maximum degree Δ. We show that a random graph Gn,p with high probability contains a copy of H, provided that p(n1log1/Δn)2/(Δ+1). Our assumption on p is optimal up to the polylog factor. We will also discuss recent progress on the “universality” problem, which entails finding the threshold for all graphs of degree at most Δ to appear in Gn,p simultaneously.