Georgia Institute of Technology College of Sciences

We will describe a twisted action of the symmetric group on the polynomial ring in n variables and use it to define a twisted version of Schubert polynomials. These twisted Schubert polynomials are known to be related to the Chern-Schwartz-MacPherson classes of Schubert cells in the flag variety. Using properties of skew divided difference operators, we will show that these twisted Schubert polynomials are monomial positive and give a combinatorial formula for their coefficients.

We provide a framework for testing the possibility of large cascades in random networks. Our results extend previous studies on contagion in random graphs to inhomogeneous directed graphs with a given degree sequence and arbitrary distribution of weights. This allows us to study systemic risk in financial networks, where we introduce a criterion for the resilience of a large network to the failure (insolvency) of a small group of institutions and quantify how contagion amplifies small shocks to the network.

The importance of analyzing big data and in particular very large networks has shown that the traditional notion of a fast algorithm, one that runs in polynomial time, is often insufficient. This is where property testing comes in, whose goal is to very quickly distinguish between objects that satisfy a certain property from those that are ε-far from satisfying that property. It turns out to be closely related to major developments in combinatorics, number theory, discrete geometry, and theoretical computer science. Some of the most general results in this area give "constant query complexity" algorithms, which means the amount of information it looks at is independent of the input size. These results are proved using regularity lemmas or graph limits. Unfortunately, typically the proofs come with no explicit bound for the query complexity, or enormous bounds, of tower-type or worse, as a function of 1/ε, making them impractical. We show by entirely new methods that for permutations, such general results still hold with query complexity only polynomial in 1/ε. We also prove stronger results for graphs through the study of new metrics. These are joint works with Jacob Fox.

Since Erdős–Rényi introduced random graphs in 1959, two closely related models for random graphs have been extensively studied. In the G(n,m) model, a graph is chosen uniformly at random from the collection of all graphs that have n vertices and m edges. In the G(n,p) model, a graph is constructed by connecting each pair of two vertices randomly. Each edge is included in the graph G(n,p) with probability p independently of all other edges. Researchers have studied when the random graph G(n,m) (or G(n,p), resp.) satisfies certain properties in terms of n and m (or n and p, resp.). If G(n,m) (or G(n,p), resp.) satisfies a property with probability close to 1, then one may say that a `typical graph’ with m edges (or expected edge density p, resp.) on n vertices has the property. Random graphs and their variants are also widely used to prove the existence of graphs with certain properties. In this talk, two problems for these categories will be discussed. First, a new approach will be introduced for the problem of the emergence of a giant component of G(n,p), which was first considered by Erdős–Rényi in 1960. Second, a variant of the graph process G(n,1), G(n,2), …, G(n,m), … will be considered to find a tight lower bound for Ramsey number R(3,t) up to a constant factor. (No prior knowledge of graph theory is needed in this talk.)