Organizers : Jeff Kahn, Bhargav Narayanan, and Abigail Raz
Date: November 27th, 2017
Speaker: Jozsef Skokan, London School of Economics
Title: The Multicolour Ramsey Number of a Long Odd Cycle.
Abstract: Click here
Date: November 20th, 2017
Speaker: Jozsef Beck, Rutgers
Title: Combinatorics and equidistribution of geodesics on flat surfaces
Abstract: A Cubeline means a geodesic on the cube surface. What can we say about the equidistribution of a concrete Cubeline with given slope, say slope square-root-2? What about the equidistribution of billiards in a nontrivial polyomino, say the L-shaped one (3 unit squares)? How does combinatorics enter the story? We attempt to answer these questions.
Date: November 13th, 2017
Speaker: Evita Nestoridi, Princeton
Title: Cutoff for random to random
Abstract: Random to random is a card shuffling model that was created to study strong stationary times. Although the mixing time of random to random has been known to be of order nlogn since 2002, cutoff had been an open question for many years, and a strong stationary time giving the correct order for the mixing time is still not known. In joint work with Megan Bernstein, we use the eigenvalues of the random to random card shuffling to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at 3/4(nlogn), answering a conjecture of Diaconis.
Date: November 6th, 2017
Speaker: Greta Panova, UPenn/IAS
Title: Hook formulas for skew shapes: combinatorics, asymptotics and beyond
Abstract: The celebrated hook-length formula of Frame, Robinson and Thrall from 1954 gives a product formula for the number of standard Young tableaux of straight shape. No such product formula exists for skew shapes. In 2014, Naruse announced a formula for skew shapes as a positive sum of products of hook-lengths using "excited diagrams" [ Ikeda-Naruse, Kreiman, Knutson-Miller-Yong] coming from Schubert calculus. We will show combinatorial and aglebraic proofs of this formula, leading to a bijection between SSYTs or reverse plane partitions of skew shape and certain integer arrays that gives two q-analogues of the formula. We will also show how these formulas can be proven via non-intersecting lattice paths interpretations, and show various applications connecting Dyck paths and alternating permutations. We show how excited diagrams give asymptotic results for the number of skew Standard Young Tableaux in various regimes of convergence for both partitions. We will also show a multivariate versions of the hook formula with consequences to exact product formulas for certain skew SYTs and lozenge tilings with multivariate weights. Joint work with A. Morales and I. Pak.
Date: October 30th, 2017
Speaker: Deepak Bal, Montclair State
Title: Monochromatic Components in Random Graphs
Abstract: We are concerned with the following Ramsey-type question: if the edges of a graph G are r-colored (not necessarily properly), what is the largest monochromatic component (or path, or cycle) which must appear? We may also ask for a cover or a partition of the vertex set of G by few monochromatic pieces. We discuss some recent work addressing these questions when G is a random graph. This is joint work with Michael Anastos and Louis DeBiasio.
Date: October 23rd, 2017
Speaker: Sophie Spirkl, Princeton
Title: The structure of triangle-free graphs with no induced six-vertex path
Abstract: I will talk about an explicit construction for triangle-free graphs that do not contain a six-vertex path as an induced subgraph. Examples include the 16-vertex Clebsch graph, and the graph that arises from a complete bipartite graph by subdividing every edge of a perfect matching exactly once. We show that every connected triangle-free graph with no six-vertex induced path can be obtained from an induced subgraph of one of these two by restricted homogeneous set and homogeneous pair operations. Joint work with Maria Chudnovsky, Paul Seymour, and Mingxian Zhong.
Date: October 16th, 2017
Speaker: Swastik Kopparty, Rutgers
Title: Approximate affine invariance and distance to polynomials
Abstract: Let F be a finite field, and let V be the set of functions from F to F computed by a univariate polynomial of degree at most d. It is easy to see that V is closed under affine transformations: i.e., if g(X) is in V, then so is h(X) = g(aX+b). V is also closed under taking linear combinations. We will study what happens to functions *not in V* when we apply random affine transformations and take random linear combinations of these. Our main result is that these operations increase the distance to V very quickly. Joint work with Eli Ben-Sasson and Shubhangi Saraf.
Date: October 9th, 2017
Speaker: Noah Stephens-Davidowitz, Princeton/IAS
Title: A Reverse Minkowski Theorem
Abstract: A classical problem in the geometry of numbers asks us to estimate how many lattice points lie in some ball around the origin. Minkowski’s celebrated theorem gives us a tight lower bound for this number that depends only on the determinant of the lattice. (One can think of the determinant as the limit of the density of lattice points inside large balls--i.e., the "global density" of the lattice. So, Minkowski’s theorem gives a lower bound on a lattice’s “local density” based on its “global density.”) We resolve a conjecture due to Dadush that gives a nearly tight converse to Minkowski’s theorem—an upper bound on the number of lattice points in a ball that depends only on the determinants of sublattices. This theorem has numerous applications, from complexity theory, to the geometry of numbers, to the behavior of Brownian motion on flat tori. Based on joint work with Oded Regev.
Date: October 2nd, 2017
Speaker: Chun-Hung Liu, Princeton
Title: The Erdos-Posa property
Abstract: For a family F of graphs, the packing number p of a graph G for F is the maximum size of a collection of pairwise disjoint subgraphs of G where each isomorphic to a member of F; the covering number c of G for F is the minimum size of a subset of vertices of G intersecting all subgraphs of G isomorphic to members of F. We say F has the Erdos-Posa property if there exists a function f such that c is at most f(p) for every graph G. Robertson and Seymour proved that if F is the set of H minors for some graph H, then F has the Erdos-Posa property if and only if H is planar. In this talk I will provide a complete but complicated characterization for the graphs H such that the set of H subdivisions has the Erdos-Posa property, and show that it is NP-hard to decide whether the input graph H has this property, so that the complication of the characterization is unlikely to be avoidable. This is joint work with Luke Postle and Paul Wollan and answers a question of Robertson and Seymour. Then I will discuss how to simplify the characterization by relaxing the conditions for having the Erdos-Posa property. In particular, I will show that for every graph H, the set of H subdivisions always has the Erdos-Posa property if we allow the packing to be half-integral. This statement easily implies a conjecture of Thomas.
Date: September 25th, 2017
Speaker: Ron Aharoni, Technion
Title: Cooperative colorings
Abstract: Given graphs $G_1, \ldots, G_k$ on the same vertex set $V$, a {\em cooperative coloring} is a choice of an independent set $I_j$ in each $G_j$, such that $\bigcup_{j \le k}I_j=V$. When all $G_i$s are the same graph, this is the familiar notion of $k$-coloring. What is the analogue of the fact that the coloring number of a graph $G$ is no larger than $\Delta(G)+1$? A sample result: three cycles have a cooperative coloring. Joint works with Berger, Chudnovsky, Holzman, Jiang and Spr\"ussel.
Date: September 18th, 2017
Speaker: Imre Leader, University of Cambridge
Title: Tiling with Arbitrary Tiles
Abstract: It is easy to tile the plane with dominoes (2x1 rectangles). It is also easy to tile the plane with trominoes (three 1x1 squares forming an L-shape). Of course, not every shape tiles the plane. What happens when we increase the number of dimensions from two to three, or beyond?
Date: September 11th, 2017
Speaker: Bhargav Narayanan, Rutgers
Title: Diffusion on Graphs
Abstract: 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!