BCC 2021

28th British Combinatorial Conference
5th - 9th July 2021
Delivered Online from Durham

The British Combinatorial Conference is a biennial event organized in the UK attracting international researchers in all areas of combinatorics.

The 2021 event is the 28th conference in the series and is being held online organized by the Departments of Computer Science and Mathematical Sciences in Durham under the auspices of the ACiD research group.

The conference is overseen by the British Combinatorial Committee.

PLENARY SPEAKERS

Image

Karim Adiprasito Copenhagen

Image

Daniele Bartoli Perugia

Image

Marthe Bonamy Bordeaux

Image

Catherine Greenhill UNSW Sydney

Image

Martin Grohe Aachen

Image

Deryk Osthus Birmingham

PROGRAMME

Below are the titles and abstracts (click on the title) of the plenary lectures and a list of the mini-symposia. There will also be contributed talks. Details of how to submit an abstract for a contributed talk are below. The deadline for submitting is 14 May.

Plenary Lectures

Karim Adiprasito: The partition complex: an invitation to combinatorial commutative algebra

We provide a new foundation for combinatorial commutative algebra and Stanley-Reisner theory using the partition complex introduced in earlier work. One of the main advantages is that it is entirely self-contained, using only a minimal knowledge of algebra and topology. On the other hand, we also develop new techniques and results using this approach. In particular, we provide

  • A novel, self-contained method of establishing Reisner's theorem and Schenzel's formula for Buchsbaum complexes.
  • A simple new way to establish Poincaré: duality for face rings of manifolds, in much greater generality and precision than previous treatments.
  • A "master-theorem" to generalize several previous results concerning the Lefschetz theorem on subdivisions.
  • Proof for a conjecture of Kühnel concerning triangulated manifolds with boundary

This is joint work with Geva Yashfe.

Daniele Bartoli: Hasse-Weil type theorems and relevant classes of polynomial functions

Several types of functions over finite fields have relevant applications in applied areas of mathematics, such as cryptography and coding theory. Among them, planar functions, APN permutations, permutation polynomials, and scattered polynomials have been widely studied in the last few years.

In order to provide both non-existence results and explicit constructions of infinite families, sometimes algebraic varieties over finite fields turn out to be a useful tool. In a typical argument involving algebraic varieties, the key step is estimating the number of their rational points over some finite field. For this reason, Hasse-Weil type theorems (such as Lang-Weil's and Serre's) play a fundamental role.

Marthe Bonamy: Decomposing the edges of a graph into simpler structures

We will review various ways to decompose the edges of a graph into few simple substructures. We will mainly focus on variants of edge colouring, and discuss specifically the discharging method and re-colouring techniques.

Catherine Greenhill: Generating graphs randomly

Graphs are used in many disciplines to model the relationships that exist between objects in a complex discrete system. Researchers may wish to compare a network of interest to a "typical" graph from a family (or ensemble) of graphs which are similar in some way. One way to do this is to take a sample of several random graphs from the family, to gather information about what is "typical". Hence there is a need for algorithms which can generate graphs uniformly (or approximately uniformly) at random from the given family. Since a large sample may be required, the algorithm should also be computationally efficient.

Rigorous analysis of such algorithms is often challenging, involving both combinatorial and probabilistic arguments. We will focus mainly on the set of all simple graphs with a particular degree sequence, and describe several different algorithms for sampling graphs from this family uniformly, or almost uniformly.

Martin Grohe: Recent advances on the graph isomorphism problem

We give an overview of recent advances on the graph isomorphism problem. Our main focus will be on Babai's quasi-polynomial time isomorphism test and subsequent developments that led to the design of isomorphism algorithms with a quasi-polynomial parameterized running time of the form \(n^{\operatorname{polylog} k}\), where \(k\) is a graph parameter such as the maximum degree. A second focus will be the combinatorial Weisfeiler-Leman algorithm.

This is joint work with Daniel Neuen

Deryk Osthus: Extremal aspects of graph and hypergraph decomposition problems

We survey recent advances in the theory of graph and hypergraph decompositions, with a focus on extremal results involving minimum degree conditions. We also collect a number of intriguing open problems, and formulate new ones.

This is joint work with Stefan Glock and Daniela Kühn

Oleg Pikhurko: Borel combinatorics of locally finite graphs

We provide a gentle introduction, aimed at non-experts, to Borel combinatorics that studies definable graphs on topological spaces. This is an emerging field on the borderline between combinatorics and descriptive set theory with deep connections to many other areas.

After giving some background material, we present in careful detail some basic tools and results on the existence of Borel satisfying assignments: Borel versions of greedy algorithms and augmenting procedures, local rules, Borel transversals, etc. Also, we present the construction of Andrew Marks of acyclic Borel graphs for which the greedy bound \(\Delta+1\) on the Borel chromatic number is best possible.

In the remainder of the paper we briefly discuss various topics such as relations to \({\sf Local}\) algorithms, measurable versions of Hall's marriage theorem and of the Lovász Local Lemma, applications to equidecomposability, etc.

Cheryl Praeger: Codes and designs in Johnson graphs with high symmetry

The Johnson graph \(J(v, k)\) has, as vertices, all \(k\)-subsets of a \(v\)-set \(V\), with two \(k\)-subsets adjacent if and only if they share \(k-1\) common elements of \(k\). Subsets of vertices of \(J(v, k)\) can be interpreted as the blocks of an incidence structure, or as the codewords of a code, and automorphisms of \(J(v, k)\) leaving the subset invariant are then automorphisms of the corresponding incidence structure or code. This approach leads to interesting new designs and codes. For example, numerous actions of the Mathieu sporadic simple groups give rise to examples of Delandtsheer designs (which are both flag-transitive and anti-flag transitive), and codes with large minimum distance (and hence strong error-correcting properties). The paper surveys recent progress, explores links between designs and codes in Johnson graphs which have a high degree of symmetry, and discusses several open questions.

Colva Roney-Dougal: Maximal subgroups of finite simple groups: classifications and applications

This paper surveys what is currently known about the maximal subgroups of the finite simple groups. After briefly introducing the groups themselves, if their maximal subgroups are completely determined then we present this classification. For the remaining finite simple groups our current knowledge is only partial: we describe the state of play, as well as giving some results that apply more generally. We also direct the reader towards computational resources for the construction of maximal subgroups.

After this, we present three sample applications, selected because they combine group theoretical and combinatorial arguments, and because they use either or both of the detailed classifications and the looser statements that can be made about all maximal subgroups. In particular, we discuss results relating to generation, and the generating graph; results concerning bases; and some applications to computational complexity, in particular to graph colouring and other problems with no known polynomial-time solution.


Mini-Symposia

  • Codes and cryptography
    Organiser: Maura Paterson (Birkbeck, University of London)
    Lilya Budaghyan (University of Bergen)
    Michael Kiermaier (University of Bayreuth)
    Siaw-Lynn Ng (Royal Holloway, University of London)
    Doug Stinson (University of Waterloo)

  • Designs and Latin squares
    Organiser: Ian Wanless (Monash University)
    Peter Cameron (University of St Andrews)
    Nick Cavenagh (University of Waikato)
    Peter Dukes (University of Victoria)
    Liana Yepremyan (London School of Economics)

  • Extremal combinatorics
    Organiser: Peter Allen (London School of Economics)
    Michelle Delcourt (Ryerson University)
    Anita Liebenau (UNSW Sydney)
    Natasha Morrison (University of Victoria)
    Olaf Parczyk (London School of Economics)

  • Graph colouring
    Organiser: Irena Penev (Charles University, Prague)
    Louis Esperet (Université Grenoble Alpes)
    Chính T. Hoàng (Wilfrid Laurier University)
    Sophie Spirkl (University of Waterloo
    Nicolas Trotignon (ENS Lyon)

  • Probabilistic combinatorics
    Organiser: Agelos Georgakopoulos (University of Warwick)
    Andreas Galanis (University of Oxford)
    Alexander Holroyd (University of Bristol)
    Tobias Müller (Groningen University)
    Leonardo Rolla (University of Warwick)

  • Temporal graphs
    Organiser: Thomas Erlebach (University of Leicester)
    Kitty Meeks (University of Glasgow)
    Hendrik Molter (TU Berlin)
    Nils Morawietz (Philipps-Universität Marburg)
    Amitabh Trehan (Durham University)

CONTRIBUTED TALKS

Delegates wishing to give a 20 minute contributed talk on any topic within Combinatorics are invited to submit a title and abstract.

Please use this template and email your abstract to bcc.2021@durham.ac.uk. We will reply to confirm that your abstract is accepted. Speakers should also register for the conference. When scheduling your talk, we will assume that you are resident at your home institution and bear in mind its time zone.

The deadline for submitting abstracts is 14 May.

REGISTRATION

If you wish to attend the conference please complete the registration form here. The deadline for registration is 18 June 2021.

If you wish to give a contributed talk, please see the instructions above and note the earlier deadline of 14 May.

There is no fee to register. An edited volume of Surveys in Combinatorics containing a chapter by each of the invited speakers will be published before the conference. This is not included in the registration fee, but it will be possible to purchase a hardcopy for £45 (with free delivery to most locations). When further information is available, it will be posted here and emailed to registered participants. Registered participants will have access to a digital copy during the conference and will be able to view and download chapters of the volume.

Registered Participants

  • Atif Abueida, University of Dayton
  • Duncan Adamson, University of Liverpool
  • Karim Adiprasito, University of Copenhagen
  • Muhammad Ajmal, Nanjing University of Aeronautics and Astronautics
  • Bogdan Alecu, University of Warwick
  • Peter Allen, London School of Economics
  • Sarwan Ali, Georgia State University
  • Awss Alogaidi, Middle Technical University
  • I Wayan Palton Anuwiksa, Institut Teknologi Bandung
  • A. Arul Shantrinal, Hindustan Institute of Technology and Science
  • Robert Bailey, Grenfell Campus, Memorial University of Newfoundland
  • Daniele Bartoli, University of Perugia
  • Edy Tri Baskoro, Institut Teknologi Bandung
  • Benjamin Aram Berendsohn, Freie Universität Berlin
  • David Bevan, University of Strathclyde
  • Ez-Zobair Bidine, Hassan First University
  • Anurag Bishnoi, TU Delft
  • Simon Blackburn, Royal Holloway, University of London
  • Jan Bok, Charles University
  • Marthe Bonamy, University of Bordeaux
  • Julia Böttcher, London School of Economics
  • Samuel Braunfeld, University of Maryland, College Park
  • Robert Brignall, The Open University
  • Thomas Britz, UNSW Sydney
  • Lilya Budaghyan, University of Bergen
  • Benjamin Merlin Bumpus, University of Glasgow
  • Yudhistira Bunjamin, UNSW Sydney
  • Thomas Butterfield, Durham University
  • Asier Calber, Queen Mary University of London
  • Peter Cameron, University of St Andrews
  • Chiara Capresi, Università degli Studi di Siena
  • Nick Cavenagh, University of Waikato
  • Kelly Chang
  • Daniel Cocks, The Open University
  • Konrad Dabrowski, University of Leeds
  • Bapan Das, Balurghat College
  • Sweta Das, Indian Institute of Technology, Madras
  • Akbar Davoodi, Czech Academy of Sciences
  • Bishal Deb, University College London
  • Michelle Delcourt, Ryerson University
  • Zakir Deniz, Duzce University
  • Stoyan Dimitrov, University of Illinois at Chicago
  • Kamal Dliou, Ibnu Zohr University
  • Peter Dukes, University of Victoria
  • Calina Durbac, Durham University
  • Joshua Erde, TU Graz
  • Thomas Erlebach, University of Leicester
  • Louis Esperet, Université Grenoble Alpes
  • John Fink, University of Michigan - Dearborn
  • Felix Fischer, Queen Mary University of London
  • Jan Foniok, Google Switzerland
  • Tony Forbes
  • Andrea Freschi, University of Birmingham
  • Max Gadouleau, Durham University
  • Andreas Galanis, University of Oxford
  • Agelos Georgakopoulos, University of Warwick
  • Nicholas Georgiou, Durham University
  • Irene Gil Fernández, University of Warwick
  • Shoni Gilboa, The Open University of Israel
  • Kirithiga Nandini Gnanasekaran, Hindustan Institute of Technology
  • Martin Charles Golumbic, University of Haifa
  • Bertille Granet, University of Birmingham
  • Baruch Granovsky, Technion
  • Ron Gray, Queen Mary University of London
  • Catherine Greenhill, UNSW Sydney
  • Martin Grohe, Aachen University
  • Harald Gropp, Universität Heidelberg
  • Pranshu Gupta, Hamburg University of Technology
  • Rimma Hamalainen, California State University Northridge
  • Anoushka Harit, Durham University
  • Tom Harris, Cambridge University Press
  • Matthew Henderson
  • Tim Hetherington, Nottingham Trent University
  • Patrick Hompe, University of Waterloo
  • Eng Keat Hng, London School of Economics
  • Chính T. Hoàng, Wilfrid Laurier University
  • Ruth Hoffmann, University of St Andrews
  • Alexander Holroyd, University of Bristol
  • Jake Horsfield, University of Leeds
  • Siti Humaira, Institut Teknologi Bandung
  • Glenn Hurlbert, Virginia Commonwealth University
  • Joseph Hyde, Birmingham University
  • Kittitat Iamthong, University of Strathclyde
  • Hany Ibrahim, Hochschule Mittweida
  • Bill Jackson, Queen Mary University of London
  • Matthew Johnson, Durham University
  • Robert Johnson, Queen Mary University of London
  • Nina Kamcev, Monash University
  • Hamed Karami, Iran University of Science and Technology
  • Fatma Karaoglu, Tekirdag Namik Kemal University
  • Michael Kiermaier, University of Bayreuth
  • Sergey Kitaev, University of Strathclyde
  • Alexander Kolpakov, Université de Neuchâtel
  • Mirza Krbezlija, UP Famnit
  • Gaurav Kucheriya, Moscow Institute of Physics and Technology
  • Aiya Kuchukova, Duke Kunshan University
  • Manish Kumar, Ben-Gurion University of the Negev, Israel
  • Joshua Lam, UNSW Sydney
  • Craig Larson, Virginia Commonwealth University
  • Van Bang Le, University of Rostock
  • Florian Lehner, TU Graz
  • Yanjia Li, University of Waterloo
  • Anita Liebenau, UNSW Sydney
  • Christian Lindorfer, Graz University of Technology
  • Laila Loudiki, Cadi Ayyad University
  • Vadim Lozin, University of Warwick
  • Robert Luther, Memorial University of Newfoundland
  • Trent Marbach, Ryerson University
  • John Marcoux, Memorial University of Newfoundland
  • Karen Meagher, University of Regina
  • Kitty Meeks, University of Glasgow
  • Criel Merino, Universidad Nacional Autónoma de México
  • George Mertzios, Durham University
  • Peleg Michaeli, Tel Aviv University
  • Xandru Mifsud, University of Malta
  • Iain Moffatt, Royal Holloway, University of London
  • Hendrik Molter, TU Berlin
  • Nils Morawietz, Philipps-Universität Marburg
  • Thomas Morris, Durham University
  • Natasha Morrison, University of Victoria
  • Tobias Müller, Groningen University
  • Maya Nabila, Institut Teknologi Bandung
  • Namrata, University of Warwick
  • Julliano Nascimento, Universidade Federal de Goiás
  • Siaw-Lynn Ng, Royal Holloway, University of London
  • Hai Nguyen, University of Exeter
  • Steven Noble, Birkbeck, University of London
  • Deryk Osthus, Birmingham University
  • Joshua Paik, Penn State University
  • Leonard Paleta, University of Southern Mindanao
  • Christoforos Panagiotis, University of Geneva
  • Olaf Parczyk, London School of Economics
  • Maura Paterson, Birkbeck, University of London
  • Daniel Paulusma, Durham University
  • Irena Penev, Charles University, Prague
  • David Penman, University of London
  • Oleg Pikhurko, University of Warwick
  • Vladimir Potapov, Sobolev Institute of Mathematics
  • Cheryl Praeger, University of Western Australia
  • Thomas Prellberg, Queen Mary University of London
  • Daniel Quiroz, Universidad de Valparaiso
  • Firdavs Rakhmonov, University of Rochester
  • Leonardo Rolla, University of Warwick
  • Colva Roney-Dougal, University of St Andrews
  • Aalekh Roy, Institute of Mathematics and Applications Bhubaneswar, Odisha, India
  • Sanja Rukavina, University of Rijeka
  • Carrie Rutherford, London South Bank University
  • Sarang Sadawarte, Sharda University, India
  • Manjil Saikia, Cardiff University
  • Shohei Satake, Kumamoto University
  • Michael Savery, University of Oxford
  • Irene Sciriha, University of Malta
  • Alex Scott, University of Oxford
  • Mahsa Shirazi, University of Regina
  • Espen Slettnes, University of California, Berkeley
  • Jason Smith, Nottingham Trent University
  • Sophie Spirkl, University of Waterloo
  • Katherine Staden, University of Oxford
  • Dudley Stark, Queen Mary University of London
  • Iain Stewart, Durham University
  • Doug Stinson, University of Waterloo
  • Anna Taranenko, Sobolev Institute of Mathematics
  • Henry (Maya) Thackeray, University of Pretoria
  • Daniel Threlfall, University of Strathclyde
  • Olivier Togni, Université de Bourgogne
  • David Torres Sanchez, Lancaster University
  • Andrew Treglown, Birmingham University
  • Amitabh Trehan, Durham University
  • Nicolas Trotignon, ENS Lyon
  • Tiana Tsang Ung, UNSW Sydney
  • James Tuite, Open University
  • Anton Varonka, Max Planck Institute for Software Systems
  • Coen del Valle, University of Victoria
  • Hiranmayee Venkataramanan, Stella Maris college
  • Ralihe Villagran, CINVESTAV-IPN
  • Andrew Wade, Durham University
  • Hitesh Wankhede, IISER Pune
  • Ian Wanless, Monash University
  • Matthew Watson, Durham University
  • Belinda Wickes, Queen Mary University of London
  • Marcin Witkowski, Adam Mickiewicz University
  • Wolfgang Woess, Institute of Discrete Mathematics, Graz University of Technology, Austria
  • Julia Wolf, University of Cambridge
  • Tin Lok Wong, National University of Singapore
  • Willie Wong, National Institute of Education, Nanyang Technological University of Singapore
  • Daniel Yaqubi, University of Torbat-e-Jam
  • Liana Yepremyan, London School of Economics
  • Mehmet Akif Yetim, Suleyman Demirel University
  • Soukaina Zayat, Lebanese University
  • Zulfaneti Zulfaneti, Institut Teknologi Bandung

DURHAM

The conference is hosted online by Algorithms and Complexity in Durham (ACiD), a research group of the Department of Computer Science with members also from the Department of Mathematical Sciences.

Organizing Committee

contact: bcc.2021@durham.ac.uk