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.

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
K_{t}-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 L_{i}(S)={u∈V(G) and d(u,S)=i} for any integer i≥0. We show that if G[S] is connected and G[L_{i}(S)] is bipartite for each i∈{1…,l-1}, then G[L_{i}(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 (S_{v}, T_{v}) of sets such that there is an edge from v to w if and only if S_{v} and T_{w} intersect. An intersection digraph is reflexive if S_{v}∩ T_{v}≠ ∅ 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 n^{1/2}. Alon improved this
slightly to n^{1/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 n^{1/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
n^{1/4+o(1))} and n^{1/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 P_{n} 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} =
P_{n} (improvement of lower bound) and where ℱ_{1} =
P_{n}, ℱ_{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(n^{2}) 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 Z^{d} 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.