Combinatorial Theory Seminar

Please note that the list below only shows forthcoming events, which may not include regular events that have not yet been entered for the forthcoming term. Please see the past events page for a list of all seminar series that the department has on offer.

Past events in this series
14 May 2019
14:30
Michael Chapman

Further Information: 

Expander graphs play a key role in modern mathematics and computer science. Random d-regular graphs are good expanders. Recent developments in PCP theory require families of graphs that are expanders both globally and locally. The meaning of “globally" is the usual one of expansion in graphs, and locally means that for every vertex the subgraph induced by its neighbors is also an expander graph. These requirements are significantly harder to satisfy and no good random model for such (bounded degree) graphs is presently known. In this talk we discuss two new combinatorial constructions of such graphs. We also say something about the limitations of such constructions and provide an Alon-Bopanna type bound for the (global) spectral gap of such a graph. In addition we discuss other notions of high dimensional expansion that our constructions do and do not satisfy, such as coboundary expansion, geometric overlap and mixing of the edge-triangle-edge random walk. This is a joint work with Nati Linial and Yuval Peled.
 

  • Combinatorial Theory Seminar
21 May 2019
14:30
Christoph Spiegel

Further Information: 

The Hales–Jewett Theorem states that any r–colouring of [m]^n contains a monochromatic combinatorial line if n is large enough. Shelah’s proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial line whose set of active coordinates is the union of at most r intervals. I will present some recent findings relating to this observation. This is joint work with Nina Kamcev.

  • Combinatorial Theory Seminar
Add to My Calendar