Round the World Relay in Combinatorics, Tuesday June 8, 2021


The international "Round the World Relay in Combinatorics" took place on Tuesday June 8, 2021. There were 22 seminars, hosted by different groups around the world. The day started in Australia at 2am UTC and ended in Alaska at 11pm UTC. Stops along the way include Brazil, Canada, Chile, China, Czech Republic, France, Hungary, New Zealand, Poland, Russia, South Korea, the United Kingdom, and the USA.

Thanks to Balazs Keszegh for designing the poster to the right. A pdf version of the poster can be found here.

The event was coordinated by Alex Scott (Email: lastname at maths.ox.ac.uk). Special thanks to János Pach (who made many contributions, including suggesting the name), as well as to Andrey Kupavskii and Sang-il Oum.


Schedule

The meeting took place over Zoom. The talks were recorded and are available on the youtube channel. The amazing introductory segments for the videos were created by Yulia Rylova.

Times are displayed in UTC and your browser's local time; thanks to Sang-il Oum for javascript that does this.


     Monash Discrete Mathematics Seminar, Melbourne, Australia (organised by Ian Wanless and Graham Farr)

Speaker: David Wood (Monash University)
Title: Universality in minor-closed graph classes

Abstract. Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). János Pach (1981) answered this question in the negative. We strengthen this result by showing that every countable graph that contains all countable planar graphs must contain an infinite complete graph as a minor. On the other hand, we construct a countable graph that contains all countable planar graphs and has several key properties such as linear colouring numbers, linear expansion, and every finite n-vertex subgraph has O(\sqrt{n}) treewidth (which implies the Lipton-Tarjan separator theorem). More generally, for every fixed positive integer t we construct a countable graph that contains every countable Kt-minor-free graph and has the above key properties. Joint work with Tony Huynh, Bojan Mohar, Robert Samal and Carsten Thomassen.


     SCMS Combinatorics Seminar, Shanghai Center for Mathematical Sciences, China (organized by Ping Hu, Hehui Wu and Qiqin Xie)

Speaker: Baogang Xu (Nanjing Normal University, China)
Title: On coloring of graphs of girth 2l+1 without longer odd holes

Abstract: A hole is an induced cycle of length at least 4. Let l≥2 be a positive integer, let Ĝl denote the family of graphs which have girth 2l+1 and have no holes of odd length at least 2l+3, and let G ∈ Ĝl. For a vertex u ∈ V(G) and a nonempty set S ⊆ V(G), let d(u,S) = min{d(u,v) : v∈S}, and let Li(S)={u∈V(G) and d(u,S)=i} for any integer i≥0. We show that if G[S] is connected and G[Li(S)] is bipartite for each i∈{1…,l-1}, then G[Li(S)] is bipartite for each i>0, and consequently χ(G)≤4, where G[S] denotes the subgraph induced by S. For a graph G∈ Ĝ2, we show that χ(G)≤3 if G induces no two cycles of length 5 sharing edges. Let θ+ be the graph obtained from the Petersen graph by removing two adjacent vertices. We show that if G ∈ Ĝ2 is 3-connected and has no unstable 3-cutset, then G does not induce θ+. As a corollary, minimal non-3-colorable graphs of Ĝ2 induce no θ+. This is a joint work with Di Wu and Yian Xu.


     Algebra and Combinatorics seminar, Auckland, New Zealand (organized by Lukas Zobernig and Matthew Conder)

Speaker: Jeroen Schillewaert (University of Auckland)
Title: Constructing highly regular expanders from hyperbolic Coxeter groups

Abstract: Given a string Coxeter system (W,S), we construct highly regular quotients of the 1-skeleton of its universal polytope P, which form an infinite family of expander graphs when (W,S) is indefinite and P has finite vertex links. The regularity of the graphs in this family depends on the Coxeter diagram of (W,S). The expansion stems from superapproximation applied to (W,S). This construction is also extended to cover Wythoffian polytopes. As a direct application, we obtain several notable families of expander graphs with high levels of regularity, answering, in particular, the question posed by Chapman, Linial, and Peled positively.
(Joint work with Marston Conder, Alexander Lubotzky and Francois Thilmany)


     CMSA seminar, Australia (organized by Nina Kamcev and Anita Liebenau)

Speaker: Gordon Royle (University of Western Australia (UWA))
Title: Real chromatic roots of planar graphs

Abstract: The chromatic polynomial P(G,q) of a graph G is the function that, for positive integer q, counts the number of proper q-colourings of the graph. The resulting function is a polynomial so, whether or not it makes any combinatorial sense, we can evaluate it at any complex number and therefore find its roots which may be integer, real of complex. The overall aim of this heavily studied topic is to understand the relationship between the properties of a graph and the location of its chromatic roots.
In this talk, I will focus on the real roots of the chromatic polynomials of planar graphs. I will start by giving some of the history, background and basic results, before focussing on efforts (by myself and others) to show that planar chromatic roots are dense in the real interval (3,4).
The talk is mostly at a general level and anyone familiar with the basic concepts of graphs, proper colourings of graphs and polynomials will be able to follow the gist of it.


     Discrete Math Seminar at the IBS Discrete Mathematics Group, South Korea (organized by Sang-il Oum)

Speaker: O-joung Kwon (Incheon National University and IBS Discrete Mathematics Group)
Title: Classes of intersection digraphs with good algorithmic properties

Abstract: An intersection digraph is a digraph where every vertex v is represented by an ordered pair (Sv, Tv) of sets such that there is an edge from v to w if and only if Sv and Tw intersect. An intersection digraph is reflexive if Sv∩ Tv≠ ∅ for every vertex v. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs, not many algorithmic applications on intersection digraphs have been developed.
Motivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width, we introduce its directed analogue called `bi-mim-width' and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular, we show that as a natural extension of H-graphs, reflexive H-digraphs have linear bi-mim-width at most 12|E(H)|, which extends a bound on the linear mim-width of H-graphs [On the Tractability of Optimization Problems on H-Graphs. Algorithmica 2020].
For applications, we introduce a novel framework of directed versions of locally checkable problems, that streamlines the definitions and the study of many problems in the literature and facilitates their common algorithmic treatment. We obtain unified polynomial-time algorithms for these problems on digraphs of bounded bi-mim-width, when a branch decomposition is given. Locally checkable problems include Kernel, Dominating Set, and Directed H-Homomorphism.
This is joint work with Lars Jaffke and Jan Arne Telle.


     TCS Seminar at Jagiellonian, Poland (organized by Paweł Idziak and Piotr Micek)

Speaker: Bartosz Walczak (Jagiellonian)
Title: Coloring polygon visibility graphs and their generalizations

Abstract: The visibility graph of a polygon P is formed by the pairs of vertices u and v of P such that the segment uv is disjoint from the exterior of P. We show that the class of polygon visibility graphs is χ-bounded, thus answering a question by Kára, Pór, and Wood from 2005. Specifically, we prove the bound χ≤3·4ω-1. We obtain the same bound for generalizations of polygon visibility graphs in which the polygon is replaced by a curve and straight-line segments are replaced by segments in a pseudo-line arrangement. The proof is carried through in the setting of ordered graphs. In particular, we show χ-boundedness of several classes of ordered graphs with excluded ordered substructures. Joint work with James Davies, Tomasz Krawczyk, and Rose McCarty.



     Mini Online Scottish Combinatorics Meeting, University of Glasgow, UK (organized by Kitty Meeks)

Speaker: Heng Guo (University of Edinburgh)
Title: A Markov chain approach towards the sampling Lovász local lemma

Abstract: Lovász local lemma is a powerful tool to establish the existence of combinatorial objects under certain dependency conditions. The algorithmic local lemma by Moser and Tardos gives an efficient way to find such objects. We are interested in the sampling local lemma, whose goal is to uniformly generate these objects efficiently, potentially under stronger conditions than those of the local lemma. This sampling problem has seen some rapid advances in recent years, and in this talk I will illustrate a Markov chain approach for this task. The running example will be sampling solutions to k-CNF formulas where each variable does not appear in too many clauses. The main difficulty to design a Markov chain here is that the solution space is not connected via local moves. This issue will be circumvented by a projection idea.


     LSE, UK (organized by Ahmad Abdi and Jozef Skokan)

Speaker: Annika Heckel (LMU)
Title: How does the chromatic number of a random graph vary?

Abstract: How much does the chromatic number of the random graph G(n, 1/2) vary? Shamir and Spencer proved that it is contained in some sequence of intervals of length about n1/2. Alon improved this slightly to n1/2 / log n. Until recently, however, no lower bounds on the fluctuations of the chromatic number of G(n, 1/2) were known, even though the question was raised by Bollobás many years ago. I will talk about the main ideas needed to prove that, at least for infinitely many n, the chromatic number of G(n, 1/2) is not concentrated on fewer than n1/2-o(1) consecutive values.
I will also discuss the Zigzag Conjecture, made recently by Bollobás, Heckel, Morris, Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length 'zigzags' between n1/4+o(1)) and n1/2+o(1), depending on n.
Joint work with Oliver Riordan.


     MIPT Big Seminar of Combinatorics and Geometry, Moscow, Russia (organized by A. Kupavskii, J. Pach, A. Polyanskii, I. Shkredov, M. Zhukovskii)

Speaker: Noga Alon (Princeton and Tel Aviv)
Title: Splitting random necklaces

Abstract: Let N be a random necklace with km beads of each of t types. What is the typical minimum number of points in which one can cut N so that it will be possible to partition the resulting intervals of beads into k collections, each containing exactly m beads of each type ? It is known that this number is at most (k-1)t with probability 1, is it typically significantly smaller? I will discuss a recent joint work with Dor Elboim, Janos Pach and Gabor Tardos addressing this problem and showing that it is connected to several seemingly unrelated topics, including matchings in nearly regular hypergraphs and random walks in Euclidean spaces.


     Budapest (BBC+G) seminar, Hungary (organized by János Pach, Dömötör Pálvölgyi, Géza Tóth)

Speaker: László Lovász (Eotvos University, Budapest)
Title: Orthogonal representations and graph limits

Abstract: Orthogonal representations have played a role in information theory, combinatorial optimization, rigidity theory and quantum physics. We start with a survey of these connections.
Recent interest in this construction is motivated by graph limit theory. Limit objects of convergent graph sequences have been defined in the two extreme cases: graphons (limits of dense graph sequences) and graphings (limits of bounded-degree graph sequences). In the middle ranges, Markov chains seem to play an important role. An interesting example from this point of view is the Markov chain on the sphere in a fixed dimension, where a step is a move by 90 degrees in any direction.
A basic question: is this object a limit of finite graphs (and in what sense)? To get an affirmative answer, we need to define the density of a given simple graph in the orthogonality graph. This leads to the problem of defining and computing a random orthogonal representation of this graph, which is an interesting and nontrivial issue on its own.


     Bordeaux Seminar, France (organized by Jonathan Narboni and Marthe Bonamy)

Speaker: Carla Groenland (Utrecht University)
Title: Universal graphs and labelling schemes

Abstract: An induced universal graph for a graph class contains all graphs in the class as an induced subgraph. We construct induced universal graphs for all hereditary graph classes, and derive reachability labelling schemes for digraphs and comparability labelling schemes for posets from this. All these results are asymptotically optimal. This talk aims to give some intuition about these concepts and our techniques (including Szemeredi regularity lemma and efficient dictionaries). We will also discuss a new venue of research: what if we strengthen induced to isometric? Several interesting questions are left open.
This is based on joint work with Marthe Bonamy, Louis Esperet, Cyril Gavoille and Alex Scott.


     NYC Combinatorics Seminar, USA (organized by Kira Adaricheva, Deepak Bal, Nadia Benakli, Jonathan Cutler, Ezra Halleck, Sandra Kingan, Joseph Malkevitch, Kerry Okajian, Eric Rowland and Mingxian Zhong.)

Speaker: Deepak Bal (Montclair State University)
Title: Size Ramsey numbers of paths and cycles

Abstract: Let ℱ1 and ℱ2 be two families of graphs. The size Ramsey number R̂(ℱ1, ℱ2) is the smallest number m such that there exists a graph G with m edges in which every red-blue coloring of E(G) contains either a red graph from ℱ1 or a blue graph from ℱ2. Let Pn represent the path on n vertices and let 𝒞 represent the family of all cycles.We discuss some recent progress on size Ramsey numbers in the cases where ℱ1 = ℱ2 = Pn (improvement of lower bound) and where ℱ1 = Pn, ℱ2 = 𝒞 (improvement of lower and upper bounds). We will also discuss some recent results concerning the size Ramsey number of hypergraph paths. This is based on joint works with DeBiasio and Schudrich.


     Extremal and Probabilistic Combinatorics Webinar (organized by Jan Hladky, Diana Piguet, Jan Volec and Liana Yepremyan)

Speaker: Dhruv Mubayi (University of Illinois at Chicago)
Title: The feasible region of hypergraphs

Abstract: Many extremal hypergraph problems seek to maximize the number of edges subject to some local constraints. We aim to gain a more detailed understanding of such problems by studying the maximum subject to an additional global constraint, namely the size of the shadow. Put differently, we seek the pairs (x,y) in the unit square such that there are F-free hypergraphs whose shadow density approaches x and edge density approaches y. I will give some general results about the shape of this "feasible region" and also extend and improve some classical Turan-type results for particular choices of F. This is joint work with Xizhi Liu.


     Joint DIMEA and FORMELA seminar, Masaryk University, Czech Republic (organized by Daniel Kral and Samuel Mohr)

Speaker: James Davies (Waterloo)
Title: Colouring circle graphs and their generalisations

Abstract: A circle graph is an intersection graph of a set of chords on a circle; vertices are adjacent whenever their corresponding chords intersect. A classical graph colouring result due to Gyárfás states that circle graphs are χ-bounded, i.e., circle graphs with bounded clique number have bounded chromatic number. I will discuss some recent results concerning χ-boundedness of circle graphs and various more general classes that contain them.
This talk includes joint work with Tomasz Krawczyk, Rose McCarty, and Bartosz Walczak.


     Oxford Discrete Mathematics and Probability Seminar, UK (organized by Christina Goldschmidt and Alex Scott)

Speaker: Jacob Fox (Stanford)
Title: Removal lemmas

Abstract: The triangle removal lemma is a central result in extremal combinatorics, with many applications in number theory, graph theory, discrete geometry, and theoretical computer science. It says that any graph with n vertices and o(n^3) triangles can be made triangle-free by removing o(n2) edges. In this talk, I will survey recent extensions and variants, quantitative aspects, applications, and open problems.


     The Ohio State University Combinatorics & Probability Seminar, USA (organized by Matthew Kahle, Hoi Nguyen, David Sivakoff and Caroline Terry)

Speaker: Allan Sly (Princeton)
Title: Spread of infections in random walkers

Abstract: We consider a class of interacting particle systems where particles perform independent random walks on Zd and spread an infection according to a Susceptible-Infectious-Recovered or SIR model. We show that if the recovery rate is low enough, the infection spreads linearly. I will describe new methods to understand growth processes in such models.
Joint work with Duncan Dauvergne


     Rio Seminar, Brazil (organized by Rob Morris)

Speaker: Marcelo Campos (IMPA)
Title: Title: The singularity probability of a random symmetric matrix is exponentially small

Abstract: Let A be drawn uniformly at random from the set of all n x n symmetric matrices with entries in {-1,1}. I'll describe some recent work where we show that Pr(det(A) = 0) < e-cn for some absolute constant c > 0.
Joint work with Matthew Jenssen, Marcus Michelen and Julian Sahasrabudhe.


     Georgia Tech Seminar, USA (organized by Anton Bernshteyn, Zhiyu Wang and Xingxing Yu)

Speaker: Jim Geelen (University of Waterloo)
Title: Homomorphisms and colouring for graphs and binary matroids

Abstract: The talk starts with Rödl's Theorem that graphs with huge chromatic number contain triangle-free subgraphs with large chromatic number. We will look at various related results and conjectures, with a notable matroid bias; the new results are joint work with Peter Nelson and Raphael Steiner.


     AGCO Seminar, Chile (organized by Maya Stein)

Speaker: David Conlon (Caltech)
Title: Random multilinear maps and the Erdős box problem

Abstract: By using random multilinear maps, we provide new lower bounds for the Erdős box problem, the problem of estimating the extremal number of the complete d-partite d-uniform hypergraph with two vertices in each part, thereby improving on work of Gunderson, Rödl and Sidorenko. Joint work with Cosmin Pohoata and Dmitriy Zakharov.


     SFU Discrete Math Seminar, Simon Fraser University, Canada (organized by Shuxing Li and Alexandra Wesolek)

Speaker: Fan Chung (UCSD)
Title: Trees and forests in Green's functions of a graph

Abstract: The Green's functions of a graph are the pseudo inverses of the Laplacians and therefore are useful for solving many types of Laplace equations in discrete settings.
In this talk, we will give combinatorial interpretations of Green's functions in terms of Counting trees and forests in a graph. We will also mention several applications concerning the pagerank algorithms and the hitting time for random walks.


    University of Victoria Discrete Math Seminar, Canada (organized by Natasha Morrison and Jonathan Noel)

Speaker: Andrew Suk (UCSD)
Title: Turán-type problems for point-line incidences

Abstract: In this talk, I will discuss several Turán-type results for point-line incidences. It will be based on joint works with Istvan Tomon and Mozhgan Mirzaei.


    University of Alaska Fairbanks, USA (organized by Jill Faudree)

Speaker: Ron Gould (Emory)
Title: Chorded cycles

A chord of a cycle is an edge between two vertices of the cycle that is not an edge of the cycle. A cycle in a graph G is said to be chorded if its vertices induce at least one chord, and it is called doubly chorded if its vertices induce two or more chords. The past decade has seen a vast increase in the study of chorded cycles.
In this talk I will survey a variety of results dealing with chorded cycles. I will consider several types of questions dealing with chorded cycles and con- sider the major known results in each of these areas. This includes minimum degree and degree sum results, forbidden subgraph results, and edge density results. We will ask questions like:` When can an edge be a chord of a cycle and when can an edge be a cycle edge of a chorded cycle? Many times, I will try to place these chorded cycle results in relation to known results on cycles and show that the chorded cycle results are actually natural extensions of known cycle results.