## BCC 2021

**28th British Combinatorial Conference**

**5th - 9th July 2021**

Delivered Online from Durham

Delivered Online from Durham

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 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.

The programme will be announced in Spring 2021. 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 will be available soon.

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.

**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 (LSE)

**Extremal combinatorics**

Organiser: Peter Allen (LSE)

Michelle Delcourt (Ryerson University)

Anita Liebenau (UNSW Sydney)

Natasha Morrison (University of Victoria)

Olaf Parczyk (LSE)

**Graph colouring**

Organiser: Irena Penev (Charles Universiy, 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)

Delegates wishing to give a 20 minute contributed talk on any topic within Combinatorics will be invited to submit a title and abstract early in 2021.

- Conference: 5th - 9th July 2021

Further information on registering for the conference and submitting contributed talks will appear here later in 2021.

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**

- Konrad Dabrowski
- Max Gadouleau (Chair)
- Nicholas Georgiou
- Matthew Johnson
- George Mertzios
- Daniel Paulusma

contact: bcc.2021@durham.ac.uk