Seminars and Colloquia by Series

On a class of sums with unexpectedly high cancellation, and its applications

Series
Combinatorics Seminar
Time
Friday, November 15, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Hamed MousaviGeorgia Tech

We report on the discovery of a general principle leading to the unexpected cancellation of oscillating sums. It turns out that sums in the
class we consider are much smaller than would be predicted by certain probabilistic heuristics. After stating the motivation, and our theorem,
we apply it to prove a number of results on integer partitions, the distribution of prime numbers, and the Prouhet-Tarry-Escott Problem. For example, we prove a "Pentagonal Number Theorem for the Primes", which counts the number of primes (with von Mangoldt weight) in a set of intervals very precisely. In fact the result is  stronger than one would get using a strong form of the Prime Number Theorem and also the Riemann Hypothesis (where one naively estimates the \Psi function on each of the intervals; however, a less naive argument can give an improvement), since the widths of the intervals are smaller than \sqrt{x}, making the Riemann Hypothesis estimate "trivial".

Based on joint work with Ernie Croot.

Finding cliques in random graphs by adaptive probing

Series
Combinatorics Seminar
Time
Friday, November 8, 2019 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Miklos RaczPrinceton University

I will talk about algorithms (with unlimited computational power) which adaptively probe pairs of vertices of a graph to learn the presence or absence of edges and whose goal is to output a large clique. I will focus on the case of the random graph G(n,1/2), in which case the size of the largest clique is roughly 2\log(n). Our main result shows that if the number of pairs queried is linear in n and adaptivity is restricted to finitely many rounds, then the largest clique cannot be found; more precisely, no algorithm can find a clique larger than c\log(n) where c < 2 is an explicit constant. I will also discuss this question in the planted clique model. This is based on joint works with Uriel Feige, David Gamarnik, Joe Neeman, Benjamin Schiffer, and Prasad Tetali. 

Local limit theorems for combinatorial random variables

Series
Combinatorics Seminar
Time
Friday, November 1, 2019 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 249
Speaker
Ross BerkowitzYale University

Let X be the number of length 3 arithmetic progressions in a random subset of Z/101Z.  Does X take the values 630 and 640 with roughly the same probability?
Let Y denote the number of triangles in a random graph on n vertices.  Despite looking similar to X, the local distribution of Y is quite different, as Y obeys a local limit theorem.  
We will talk about a method for distinguishing when combinatorial random variables obey local limit theorems and when they do not.

Twisted Schubert polynomials

Series
Combinatorics Seminar
Time
Friday, October 18, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Ricky LiuNorth Carolina State University

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.

Long-range order in random colorings and random graph homomorphisms in high dimensions

Series
Combinatorics Seminar
Time
Friday, March 29, 2019 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yinon SpinkaUniversity of British Columbia, Vancouver, Canada

Consider a uniformly chosen proper coloring with q colors of a domain in Z^d (a graph homomorphism to a clique). We show that when the dimension is much higher than the number of colors, the model admits a staggered long-range order, in which one bipartite class of the domain is predominantly colored by half of the q colors and the other bipartite class by the other half. In the q=3 case, this was previously shown by Galvin-Kahn-Randall-Sorkin and independently by Peled. The result further extends to homomorphisms to other graphs (covering for instance the cases of the hard-core model and the Widom-Rowlinson model), allowing also vertex and edge weights (positive temperature models). Joint work with Ron Peled.

Contagion in random graphs and systemic risk

Series
Combinatorics Seminar
Time
Friday, February 15, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Hamed AminiGeorgia State University
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.

Hamiltonian Cycles in Uniform Hypergraphs with Large Minimum Degree

Series
Combinatorics Seminar
Time
Friday, February 8, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Andrzej RucinskiEmory and AMU Poznań

Abstract: Reiher, Rödl, Ruciński, Schacht, and Szemerédi proved, via a modification of the absorbing method, that every 3-uniform $n$-vertex hypergraph, $n$ large, with minimum vertex degree at least $(5/9+\alpha)n^2/2$ contains a tight Hamiltonian cycle. Recently, owing to a further modification of the method, the same group of authors joined by Bjarne Schuelke, extended this result to 4-uniform hypergraphs with minimum pair degree at least, again, $(5/9+\alpha)n^2/2$. In my talk I will outline these proofs and point to the crucial ideas behind both modifications of the absorbing method.

Property testing and removal lemma

Series
Combinatorics Seminar
Time
Friday, January 25, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Fan WeiStanford University
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.

Fast sampling of sparse contingency tables

Series
Combinatorics Seminar
Time
Friday, January 18, 2019 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 169 (*Unusual room*)
Speaker
Samuel DittmerMathematics, UCLA
We present a new algorithm for sampling contingency tables with fixed margins. This algorithm runs in polynomial time for certain broad classes of sparse tables. We compare the performance of our algorithm theoretically and experimentally to existing methods, including the Diaconis-Gangolli Markov chain and sequential importance sampling. Joint work with Igor Pak.

A tale of models for random graphs

Series
Combinatorics Seminar
Time
Thursday, January 17, 2019 - 12:00 for 1.5 hours (actually 80 minutes)
Location
Skiles 005
Speaker
Jeong Han KimKorea Institute for Advanced Study (KIAS)
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.)

Pages