Seminars and Colloquia by Series

Sets without 4APs but with many 3APs

Series
Combinatorics Seminar
Time
Friday, January 31, 2020 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Andrei (Cosmin) PohoataCalifornia Inst. of Technology, Pasadena, CA

 It is a classical theorem of Roth that every dense subset of $\left\{1,\ldots,N\right\}$ contains a nontrivial three-term arithmetic progression. Quantitatively, results of Sanders, Bloom, and Bloom-Sisask tell us that subsets of relative density at least $1/(\log N)^{1-\epsilon}$ already have this property. In this talk, we will discuss some sets of $N$ integers which unlike $\left\{1,\ldots,N\right\}$ do not contain nontrivial four-term arithmetic progressions, but which still have the property that all of their subsets of density at least $1/(\log N)^{1-\epsilon}$ must contain a three-term arithmetic progression. Perhaps a bit surprisingly, these sets turn out not to have as many three-term progressions as one might be inclined to guess, so we will also address the question of how many three-term progressions can a four-term progression free set may have. Finally, we will also discuss about some related results over $\mathbb{F}_{q}^n$. Based on joint works with Jacob Fox and Oliver Roche-Newton.

Fast uniform generation of random graphs with given degree sequences

Series
Combinatorics Seminar
Time
Friday, January 24, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Andrii ArmanEmory University

In this talk I will discuss algorithms for a uniform generation of random graphs with a given degree sequence. Let $M$ be the sum of all degrees and $\Delta$ be the maximum degree of a given degree sequence. McKay and Wormald described a switching based algorithm for the generation of graphs with given degrees that had expected runtime $O(M^2\Delta^2)$, under the assumption $\Delta^4=O(M)$. I will present a modification of the McKay-Wormald algorithm that incorporates a new rejection scheme and uses the same switching operation. A new algorithm has expected running time linear in $M$, under the same assumptions.

I will also describe how a new rejection scheme can be integrated into other graph generation algorithms to significantly reduce expected runtime, as well as how it can be used to generate contingency tables with given marginals uniformly at random.

This talk is based on the joint work with Jane Gao and Nick Wormald.

Non-concentration of the chromatic number of a random graph

Series
Combinatorics Seminar
Time
Friday, January 10, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Lutz Warnke

We shall discuss the recent breakthrough of  Annika Heckel on the chromatic number of the binomial random graph G(n,1/2),  showing that it is not concentrated on any sequence of intervals of length n^{1/4-o(1)}.

To put this into context, in 1992 Erdos (and also Bollobás in 2004) asked for any non-trivial results asserting a lack of concentration, pointing out that even the weakest such results would be of interest.  
Until recently this seemed completely out of reach, in part because there seemed to be no obvious approach/strategy how to get one's foot in the door. 
Annika Heckel has now found such an approach, based on a clever coupling idea that compares the chromatic number of G(n,1/2) for different n. 
In this informal talk we shall try to say a few words about her insightful proof approach from https://arxiv.org/abs/1906.11808

Please note the unusual room (Skiles 202)

Thresholds versus fractional expectation-thresholds

Series
Combinatorics Seminar
Time
Friday, December 6, 2019 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jinyoung ParkRutgers University

(This is a joint event of the Combinatorics Seminar Series and the ACO Student Seminar.)

In this talk we will prove a conjecture of Talagrand, which is a fractional version of the “expectation-threshold” conjecture of Kalai and Kahn. This easily implies various difficult results in probabilistic combinatorics, e.g. thresholds for perfect hypergraph matchings (Johansson-Kahn-Vu) and bounded-degree spanning trees (Montgomery). Our approach builds on recent breakthrough work of Alweiss, Lovett, Wu, and Zhang on the Erdos-Rado “Sunflower Conjecture.” 

This is joint work with Keith Frankston, Jeff Kahn, and Bhargav Narayanan.

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.

Pages