Organizers : Jeff Kahn, Bhargav Narayanan and Jinyoung Park.
All seminars after March 9th were cancelled due to COVID-19 restrictions.
Date: March 9th, 2020
Speaker: David Galvin (University of Notre Dame)
Title: Independent set permutations, and matching permutations
Abstract:
To a sequence associate a permutation $\pi$, via: $\pi(k)$ is the index of the k-th smallest element of the sequence. This association was introduced in 1987 by Alavi, Malde, Schwenk and Erd\H{o}s, who used it to study the possible patterns of rises and falls that can occur in the matching sequence of a graph (the sequence whose k-th term is the number of matchings of size k), as well as in the independent set sequence.
Their main result was that every permutation can arise as the ``independent set permutation'' of some graph. They left open the following extremal question: for each n, what's the smallest order m such that every permutation of [n] can be realized as the independent set permutation of some graph of order at most m?
We answer this question. We also improve on Alavi et al.'s upper bound on the number of permutations that can be realized as the matching permutation of some graph. This is joint work with T. Ball, K. Hyry and K. Weingartner, all at Notre Dame.
Date: March 2nd, 2020
Speaker: Sophie Spirkl (Princeton University)
Title: Pure pairs in graphs with forbidden induced subgraphs
Abstract:
Given a graph G, two subsets A and B of its vertex set are a "pure pair" if either all or none of the edges between them are present in G.
Motivated by the Erdos-Hajnal conjecture, we ask: Given a class of graphs C defined by forbidding induced subgraphs, do all graphs in C have large pure pairs? More precisely, for which functions f and g does every n-vertex graph in C have a pure pair with |A| = f(n) and |B| = g(n)?
Two years ago, I talked about classes of graphs for which f and g can be chosen as linear functions. This time, I will talk about more recent progress on the general question, and related results.
Joint work with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour.
Date: February 24th, 2020
Speaker: Peter Winkler (Dartmouth / MoMath)
Title: Random Permutations and the Displacement Ratio
Abstract:
The "displacement ratio" R is the ratio of two natural measures of how close a permutation is to the identity, and is known always to be between 1 and 2.
We want to know: what is R for a random permutation in S_n with a given number m(n) of inversions? The behavior of R as m(n) changes is not entirely proven but seems rather surprising.
Ongoing work with David Bevan, U. of Strathclyde.
Date: February 17th, 2020
Speaker: Keith Frankston (Rutgers University)
Title: Thresholds versus fractional-expectation thresholds
Abstract:
Given an increasing family F of subsets of a finite set X, its measure according to \mu_p increases and often exhibits a threshold behavior, growing quickly as p increases from near 0 to near 1 around a specific value p_c. These thresholds have been a central focus of the study of random discrete structures, with estimation of thresholds for specific properties the subject of some of the most challenging work in the area.
In 2006, Kahn and Kalai conjectured that a natural (and often easy to calculate) lower bound q(F) (which we call the ``expectation-threshold'') for p_c is never far from its actual value. We prove a fractional version (proposed by Talagrand) of this so called ``expectation-threshold'' conjecture showing that for any increasing family we have p_c(F) = O(q_f(F) \log \ell(F)), where q_f is the ``fractional expectation-threshold'' and \ell(F) is the maximum size of a minimal element of F.
This result easily implies previously difficult results in probabilistic combinatorics such as thresholds for perfect hypergraph matchings (Johansson-Kahn-Vu) and bounded-degree spanning trees (Montgomery). Our approach builds on a recent breakthrough of Alweiss, Lovett, Wu and Zhang on the Erdős-Rado ``Sunflower Conjecture.''
Joint with Jeff Kahn, Bhargav Narayanan, and Jinyoung Park.
Date: February 10th, 2020
Speaker: Ander Lamaison (Freie Universität Berlin)
Title: Ramsey upper density of infinite graphs
Abstract:
Let H be an infinite graph. In a two-coloring of the edges of the complete graph on the natural numbers, what is the densest monochromatic subgraph isomorphic to H that we are guaranteed to find? We measure the density of a subgraph by the upper density of its vertex set. This question, in the particular case of the infinite path, was introduced by Erdős and Galvin. Following a recent result for the infinite path, we present bounds on the maximum density for other choices of H, including exact values for a wide class of bipartite graphs.
Date: February 3rd, 2020
Speaker: Guy Moshkovitz (IAS)
Title: New Results on Projections
Abstract:
What is the largest number of projections onto k coordinates guaranteed in every family of m binary vectors of length n?
This fundamental question is intimately connected with important topics and results in combinatorics and computer science (Turan numbers, the Sauer-Perles-Shelah Lemma, the Kahn-Kalai-Linial Theorem), and is generally wide open.
We (essentially) settle the question for a wide range of parameters: linear k and sub-exponential m.
Based on joint work with Noga Alon and Noam Solomon.