Seminars and Colloquia by Series

Spatial mixing and the Swendsen-Wang dynamics

Series
Combinatorics Seminar
Time
Friday, September 18, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Antonio Blanca Pennsylvania State University

The Swendsen-Wang dynamics is a popular algorithm for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. The dynamics is a global Markov chain that is conjectured to converge quickly to equilibrium even at low temperatures, where the correlations in the system are strong and local chains converge slowly. In this talk, we present new results concerning the speed of convergence of the Swendsen-Wang dynamics under spatial mixing (i.e., decay of correlations) conditions. In particular, we provide tight results for three distinct geometries: the integer d-dimensional integer lattice graph Z^d, regular trees, and random d-regular graphs. Our approaches crucially exploit the underlying geometry in different ways in each case.

The chromatic number of a random lift of K_d

Series
Combinatorics Seminar
Time
Friday, September 11, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Xavier Pérez GiménezUniversity of Nebraska-Lincoln

An n-lift of a graph G is a graph from which there is an n-to-1 covering map onto G. Amit, Linial, and Matousek (2002) raised the question of whether the chromatic number of a random n-lift of K_5 is concentrated on a single value. We consider a more general problem, and show that for fixed d ≥ 3 the chromatic number of a random lift of K_d is (asymptotically almost surely) either k or k+1, where k is the smallest integer satisfying d < 2k log k. Moreover, we show that, for roughly half of the values of d, the chromatic number is concentrated on k. The argument for the upper-bound on the chromatic number uses the small subgraph conditioning method, and it can be extended to random n-lifts of G, for any fixed d-regular graph G. (This is joint work with JD Nir.)

On the Helfgott-Lindenstrauss conjecture for linear groups

Series
Combinatorics Seminar
Time
Friday, September 4, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Speaker
Brendan MurphyUniversity of Bristol

Freiman's theorem characterizes finite subsets of abelian groups that behave "approximately" like subgroups: any such set is (roughly) a sum of arithmetic progressions and a finite subgroup. Quantifying Freiman's theorem is an important area of additive combinatorics; in particular, proving a "polynomial" Freiman theorem would be extremely useful.

The "Helfgott-Lindenstrauss conjecture" describes the structure of finite subsets of non-abelian groups that behave approximately like subgroups: any such set is (roughly) a finite extension of a nilpotent group. Breuillard, Green, and Tao proved a qualitative version of this conjecture. In general, a "polynomial" version of the HL conjecture cannot hold, but we prove that a polynomial version of the HL conjecture is true for linear groups of bounded rank.

In this talk, we will see how the "sum-product phenomenon" and its generalizations play a crucial role in the proof of this result. The amount of group theory needed is minimal.

Exponentially Many Hypergraph Colourings

Series
Combinatorics Seminar
Time
Friday, August 28, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/751242993/???? (Replace ???? with the password sent via email)
Speaker
Lutz WarnkeGeorgia Institute of Technology

We shall discuss a recent paper of Wanless and Wood (arXiv:2008.00775), which proves a Lovász Local Lemma type result using inductive counting arguments.
For example, in the context of hypergraph colorings, under LLL-type assumptions their result typically gives exponentially many colorings (usually more than the textbook proof of LLL would give).
We will present a probabilistic proof of the Wanless-Wood result, and discuss some applications to k-SAT, Ramsey number lower bounds, and traversals, as time permits.

TBA by Jeffrey Rosenthal

Series
Combinatorics Seminar
Time
Friday, April 17, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jeffrey RosenthalUniversity of Toronto

TBA (joint with Stochastics Seminar)

Cancelled due to COVID-19: Counting extensions revisited

Series
Combinatorics Seminar
Time
Friday, March 27, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Lutz WarnkeGeorgia Tech

We consider rooted subgraphs in random graphs, i.e., extension counts such as (i) the number of triangles containing a given vertex or (ii) the number of paths of length three connecting two given vertices. 
In 1989, Joel Spencer gave sufficient conditions for the event that, with high probability, these extension counts are asymptotically equal for all choices of the root vertices.  
For the important strictly balanced case, Spencer also raised the fundamental question whether these conditions are necessary. 
We answer this question by a careful second moment argument, and discuss some intriguing problems that remain open. 

Graph fractal dimension and structure of fractal networks: a combinatorial perspective

Series
Combinatorics Seminar
Time
Friday, March 6, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Pavel SkumsGeorgia State University

We study self-similar and fractal networks from the combinatorial perspective. We establish analogues of topological (Lebesgue) and fractal (Hausdorff) dimensions for graphs and demonstrate that they are naturally related to known graph-theoretical characteristics: rank dimension and product (or Prague or Nešetřil-Rödl) dimension. Our approach reveals how self-similarity and fractality of a network are defined by a pattern of overlaps between densely connected network communities. It allows us to identify fractal graphs, explore the relations between graph fractality, graph colorings and graph Kolmogorov complexity, and analyze the fractality of several classes of graphs and network models, as well as of a number of real-life networks. We demonstrate the application of our framework to evolutionary studies by revealing the growth of self-organization of heterogeneous viral populations over the course of their intra-host evolution, thus suggesting mechanisms of their gradual adaptation to the host's environment. As far as the authors know, the proposed approach is the first theoretical framework for study of network fractality within the combinatorial paradigm. The obtained results lay a foundation for studying fractal properties of complex networks using combinatorial methods and algorithms.

Based on joint work with Leonid Bunimovich

Scalefree hardness of the Euclidean TSP

Series
Combinatorics Seminar
Time
Friday, February 7, 2020 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Wesley PegdenCarnegie Mellon University

We  show  that  if  $P\neq NP$,  then  a  wide  class  of  TSP heuristics fail to approximate the length of the TSP to asymptotic 
optimality, even for random Euclidean instances.  Previously, this result was not even known for any heuristics (greedy, etc) used in practice.  As an application, we show that when  using  a  heuristic from  this  class,  a  natural  class  of  branch-and-bound algorithms takes exponential time to find an optimal tour (again, even on a random point-set),  regardless  of  the  particular  branching  strategy  or lower-bound algorithm used.

Pages