Round the World Relay in Combinatorics


On Tuesday 8 June, 2021, a number of seminars and groups around the world are getting together for a Round the World Relay in Combinatorics. Each site will host a talk, and everyone is welcome!
If you would like to organize a talk or have any questions, then please get in touch with Alex Scott (Email: lastname at maths.ox.ac.uk).

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


Schedule

Here is a list of talks that have been scheduled so far! Further details will be put up over the coming weeks. We will put up a Zoom link or other joining information before the seminars take place.



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

Speaker: David Wood (Monash University)


3am (UTC)      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.


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


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

Speaker: Gordon Royle (University of Western Australia (UWA))


6am (UTC)      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.

7am (UTC)      TCS @ Jagiellonian Seminar , Poland (organized by Paweŀ Idziak and Piotr Micek)


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

Speaker: Heng Guo (University of Edinburgh)


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

Speaker: Annika Heckel (LMU)


10am (UTC)      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)


11am (UTC)      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)


12pm (UTC)      Bordeaux Seminar, France (organized by Marthe Bonamy)


1pm (UTC)      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)


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

Speaker: Dhruv Mubayi (University of Illinois at Chicago)


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

Speaker: James Davies (Waterloo)


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

Speaker: Jacob Fox (Stanford)


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

Speaker: Allan Sly (Princeton)


6pm (UTC)      Rio Seminar, Brazil (organized by Rob Morris)

Speaker: Marcelo Campos (IMPA)


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

Speaker: Jim Geelen (University of Waterloo)


8pm (UTC)      AGCO Seminar, Chile (organized by Maya Stein)

Speaker: David Conlon (Caltech)


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

Speaker: Fan Chung (UCSD)


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

Speaker: Andrew Suk (UCSD)


11pm (UTC)     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.